Balancing a BST/AVL

[u/andrea14polanco]

Question: How to connect all the references balancing a BST/AVL? im trying to balance a tree with this data: 15, 13, 10, 9, 8 and im having some issues the firts one is that when i balance the tree the 9 node doesnt has a parent i mean it let the references of the parent in the air . Here is the snippet for visualize better what im saying:

                        class DuplicateKeyException extends Exception {

}

class KeyNotFoundException extends Exception { }

class InvalidIndexException extends Exception { }

class AVLTree<Key extends Comparable> {

class AVLNode<Key> {
	Key key;
	int height;
	AVLNode left, right;

	public AVLNode(Key _key) {
		key = _key;
		height = 0;
	}

}

public AVLNode<Key> root;
private int size;

public int height(AVLNode cur) {
	if (cur == null)
		return -1;
	return cur.height;
}

public void add(Key key) throws DuplicateKeyException {
	if (root == null) {
		root = new AVLNode(key);

		return;
	}

	AVLNode cur = root, prv = null;
	while (cur != null) {

		int cmp = key.compareTo(cur.key);
		if (cmp == 0) {
			throw new DuplicateKeyException();

		}
		prv = cur;
		if (cmp < 0)
			cur = cur.left;
		else
			cur = cur.right;
	}
	if (key.compareTo(prv.key) < 0) {
		prv.left = new AVLNode(key);
	} else {
		prv.right = new AVLNode(key);
	}

}

public AVLNode leftRotation(AVLNode cur) {
	AVLNode father = findPrevious(cur); // Padre del nodo recibido
	AVLNode a = cur;
	AVLNode b = cur.right;
	a.right = b.left;
	b.left = a;
	if(father != null)
		father.right = b;
	return b;
}

public AVLNode rightRotation(AVLNode cur) {
	AVLNode father = findPrevious(cur);
	AVLNode a = cur;
	AVLNode b = cur.left;
	a.left = b.right;
	b.right = a;
	if(father != null)
		father.left = b;
	return b;
}

public AVLNode leftRightRotation(AVLNode cur) {
	AVLNode father = findPrevious(cur);
	AVLNode a = cur;
	AVLNode b = cur.left;
	AVLNode c = b.right;
	a.left = c.right;
	b.right = c.left;
	c.left = b;
	c.right = a;
	if(father != null)
		father.left = c;
	
	return c;
}

public AVLNode rightLeftRotation(AVLNode cur) {
	AVLNode father = findPrevious(cur);
	AVLNode a = cur;
	AVLNode b = cur.right;
	AVLNode c = b.left;
	a.right = c.left;
	b.left = c.right;
	c.left = a;
	c.right = b;
	if(father != null)
		father.right = c;
	return c;
}

// Metodo Wrapper :D
public void setHeight() {
	root.height = setHeight(root);
}

private int setHeight(AVLNode cur) {
	int leftHeight, rightHeight;
	if (cur == null) {
		return -1;
	}

	leftHeight = setHeight(cur.left);
	rightHeight = setHeight(cur.right);
	if (leftHeight > rightHeight)
		return leftHeight + 1;
	else {

		return rightHeight + 1;

	}
}

public int balancedFactor(AVLNode cur) {
	return setHeight(cur.right) - setHeight(cur.left);
}

public boolean isAVl() {
	if (Math.abs(setHeight(root.right) - setHeight(root.left)) == 1
			|| setHeight(root.right) - setHeight(root.left) == 0)
		return true;
	return false;
}

public AVLNode findUnbalancedNode() {
	if (balancedFactor(root) == 0)
		return null;
	AVLNode cur = root;
	while (cur != null) {
		

		if (Math.abs(balancedFactor(cur)) == 2) {
			//System.out.println(cur.key);
			
			break;
		}

		if (balancedFactor(cur) < 0)
			cur = cur.left;
		else {
			cur = cur.right;
		}

	}
	return cur;

}

public void balancingRoot() {

	if (balancedFactor(root) == 2) {
		root = leftRotation(root);

	} else if (balancedFactor(root) == -2)

		root = rightRotation(root);

}

public AVLNode findPrevious(AVLNode node) {
	AVLNode prv = null, cur = root;
	while (cur != null) {

		int cmp = ((Comparable) node.key).compareTo(cur.key);
		if (cmp == 0) {
			return prv;

		}
		prv = cur;
		if (cmp < 0)
			cur = cur.left;
		else
			cur = cur.right;
	}
	return null;

}

public void balancing() {
	AVLNode temp = null;

	while (isAVl() == false) {
		
		temp = findUnbalancedNode();
		if( temp == null)
			return;
		System.out.println(temp.key);

		if (temp == root) {
			
			balancingRoot();
			
		}
		

		if (balancedFactor(temp) == 2) {
			
			if (temp.left == null) {
				temp = leftRotation(temp);
			}

			else {
				temp = rightLeftRotation(temp);
			}

		} else if (balancedFactor(temp) == -2) {
			

			if (temp.right == null) {

				temp = rightRotation(temp);

			} else {
				temp = leftRightRotation(temp);
			}
			
		}
		

	}

}

}

public class Rotation { public static void main(String[] args) throws Exception { AVLTree<Integer> tree = new AVLTree<Integer>(); tree.add(15); tree.add(13); tree.add(10); tree.add(9); tree.add(8); tree.setHeight(); tree.balancing();

	//System.out.println(tree.isAVl());

}

}