3
$\begingroup$

enter image description here

In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees. I have understood how the rotation is working and have no trouble with that. The problem I am having is determining the final balance factor of nodes in the tree. In the first case before rotation, the balance of factor of x will be +2 or -2(that's why we are performing the rotation). But what about the balance factor of y? Why is it always taken as +1 or -1 before rotation? Why it can't be 0(the height of T3 can be equal to the height of z)? What will we the balance factor of z before rotation? It can be anything right? In short, what will be the balance factor of nodes with the question mark before and after the rotation?

This is the code I am trying to write:

Node insert(Node node, int key)
{
    if(node == NULL)
        node = new Node(key);

    else if (key <= node->key)
    {
        node->balance++;
        node->left = insert(node->left, key);
    }

    else if (key > node->key)
    {
        node->balance--;
        node->right = insert(node->right, key);  
    }

    // Right Tree Heavy
    if (node->balance == -2) 
    { 
        /*Do the required rotation and update the balance factor*/
    }

    // Left Tree Heavy
    if (node->balance == 2) 
    {
         /*Do the required rotation and update the balance factor*/
    }

    return node;
}

Edit: Initially the tree was satisfying all the properties of avl tree. Then a new node was added to either T1 or T2 which made the tree unbalanced at node x. Can anyone explain all the cases of balance factor of nodes before and after the rotation.

$\endgroup$
  • $\begingroup$ balance factor of y? Why is it always taken as +1 or -1? please include in such statements before or after rotation. the balance factor of z [after rotation] can be anything right? Before rotation, did the differences in sub-tree heights at $y$ and $z$ stay within limits? $\endgroup$ – greybeard Mar 30 '18 at 7:37
  • $\begingroup$ Yes the difference of height in y and z before rotation is within limits $\endgroup$ – Paras Gupta Mar 30 '18 at 8:00
  • $\begingroup$ difference of height in y and z before rotation is within limits (don't comment comments asking for additional information or clarification: edit your post) Then you should be able to say/argue more about the balance factor of $z$ after rotation than can be anything. $\endgroup$ – greybeard Mar 30 '18 at 8:33
  • $\begingroup$ Why can't [the balance of y] be 0 (the height of T3 can be equal to the height of z)? The presumption will be that the tree rooted at $x$ has been AVL before this insertion of a single node - go through the possibilities. $\endgroup$ – greybeard Mar 30 '18 at 8:38
2
$\begingroup$

The reason that the number of possible values for the balance factors at $y$ and $z$ is limited is not only the fact that the tree has been AVL before insertion, but also the precise location where the rotation is performed in an ex-AVL tree.

Rebalancing is only needed at the lowest position where the balance becomes $\pm 2$ where below had balance factors $0$. All those $0$ balance factors have been changed into $\pm 1$ depending on the side where the key has been entered. The short reason for this is that when a node has originally balance factor $0$ and one of its subtrees becomes taller after insertion, not only the balance factor becomes $\pm 1$ but also the total length of the tree at that node becomes one taller, so we have to consider its father.

  • If that father has balance $0$ it will become $\pm 1$, the tree is taller, and we proceed up again [diagram b)].

  • If the father has balance $\pm 1$ we may happen to improve the balance to $0$, and we stop, no rotation needed [diagram a)].

  • If the balance becomes $\pm 2$ we rebalance at that point using the proper rotation. After rotation the tree at that point has the same height as originally, so we do not have to consider balance factors higher up in the tree. [diagram c)]

inserting a key in AVL-tree, bottom up

So the issue here is to determine the context where the rotation takes place. This is determined by following the insertion process bottom-up, from the leaf where the key was added.

The precise type of rotation (single/double, left/right) is determined by the insertion path that was followed below the node where we rotate.

In the single rotation case we have left-left insertion from $x$ so $y=-1$ (longer to the left, my balance factors are opposite to yours). The value at $z$ is not important, its complete subtree is copied during the single rotation at $x$. In the double rotation case we have left-right insertion from $x$ so again $y=-1$. At $z$ we might have any value: $\pm 1$ depending on whether the key went left/right at $z$, but even $0$ in the special case $z$ itself was inserted!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.