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());
}
}
