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!

Sorting it all out

Well, I have missed a couple of SLOG entries over this term, so I’m gonna try to make up for it by posting a few today. In this one I want to talk about sorting algorithms. (In the spirit of holidays this post also includes lots of flashing coloured things) We went over the basic and/or most common sorts:

Bubble

Image by Wikipedia User Swfung8

Insertion

Image by Wikipedia User Swfung8

Selection

Image by Wikipedia User Joestape89

Quick

Image by Wikipedia User Matt Chan

and last but not least Merge

Image by Wikipedia User Swfung8

However the world of sorting doesn't end there. One sort I thought of, and I believe we may have done in class was using a binary tree to sort. You make a Binary search tree and add items accordingly, and then do an inorder traversal of it. The performance of such a sort is quite good: O(n log n) on average )( n) in best case. The worst case is a bit more interesting though where you can have a balanced or unbalanced BST. Balanced means the tree's height is the minimum (or close to) of what it can be (log2 n [thats "log base 2 of n"]) and unbalanced means it is more. Balancing a tree can be quite the overhead but it doesn't have to happen upon every insertion. 

The difference in worst case performance is O(n log n) for balanced and O (n^2) for unbalanced.

Balancing a tree seems rather tricky and I have yet to figure it out exactly, but I hope this sparks some interest in some of you.

Anyways that concludes this post, see you guys next week (actually like a few hours).