avl question with example

lets suppose i have this tree
Attachment 15783

the node with data = 35 was the last node added and has thrown the balance out of wack.
balance of 35 = 0 left 0 right
balance of 40 = 1 left 1 right ....still ok
balance of 30 = 1 left 2 right... still ok
balance of 20 = 1 left 3 right ... problem

so 20 is the first unbalanced node.
q1) is that a right right left problem?
q2) if so do i solve it with a left right rotation
q3) how do i decide which is the rt node and which nodes are A B and C ie which node do i rotate about and keep track of its children and grandchildren

I don't think an AVL would get to this state, it would have been tightly balanced before this condition.

I say that because 35 is what you're adding, but if I say 35 didn't exist (the state before the insertion), the tree was already not balanced.

That's key to AVL. AVL can't balance a tree if it was more than 1 node out of balance. That is, AVL will allow only one node to be slightly out of balance simply because that last node was an "odd entry". I'm not saying trees have even numbers when balanced. Factually, only an odd number of entries could be perfectly balanced. You can see that with just 3 nodes. A balanced 3 node tree would have one left, one right and the root. An even number of nodes would unbalance that tree no matter what, but by only 1 node. So when I say an "odd entry", I'm saying that one unbalanced node situation AVL can permit.

So, I must first imagine than not only 35, but 40 and 25 are not there.

At that point the tree is perfectly balanced.

EDIT:

Ok, I'm wrong.

I found this really nice looking visualization tool you'll want to use.

AVL Tree Visualzation


I'll refresh my memory, pour the second, and by the third I'll be in shape to be more coherent on what's next.

i don't understand why the tree is out of balance if you are allowed -1 0 or 1
Attachment 15784

just focusing on the right side from the root and skipping the nodes with no children (bf = balance factor)
node 30: 1 node left and 1 node right bf = 1 - 1 = 0
node 20: 1 node left and 2 nodes right bf = 1 - 2 = -1
node 15: 2 nodes left and 3 nodes right bf = 2 - 3 = -1

if we add node 35 back in
node 40: 1 node left 0 nodes right bf = 1 - 0 = 1
node 30: 1 node left 2 nodes right bf = 1 - 2 = -1
node 20: 1 node left 3 nodes right bf = 1 - 2 = -2 first issue do a rotation of some sort

coop

Like I edited - I needed more coffee...check the visual tool I linked. It's quite good.

It animates the balancing, you can build this exact tree there and watch the solution.

Even back it up and roll it forward.

sorry you must of edited as i posted

It turns out that when 35 is added, the rotation happens at 20. It is rotated to the left, so 30 is connected to 15, 20 is on it's left, 40 on it's right.