3
$\begingroup$

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance tree wnen new node is added, we turn the tree either to left or right, e.g if new node in left child's left subtree (left-left) we turn it to right, or in right-right case we turn it to left.

It is not hard to notice the pattern, that if left subtree is heavier then we turn it to right and vice versa. For me it is like standing and balancing on the board (that's my intuition).

Then I tried to apply this intuition on left-right (left child's right subtree) and right-left (right child's leftsubtree ) case. But I failed. It looks like: Left-right case

Here assume that B is root and new node somewhere in right subtree of C, which root is A. Here one rotation is not enough, i.e. we need to turn it first to left, then to right. So the point is in middle rotation the we make, it is like bringing tree to rotatable form. Because if I have tree in following form, I can just rotate the tree to right, that's all. enter image description here

So it looks like in previous image what we were doing is to bringing the tree to the form of tree as in the last example. Because rotating it directly to right doesn't solve problem, actually we get again unbalanced tree but with right heavy part.

I am familiar with optimization methods, also Pareto efficient points, etc, and somehow feel that there is something like that. If you want to decrease the height of one subtree, then you must increase somewhere, and vice versa. All good people already devised pattern for all cases. But I can't understant what are these properties (maybe how we can mathematically define that properties) of that middle, even stable stage. I feel it, but can not understand these properties. Or maybe I am absolutely wrong. Sorry for long question. But I will be very happy if you answer and clarify this for me.

$\endgroup$
  • $\begingroup$ The intuition is: "It's bad if different branches have very different length. So if that threatens to happen, shift stuff around to prevent that." $\endgroup$ – Raphael Mar 19 '17 at 18:35
  • $\begingroup$ @Raphael, that's okay. I mean what is the intuition of the process of balancing itself? How to know which node should I replace and where? Of course, there are rules for this. But I want to understand the behavior rather than just remembering these rules. $\endgroup$ – Turkhan Badalov Mar 19 '17 at 18:38
  • $\begingroup$ After rotating the tree to limit the height difference you should get the same inorder traversal. Try balancing the all 4 four cases with this idea. I think you will get the same results. $\endgroup$ – Deep Joshi Mar 20 '17 at 6:39
  • $\begingroup$ The term "rotate" is the intuition. Imagine the node is a pulley, and the subtrees are ropes attached to the lead rope on either side. If the ropes are longer on one site, you pull down on the other. $\endgroup$ – Raphael Mar 20 '17 at 7:21

Your Answer

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

Browse other questions tagged or ask your own question.