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

Improve this question
$\endgroup$
8
  • $\begingroup$ here and here I found some information but I still don't get it $\endgroup$
    – TGar
    Jan 5, 2017 at 9:46
  • $\begingroup$ Does this image from the German Wikipedia help? $\endgroup$
    – adrianN
    Jan 5, 2017 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, 2017 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, 2017 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, 2017 at 11:26

1 Answer 1

Reset to default
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.

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

Your Answer

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

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