Hanging in the balance

I'm really running out of puns for titles. In this post I wanted to talk some more about Binary Search Trees. But more specifically how to balance them - that's where I left off on my lat post.

The most common technique for balancing a tree is rotation. Rotating a tree is quite simple:

Lets say we have a tree:
     20
    /    \
 10    30
  /\
5 15
If we rotate it right we get
10
 /  \
5  20
    / \
 15  30
And vice versa.

As you can see that really didn't help much since the balance of left and right only differed by 1.
But if it differs by 2..
1
 \
  2
   \
    3
Rotate left and...
    2
  /    \
1       3
Bam! A balanced tree. A tree like that will become way more efficient add items to.
Actually properly implementing tree rotation is a lot more complicated, but feel free to give it a shot and let me know how it goes.

What I just showed you is based off an AVL tree(see link below).
There is also a different way to balance - using red-black trees.
It still uses rotation but the way it figures out what to rotate is a little different.
Check it out below!


I've thrown in some links here for you guys to check out if you'd like to learn more:
http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html

Once again, thanks for reading. I'll probably make another post this week so stay tuned!