Implementing a balanced binary search tree?

I have implemented a binary search tree and I want to add more functionality in its insertion function to make it a self-balancing tree. I am coding in C#.

Can anybody please suggest me good tutorials or links on this? I did some searches and found some links, but none of them were descriptive enough.

Thanks.

Answers


There are a great many algorithms for self-balancing search trees, many of which are complex and others of which are quite straightforward (albeit, with some caveats).

The book "Introduction to Algorithms, Second Edition" by Cormen, Leisserson, Rivest, and Stein is an excellent introduction to algorithms and covers red/black trees very well. It's also a great book in general on algorithms and data structures.

If you're interested in using splay trees, which are extremely fast and actually quite easy to implement, the original paper on the data structure is very accessible. On top of that, it includes a proof of all the runtime bounds.

The treap is a simple randomized balanced binary search tree that can be implemented quite easily once you know how to implement tree rotations. Tree rotations are also used in splay trees as well, and so it might be worth investigating.

For AVL trees, this lecture seems to be a good resource.

Hope this helps!


check out http://code.google.com/p/self-balancing-avl-tree/ , implements a self balancing avl tree in c#. plus it also implements concatenate and split operations.


Need Your Help

can you prevent a php while loop from erroring out?

php loops

I was wondering if there was a way to prevent a while loop from prematurely erroring out or terminating. I've thrown a try/catch in there and it seems to keep terminating. (As to the cause why it's

how to line up several divs with background images

css background-image

I have a very large image to use as a background image. Because the image is so large, I have divided it into three images that can be stacked one on top of the other.