I’m working on my CS homework, and one of the problems involves inserting a value into an AVL-tree. I came up with at least two ways of doing this, and I was wondering if anyone here knew of the “more correct” way of doing it, out of the two that I’ve done.
The problem, and my 2 solutions
I’m not sure if either is considered better than the other, but if so, could someone help me out?
Thanks
Actually, your tree after insertion doesn’t need to be rebalanced at all. Remember, AVL trees only need rebalancing (or whatever you call it) if the heights of children of the same node differ by more than one. Unless I’m missing something, I don’t think that the tree in 1 is an improper AVL tree at all.
In case you’re interested, my data structures prof from last semester has notes on search trees, including AVL trees, at http://www.cs.jhu.edu/~cohen/CS226/Lectures/SearchTrees.pdf
Awesome! Thanks.
So fig 1 looks like the best solution, since there’s no rebalancing needed?
Fig 1 is actually the only correct solution in this case. While there may be multiple correct AVL trees containing a certain set of letters, there is only one correct way to insert a letter, presuming that there are no duplicates. (Then you could decide to go either right or left at certain points, and… yeah.)
I find it’s easy to think algorithmically, in very careful steps that don’t involve just looking at it and saying “Oh, this goes here!” That is, after all, how you’re going to be implementing an AVL tree in code.
Anyway, here’s how I think about insert for an AVL tree, using yours as an example.
We have N.
Find the root and look at what’s there.
Is M bigger or smaller than N?
Smaller, so go right.
Is P bigger or smaller than N?
Bigger, so go left.
Is O bigger or smaller than N?
Bigger, so go left.
No more nodes for comparison, so N must go here.
Now, we make sure it’s balanced.
The height of N is 0. What’s the height of its sibling?
No sibling, so no problem.
The height of N’s parent, O, is 1. What’s the height of its sibling?
Height of X is 1, so no problem.
The height of O’s parent, P, is 2. What’s the height of its sibling?
Height of E is 2, so no problem.
The height of P’s parent, M, is 3. It’s root, so the tree is balanced and we stop checking.
Awesome-- going by your rules, I came up with these. I think they’re correct.
Close, but not quite. You’re rotating funny.
A and C look fine, no rotations are needed for those.
In B, you would add C to the left of D. First thing you get is… let’s see if I can get this…
M
/ \
E P
/ \ / \
A H O X
\ /
D W
/
C
So you start checking. C has no siblings, so you move up. D has no siblings, so you move up. A has a sibling, H. A is height 2, H is height 0. Uh-oh! You need to rotate!
Now, I’m basically copying thing out of my textbook (Goodrich & Tamassia), because rotate operations are annoying and I want to make sure I do it right.
Anyway, E is the first unbalanced node we find, because one of its children is height 2 and one is height 0. Now, we find its taller child. That’s A. Finally, we find A’s taller child. That’s D, since it’s A’s only child.
To rebalance the tree, we take E, A and D and put them in increasing order: A, D, E. The middle one of those three is D, so D needs to be at the top, with A and E as its left and right children, respectively.
M
/ \
D P
/ \ / \
A E O X
/
W
C H
Now we take C and H (and all of their children, if they had any) and attach them back to the tree, on A and E.
So now we have
M
/ \
D P
/ \ / \
A E O X
\ \ /
C H W
We continue our checking up the tree, and huzzah, everything’s balanced!
Let me know if you understand how this works, and see if you can figure out the last part of the problem on your own. (I know how hard AVL trees can be, so I’ve been nice, but I’m not going to give step-by-step answers after this one.)
I think I see what you’re doing, but isn’t the only requirement of an AVL tree that it be increasing LTR and have a difference of 1 at most between nodes?
So wouldn’t mine fit that?
Also, D looks strikingly similar to your derivation for B. I’m really missing what’s wrong there.
You’re right, any tree that fits that definition is an AVL tree. However, in order to use an AVL tree for a computer science application, you have to have a step-by-step algorithm for inserting new nodes that’ll restructure the tree properly every time, since you want the computer to do it, not you. As far as I am aware, there is a standard method for balancing AVL trees, which is what I’m using to work with these. (I suggest playing with http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html to see how it works) If your assignment had been “Make an AVL tree including these nodes”, then your version would be fine, but the assignment requires insertion into already existing trees. In this case, it’s the process of algorithmically building the tree that’s important, and you can get very different results depending on what order letters are inserted and other stuff. This is why, though your answer for the last part is a valid AVL tree, I still believe it to be an incorrect answer to the problem.
Okay, so applying your method to the last question, I get:
M
/ \
E P
/ \ / \
B H O S
/ \ /
A D R
as opposed to
M
/ \
D P
/ \ / \
A E O S
\ \ /
B H R
Yes? No? I suck? 
Okay, so applying your method to the last question, I get:
M
/ \
E P
/ \ / \
B H O S
/ \ /
A D R
as opposed to
M
/ \
D P
/ \ / \
A E O S
\ \ /
B H R
Yes? No? I suck?
Closer, I think, but still no.
In this case, E is the first unbalanced node. You take E, E’s tallest child, and that child’s tallest child. Then you put them in order. The middle one takes E’s place. The smaller one goes to the left of that, the bigger one to the right of it. Then you reconnect all the other nodes in their proper places, attaching them to the smaller or larger one that you just messed with.
You should’ve been shown examples of this… :mad: I’m annoyed with your department, not you, actually, because this should really be explained thoroughly and doesn’t take that much time if you have some powerpoint slides or something.
I’ve always admired Ben Pfaff’s Libavl 2.0. The library is written as Knuth-style “literate programming”, so it also contains a thorough explanation of the theory behind each type of tree (rotations for balancing), the operations (insert, delete, traversal), plus various implementation details.
It contains binary search, AVL, and Red-Black trees plus threaded, right threaded, and parent pointer varients of the same.
Oy… now I’m really lost…
I did the first using the guidelines you suggested (I thought I did, anyway), and the “as opposed to” one goes BY these guidelines, if I’m not mistaken.
Bah… I’ll figure it out.