CODEWITHSUNDEEP
javabinary-treebinary-search-treeavl-tree
Heil
Heil

Reputation: 53

How to update the height of an AVL TREE after a rotation?

enter image description here

I'm trying to implement an AVL TREE and I stumble upon this problem, how to update the height whenever I insert a new node?

I know that I have to update the height of the node all the way up.

For instance, in the image the tree has 2 nodes, 50 and 52. H stands for height, and BF stands for balance factor. After insert the node 51 the and update the heights of all its ancestors (52 and 50) I come across the node 50 that after have its height updated to 3 and BF updated to 2 it becomes unbalanced.

After perform a right left rotation the heights got all messed up. How to update the height correctly after any rotation?

Balance factor = node.right - node.left

public void insertTree(String word) {

        if (nodeCount == 0) {

            this.root = new AVLNode(word, 1, 0, null, null, null);

            AVLNode left = new AVLNode(null, null, 0, 0, this.root, null, null);
            AVLNode right = new AVLNode(null, null, 0, 0, this.root, null, null);

            this.root.setLeft(left);
            this.root.setRight(right);

            this.nodeCount++;
            return;
        }

        AVLNode nodeFound = treeSearch(word, this.root);
        AVLNode left = new AVLNode(null, 0, 0, nodeFound, null, null);
        AVLNode right = new AVLNode(null, 0, 0, nodeFound, null, null);

        nodeFound.setWord(word);
        nodeFound.setLeft(left);
        nodeFound.setRight(right);
        nodeFound.setHeight(1);
        nodeFound.setBF(0);

        this.nodeCount++;

        // Update height

        updateTree(nodeFound.getParent());

    }

public void updateTree(AVLNode node) {

        while (node != null) {

            AVLNode nodeParent = node.getParent();

            node.setHeight(height2(node));
            balanceFactor(node);
            // Check if its necessary to do any rotation. Update the ancestor of the node
            balance(node);
            node = nodeParent;
        }

    }

public int height(AVLNode node) {

    int heightLeft = node.getLeft().getHeight();
    int heightRight = node.getRight().getHeight();

    int height = 1 + Math.max(heightLeft, heightRight);

    return height;

}

Upvotes: 0

Views: 1032

Answers (1)

LunaVoid
LunaVoid

Reputation: 19

I'm a relatively novice programmer but I figured I would take a stab at answering this because I'm trying to do it right now. From what I know, I would recommend doing a postorder traversal, and updating all the heights as you move out from the furthest out node. Each node will be the maxOf(node->leftheight,node->rightheight), unless the children are null than the height will just be 1. This should allow you to traverse the entire tree and update the heights accordingly.

Upvotes: 0

Related Questions