Hey people, yes, it's me again.
A quick note - I wasn't asking for people to suddenly correct my code, that isn't my plan.
My plan is simple: I would like to understand how to correct the balances of nodes that are rotated, in LRR, LRL, RLR, RLL cases.
Simple : Left-Heavy, right-heavy, left-right heavy, right-left heavy rebalancing is working just fine. Just, The only thing is - The nodes balances after those special cases (Left-right-left, for example) aren't really being corrected.
So far, my solution is drawing hundreds of AVL diagrams all over any piece of paper I can find and trying to determine what the balances would be after such an operation.
Any help would be greatly appreciated, even if it is a detailed explanation of performing a left or right rebalance.
Im on my knees here people, Im kind of stumped. So far, My code seems to function fine, the problem is I just dont trust it, and I cant trust it until I know for sure that what Im doing to resolve an imbalance is correct.
~Zeii (The helpless)
AVL Tree : Help, please?
-
Combuster
- Member
- Posts: 9301
- Joined: Wed Oct 18, 2006 3:45 am
- Libera.chat IRC: [com]buster
- Location: On the balcony, where I can actually keep 1½m distance
- Contact:
the general algorithm is like:
find location to insert node
walk up, adjusting weights if necessary, and for each node you pass check that:
-1 <= the depth of the left tree - depth of right tree <= 1
if that does NOT hold:
take the current node (1) and the smallest subtree attached to it (a)
go down to the heaviest node (2), and record the smallest subtree from there (b)
go to the heaviest node (3), and record the two remaining subtrees (c, d).
remove this part of the tree and rebuild as follows:
the new top node is (2)
attach the two subnodes (1) and (3) in the correct location
attach the four subtrees (a,b,c,d) to (1) and (3) in the logical location.
if you reorder after an insert, you are done. if you reorder after a delete, you'll have to continue up to the root.
how it works:
the smallest subtree (1) on the errorenous node is 2 levels shorter than the other subtree: the difference was previously one, and an insert could only have increased this level by one - hence its always 2.
now the other subtree has a height that's two in excess. it also has two subtrees which are different in size: if they are equal then there would have been two added nodes whereas we only inserted one, if they are apart more we would have rebalanced before. (the smaller tree is (2))
The heaviest subtree has again a node and two subtrees. one equals the height of the previous subtree mentioned (3), the other is one larger for the same reason (4).
now: the subtrees are in size
(1) N
(2) N+1
(3) N+1
(4) N+2
by reordering we move down 1, 2 ends up at the same level, and move up 3 and 4 so after reordering the weights are:
(1) N+1
(2) N+1
(3) N
(4) N+1
which satisfy the balance property.
Maybe i should create some images that explains what happens...
find location to insert node
walk up, adjusting weights if necessary, and for each node you pass check that:
-1 <= the depth of the left tree - depth of right tree <= 1
if that does NOT hold:
take the current node (1) and the smallest subtree attached to it (a)
go down to the heaviest node (2), and record the smallest subtree from there (b)
go to the heaviest node (3), and record the two remaining subtrees (c, d).
remove this part of the tree and rebuild as follows:
the new top node is (2)
attach the two subnodes (1) and (3) in the correct location
attach the four subtrees (a,b,c,d) to (1) and (3) in the logical location.
if you reorder after an insert, you are done. if you reorder after a delete, you'll have to continue up to the root.
how it works:
the smallest subtree (1) on the errorenous node is 2 levels shorter than the other subtree: the difference was previously one, and an insert could only have increased this level by one - hence its always 2.
now the other subtree has a height that's two in excess. it also has two subtrees which are different in size: if they are equal then there would have been two added nodes whereas we only inserted one, if they are apart more we would have rebalanced before. (the smaller tree is (2))
The heaviest subtree has again a node and two subtrees. one equals the height of the previous subtree mentioned (3), the other is one larger for the same reason (4).
now: the subtrees are in size
(1) N
(2) N+1
(3) N+1
(4) N+2
by reordering we move down 1, 2 ends up at the same level, and move up 3 and 4 so after reordering the weights are:
(1) N+1
(2) N+1
(3) N
(4) N+1
which satisfy the balance property.
Maybe i should create some images that explains what happens...
Thanks Combuster.
I understand the concept of AVL. Just, implementing it has been kinda difficult!
To my glee, I think I managed to get insertion and reordering working!
After a few hours of diagram drawing, I think ive managed to get it.
As per usual, I have my source included with this post.
Feedback or advice would be appreciated.
Im hopeful at the moment, It seems to be working okay and my integrity checking functions say that the tree is fine.
Specifically, Rebalance_left, rebalance_right functions.
~Zeii
I understand the concept of AVL. Just, implementing it has been kinda difficult!
To my glee, I think I managed to get insertion and reordering working!After a few hours of diagram drawing, I think ive managed to get it
.As per usual, I have my source included with this post.
Feedback or advice would be appreciated.
Im hopeful at the moment, It seems to be working okay and my integrity checking functions say that the tree is fine.Specifically, Rebalance_left, rebalance_right functions.
~Zeii
- Attachments
-
- zcapp-avl-0029200307.tar.gz
- (3.28 KiB) Downloaded 51 times