n2xssvv g02gfr12930 <(E-Mail Removed)> wrote:

>This link gives an animated demonstration as well as some theory.

>

>http://www.geocities.com/SiliconVall.../1854/Rbt.html

>

>I've actually got the "Introduction to Algorithms" book referenced

>and I'd recommend it if you're interested in the often unseen

>algorithms used to solve a variety of problems.

>It's heart warming to know that I'm not the only one interested in

>understanding what's really going on and why, and it was from

>looking at the STL code that I became interested in Red Black

>trees. More to the point I decided to develop my own C++ code

>to implement a Red Black tree, both for hard coded data and as

>a template version. I found it satisfying, but it hasn't helped

>career wise yet as far as I can tell.
Thanks for that information, and the information on the book.

I've checked it out on Amazon and it looks very interesting, however

it doesn't list AVL trees in the table of contents.

I think I may be looking for something I can't afford

Probably

Knuth's multi-volume epic!

I read the article "Performance Analysis of BSTs in System Software"

and based on that it looks like, for our application, an AVL tree

would be best, closely followed by a Splay tree so whatever book I go

for needs to at least cover those. Red Black trees would also be a

bonus really. Also the hash table stuff needs to be there as well, and

I spotted something about (I think) directed graphs that I'd like to

read more on.

But thanks again for taking the time to provide me with those links

and info.

Does anyone know anything about this book:

Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching

Pts. 1-4 by Robert Sedgewick