Binary Search Tree balance

Question

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.

The assignments to `node` in `balanceTree` do not accomplish anything. This might be a duplicate of http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value. — ajb, Oct 23 '16 at 19:12
To which side should it rotate? When its bigger than either left or right it rotates the neighbor Node, aint that an infinite loop?(e.g. what is the balance, isnt this a List implementation in the end, which is sorted on hitCount? [Hint hint]) — n247s, Oct 23 '16 at 19:15
@ajb how does the provided link help in this case? The OP knows the mechanism, though doesnt have the right assignments. — n247s, Oct 23 '16 at 19:18
@n247s Hard to say whether the OP knows... I've seen lots of questions where programmers thought assigning to the parameter would have an effect on the parameter passed by the caller. Also, it fits the question: the OP says that a node is deleted, and since there's no deletions in the code, it seems to mean that the node is no longer linked from any parent--which could happen if he passed the parent node (`root` here) as a parameter and expected it to be changed. So... maybe, maybe not. — ajb, Oct 23 '16 at 19:23
It doesn't help. And it's supposed to rotate around the node itself, not the neighbor nodes(it does go in a loop, i've tried it). I've tried making a new temp node and set it to the value the rotate method returns, this does rotate the nodes but not in the way I expected it. There's something wrong in the logic of it but I can't see it. — NaughtySloth, Oct 23 '16 at 19:26
@NaughtySloth I tried to explain why it loops in my answer, please let me know if this is clear enough for you — n247s, Oct 23 '16 at 19:39
@ajb I know what you mean, though maybe not the best hint to the problem. (At least I wouldnt understand if I didnt understand the core mechanism of a java field/refference) — n247s, Oct 23 '16 at 19:43

n247s · Answer 1 · 2016-10-23T20:08:52.973

There are 2 things wrong with this code.
1) I miss the structure of this Tree. So they need to be sorted based on their hitCount, aint that basically a List/Collection sorted on hitCount?

Right now you are swapping Nodes with their left and right Node if they have a higer hitCount than themself. So imagine 2 Nodes [A, B] A has 1 hitCount and B has 2 hitCounts. So on sorting (you'll propably itterate over the Nodes):
Begin situation: [A, B]

First sort: A has lower hitCount than B so swap with right. Result = [B, A]

Second sort: A has lower hitCount than B so swap with left. Result = [A, B]

Where do we end? A better idea might be to use a List and sort the Nodes based on their hitCount. This way you dont have to mess with all this.

2) Your swap methods do not work as you think they do. Take a close look at this:

 static Node rotateWithLeftChild(Node k2) {
     Node k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     return k1;
 }

 // exact the same results:
 static Node rotateWithLeftChild(Node k2)
 {
     k2.left = k2;
     return k2.left;
 }

Doesn't seem right to me. Probably you meant something like :

 static Node rotateWithLeftChild(Node k2)
 {
     Node k1 = k2.left;
     k1.right = k2.right;
     k2.left = k1.left;
     k1.left = k2;
     k2.right = k1;
     return k1;
 }

And of course the opposite goes for "rotateWithRightChild".

I hope this helped you out a bit.

Edit:

How to implement a List/Collection for order? Once a node is added to the tree, simply add the Node to a Lisf/Collection. And when you want to sort the Nodes, simply use this:

 //myNodesCollection is the List/Collection containing all the nodes.
 static void sortByHitCount()
 {
     Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits());
 }

It might seem complicated but this is a method doing all the sorting for you. The first parameter is the List/Collection you want to sort. Second parameter is a comparator which in this case compares each nodes based on their hitCount.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

I understand what You mean about the lists, it's just that I don't have the knowledge or time to redo it using lists. As for Your correction of the method, it still loops, unfortunately. — NaughtySloth, Oct 23 '16 at 19:51
I edited my answer to show a simple List implementation. Im sure its way less time consuming than your current way. Second I corrected the Swap method, but if you read carefully I explained in the first section why it will loop for ever. (Ps. The problem lies in the `balanceTree()` method) — n247s, Oct 23 '16 at 20:06

score 0 · Accepted Answer · answered Oct 23 '16 at 19:53

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.

Binary Search Tree balance

2 Answers2