0
$\begingroup$

Consider we have an AVL tree.

Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left subtree has greater length).

If I understand correctly, we're looking for the most right vertex in the left subtree.

After deleting this specific vertex, what are possible cases regarding the tree rebalancing? When will it have to be rebalanced and when not?

Please correct me, if I've made any mistakes.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let $w$ be the node to be deleted

1) Perform standard BST delete for $w$.

2) Starting from $w$, travel up and find the first unbalanced node. Let $z$ be the first unbalanced node, $y$ be the larger height child of $z$, and $x$ be the larger height child of $y$. Note that the definitions of $x$ and $y$ are different from insertion here.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with $z$. There can be 4 possible cases that needs to be handled as $x$, $y$ and $z$ can be arranged in 4 ways. Following are the possible 4 arrangements:

a) $y$ is left child of $z$ and $x$ is left child of $y$ (Left Left Case)

b) $y$ is left child of $z$ and $x$ is right child of $y$ (Left Right Case)

c) $y$ is right child of $z$ and $x$ is right child of $y$ (Right Right Case)

d) $y$ is right child of $z$ and $x$ is left child of $y$ (Right Left Case)

Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node $z$ won’t fix the complete AVL tree. After fixing $z$, we may have to fix ancestors of $z$ as well (See this video if you have trouble visualizing the above mentioned cases).

Courtesy of Geeksforgeeks.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you so much. Could you please tell me also if I'm correct about this: Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left subtree has greater length). Does it mean that in this graph we're looking for the first left vertex that has the first right son? $\endgroup$
    – Mirek
    Commented Nov 13, 2017 at 8:19
  • $\begingroup$ If it helps, than an upvote and an accept is much appreciated. Please rephrase your comment more clearly so I can also answer that. $\endgroup$
    – theSongbird
    Commented Nov 13, 2017 at 10:21
  • $\begingroup$ Certainly, I plan on accepting it as final answer. Well, which vertex is exactly the one that we can find in the left subtree whose disbalance coeff is +1 in its right son (whose coeff is -1)? Does it even affect those cases? $\endgroup$
    – Mirek
    Commented Nov 13, 2017 at 12:00
  • $\begingroup$ @Mirek Let $T$ be you tree and $T_R$, $T_L$ be it's respective right and left subtrees. If depth($T_R$) $\gt$ depth($T_L$) and $T_L$ has a right subtree larger it's left subtree, than this falls in the $2^nd$ case mentioned in my answer: $Left-Right \ Case$. $\endgroup$
    – theSongbird
    Commented Nov 13, 2017 at 15:44
  • $\begingroup$ That's the situation that happens after deleting one vertex. I need that very situation (of course without those subtrees below it - so it's balanced) and then I delete X and I need to know to which one of these groups can it fall to then? $\endgroup$
    – Mirek
    Commented Nov 13, 2017 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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