2
$\begingroup$

I am trying to find out from this visualization how does the AVL trees work. But I am not able to find out how is the algorithm choosing which vertex is the right one to use as "partial root".

The simple rotation is actually very simple, but when it comes to the double rotation it is much worse.

There are some tricks with signs of vertices when inserting a new vertex, but I don't completely understand that either (and also I am not sure if it is important for the rotation).

EDIT: I add a drawing of my Insertion. I would expect that the double rotation will choose the purple (left) variant (it seems simplier), but the visualization choose the brown one. Why is that?

drawing

$\endgroup$
  • $\begingroup$ here and here I found some information but I still don't get it $\endgroup$ – TGar Jan 5 '17 at 9:46
  • $\begingroup$ Does this image from the German Wikipedia help? $\endgroup$ – adrianN Jan 5 '17 at 9:47
  • $\begingroup$ @adrianN not really, what is the meaning of the numbers there? And I sill don't know how to choose correct vertex.. $\endgroup$ – TGar Jan 5 '17 at 10:02
  • $\begingroup$ Perhaps rather than using a visualization as your sole reference, you should be looking at a complete specification of AVL trees. Have you tried looking at a data structures textbook that covers AVL trees? Have you tried finding a more definitive reference? Have you tried searching online for pseudocode? What research have you done, and what have you found so far? $\endgroup$ – D.W. Jan 5 '17 at 19:10
  • $\begingroup$ @D.W. Yes I was trying to. For example here, here or in our lectures. But I did not understand. $\endgroup$ – TGar Jan 6 '17 at 11:26
1
$\begingroup$

At the drawing is correct the brown variant. The purple isn't binary search tree (thanks, Hendrik Jan for this clarification) at all.
Why? Because it is not in the right order (for all nodes in a BST must be true, that all nodes in its right subtree have bigger value and all nodes in the left subtree have a smaller value than the node).

About the double rotation itself:
The problem was that I didn't know how to choose the correct vertex, the right answer is that you have to take the middle one as the root of the new subtree (11 from the set 10, 11, 14 on my drawing) and the rest must fit the rules for the binary search AVL trees.

$\endgroup$
  • $\begingroup$ I hope it's correct, please note if otherwise. $\endgroup$ – TGar Jan 6 '17 at 18:32

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.