I'm working on a BST that will balance nodes according to their hits and their elements, where a hit is an attribute that increases when a node is found using find(), contains() etc. The root of the tree is the node with the highest number of hits. All of my code is alright, except the balance method that will balance the tree after I increment a hit. I'm using modified AVL Tree rotate methods(https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java) where I don't compare the elements, rather the hits of a node. I can't get it to work no matter what I try, I can't get the tree to balance correctly Here is my code so far:
public void balanceTree() {
balanceTree(root);
}
private void balanceTree(Node node) {
if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) {
return;
} else if (node.left.getHits() > node.getHits()) {
node = rotateWithLeftChild(node);
} else if (node.right.getHits() > node.getHits()) {
node = rotateWithRightChild(node);
}
}
static Node rotateWithLeftChild(Node k2) {
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
static Node rotateWithRightChild(Node k1) {
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
Right now the balance method simply deletes the node its supposed to rotate, I tried debugging it but couldn't see what's wrong.
In java one cannot change the passed parameter, so one needs to return the new Node value.
public void balanceTree() {
root = balanceTree(root);
}
private Node balanceTree(Node node)
if (node.left.getHits() <= node.getHits()
&& node.right.getHits() <= node.getHits()) {
node.left = balanceTree(node.left);
node.right = balanceTree(node.right);
} else if (node.left.getHits() > node.getHits()) {
node = rotateWithLeftChild(node);
} else if (node.right.getHits() > node.getHits()) {
node = rotateWithRightChild(node);
}
return node;
}
Assuming you rebalance the tree after every insert, then one need not recurse after a rotation to balance the subtree.
Without rotation one needs to recurse.
The current algorithm recurses left and then right, but if in the left a rotation took place the right subtree no longer might be recursed.
More worrisome for such kind of modification algorithms is that it might not stabilize: keeping rebalancing. But that you will certainly spot on testing.