Balanced Binary Trees

Quote:

Hello toGameDev.net. Below is an article about a highly advanced C++ Tree Class Library (AVL) at www.5trees.com. This product ships with source code and much of the source code can be viewed online. In particular, the sophisticated tree balancing routines may be freely viewed online (see Source Book). For a detailed technical discussion of tree balancing see The Theory of Balanced Binary Trees. The Most Important C++ Types -------------------------------------------------------------------------------- What are the most important classes in computer science? Professor Stroustrup says in his book The C++ Programming Language, "An associative array is probably the most useful general non-built-in type". There are several other types that rival associative arrays for this title. Associative arrays and these other classes are best represented using balanced binary trees - which are AVL Trees (named after G.M.Adel'son-Vel'skii and E.M.Landis). Associative arrays will be discussed shortly, but first some simpler (and almost equally as important) classes will be discussed. Dynamic Arrays A dynamic array is an array of a given type in which objects may be allocated upon request. A dynamic array is accessed through the subscript operator using an unsigned integer index - just like a normal memory array; however, non-consecutive indices may be used. The integer indices of the array are stored in tree form. A code fragment that uses a dynamic array is shown below. array a; a[0] = "String0"; a[10] = "String10"; a[100] = "Hello World"; What this code does is create a dynamic array of strings. The means by which it does this is to instantiate a template. Once the array is created (in the first line), it is loaded with three strings. Behind the scenes, a balanced binary tree with integer keys is created. The entries have integer keys and strings as their data. Finite Ordered Sets The next important type to be discussed is set. A simple example of how sets may be used is shown below. set s; s << 1.5 << 2.5 << 3.5 << 4.5; This code fragment declares a set of floating point numbers. It then adds 4 numbers to the set. An element may be removed from the set as follows. s >> 1.5; Ordered sets are AVL trees. The template that enables the above code may be found at set. This template has a single constructor parameter called a comparator. It is the callback that compares items in the set tree. The code above defaults the comparator and it is automatically generated. For a complete discussion of sets see the topic titled Finite Ordered Sets. Balanced Binary Trees - Associative Arrays The next important class to be discussed is the balanced binary tree class which implements associative arrays. The template for tree has two class parameters - the key type and the data type. For example, consider implementing an associative array with key type string and data type of double. Such a tree can be declared as follows. tree t; The comparator is defaulted to the function for comparing two strings. Such a tree may then be loaded as follows. t["Key5"] = 50.1; t["Key1"] = 10.1; t["Key3"] = 30.1; A full program that uses this code is shown below. // 5Trees -- tree1.cpp -- Tree - Associative Array Access Method #include using namespace std; #include #include using namespace trees; void main() { try { tree t; t["Key5"] = 50.1; t["Key1"] = 10.1; t["Key3"] = 30.1; cout << t; } catch (trees::exception caught) {Collect(); cout << caught;} } The program produces the following output. {(Key1,10.1),(Key3,30.1),(Key5,50.1)} It should be reiterated, the above three class templates are the three most important non-builtin datatypes of the C++ language. They are so important as to be almost mandatory for most programming tasks. The Tree Interfaces Although the above programs may appear to be simple, to implement them properly is surprisingly difficult. The implementation that was chosen is a C Application Programming Interface (API) backed by C++ classes on the inside and C++ templates on the outside. The table below lists the main classes of the library with their associated C API. Template API array Array API set Set API tree Tree API table Table API By viewing the API, it becomes clear that the system is quite large. The Source Code The source code of the above API and the classes which they call may be viewed in the following table. API C++ Class Array API Array Set API Set Tree API Tree Table API Table The class Tree is complex and involves balancing binary trees using the classic AVL algorithms. An explanation of the process may be found in the topic titled The Theory of Balanced Binary Trees. The Significance Any C++ programmer should ask himself/herself, "Can I do without these most important concepts when programming in C++"? The answer is: probably not. Clean code will almost certainly require all of these concepts. The source code of these classes may be purchased at 5Trees.com.