ubiqx library

0. introduction
1. linked lists
2. binary trees
3. cache
4. database

2. Binary Trees

This is really where the ubiqx library started. I was taking a graduate class in Compiler Design (a long time ago). The text stated that binary trees would be a poor choice for maintaining a symbol table so, of course, that's what I decided to use. Simple binary trees were fairly easy to do, so I went for AVL height-balaced trees instead. Needless to say, the compiler I wrote worked just fine. I refined the code over the years and then added the Splay trees (which are niftier than the AVL trees, IMHO).
The ubi_BinTree and ubi_AVLtree modules were originally written for the Amiga. I wanted to be very careful with stack space under AmigaOS, which is why the implementation is non-recursive. Also, AmigaOS was written in plain-old C using object-oriented concepts--a style I tried to emulate.

2.0 overview

Binary trees are typically defined as a collection of linked nodes such that each node has zero, one, or two child nodes. Most implementations manage the tree using recursive function calls, but the ubiqx implementation of binary trees is non-recursive. Depending upon your experience with recursion, this may make the code easier or harder to figure out.

There really are a lot of interesting ways to write binary trees. I know of some folks who use empty child pointers to point to the sequentially previous or next node in the tree (a flag is used to indicate how the pointer is being used). This is known as a Threaded Tree.

The remainder of this section attempts to describe how to use the ubiqx tree modules. If you want to know more about binary trees in general, see the reference section below.

2.1 ubi_BinTree

This is the foundation upon which the AVL and Splay Tree classes are built; the latter are descendant types. The class implemented by ubi_BinTree provides a simple, non-balanced binary tree.

If the data entered into a simple binary tree is pre-sorted, the resultant tree will look, and work, like an ordered linked list. If the data is random, the tree will be "bushier", but it is not likely to be perfectly balanced. Balancing the tree provides the best performance for the search operation, at the cost of some overhead. That being the case, the ubi_BinTree module is suited for:

small sets of data
slightly larger sets generated from random data
acting as the foundation class for the balanced tree classes.

2.1.0 types

ubi_btRoot: This structure represents a tree as a whole. It keeps track of overall tree data, such as the number of entries currently in the tree.
ubi_btRootPtr: Pointer to a ubi_btRoot.

ubi_btNode: A single tree node.
ubi_btNodePtr: A pointer to a ubi_btNode.

2.1.1 macros

2.1.2 functions

2.1.3 quirks

2.2 ubi_AVLtree

2.2.0 types

2.2.1 macros

2.2.2 functions

2.2.3 quirks

2.3 ubi_SplayTree

2.3.0 types

2.3.1 macros

2.3.2 functions

2.3.3 quirks

2.4 binary tree references

These links are the result of a very quick search of the web. A little more digging would likely result in many more fine gems. There seem to be a lot of binary tree demonstrations written in Java.

NIST Dictionary of Algorithms and Data Structures: Binary Search Tree
NIST Dictionary of Algorithms and Data Structures: AVL Tree
NIST Dictionary of Algorithms and Data Structures: Splay Tree
D. Sleater, co-author of the original paper on Splay Trees.

ubiqx development uninq.