2 Years
Discussion Span
Last Post by deceptikon

There are a number of ways to go about it, but I'd suggest starting simple. This is an article that cuts right to the chase and doesn't include any fluff that might confuse the core concepts.

Once you have the basics down you can introduce classes to wrap it all up into a nice package.


Just remember, that inserting already sorted data into a pure binary tree (b-tree) will result in what is effectively a linked list, with unoptimal search characteristics. Once you are able to build a b-tree, then consider building a balanced binary tree. The insert algorithm is more complex as it has to rebalance the tree when necessary, but it will always provide an optimal search performance. This is especially useful for large sets of data. The seminal treatise on this subject is Knuth's "The Art of Computer Programming - Volume 3 - Sorting and Searching".

Edited by rubberman


The article I linked to covers that, and followup articles cover balancing techniques. The problem with Knuth is that it uses a home grown assembly language for code examples. I love the books, don't get me wrong, but translating the code into C++ is more of an intermediate exercise that distracts from the concepts of the data structure.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.