• Advertisement
Sign in to follow this  

AVL trees - updating balance factors after rotation

This topic is 3317 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was hoping someone could explain how to do this or point me to some online resource. Everywhere I look, it seems like this is done by calculating the height of the children and taking the difference, but I'm sure it can be done in constant time. This page shows how, but when I implement that method my program crashes. I could post the code but it's somewhat long. Also, the derivation there is somewhat tricky so I was hoping someone could provide a simpler explanation. Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Assuming you've written a recursive insertion routine, you simply need to pass back to the previous call whether the height of that branch increased or not, probably using the return value.
The previous call then knows which branch it called itself recursively on, and hence knows whether that branch increased or not. It's a case of adding or subtracting the returned height change to/from the existing balance factor, depending on which branch it was called on. If that pushes the balance factor outside the range -1 .. 1 then you need to rotate. For each rotate you do you know what effect it has on the height, and again return zero or one for whether the height increased or not. And so on.
I have a working implementation on my website.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
For each rotate you do you know what effect it has on the height


Well actually that's what I'm asking - how do I know that?

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
Quote:
Original post by iMalc
For each rotate you do you know what effect it has on the height


Well actually that's what I'm asking - how do I know that?
Sorry I thought you knew what effect the rotates had on the height, but just not how to update the parent's balance factor as a result.
What you've asked for should be all described in the site you linked to. One of the sites I made a fair bit of use of when making mine was the one you've linked to. I found it okay.
Here's another site that might help.

One thing though is that if you get the balance updating wrong, then all you should get is an unbalanced tree. It wouldn't crash unless you're doing something like dereferencing a NULL node. I'm thinking now that it might just be better for someone to take a look at some of your code. Can you provide any more information about the crash?
Either that or you need to compare it against someone else's.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement