---

3.1.2 BST Based Variable Size Data Arrays

There are available sorted, variable length data associative arrays constructed over binary search trees such as AVL, red/black, AA or RBST (randomized BST). The arrays may be constructed over such BST flavors as plain, threaded and parent pointer.

The plain BST is the binary tree, no memory reserved for fancy operations, no provisions made for fancy operations.

The threaded BST reserves no extra memory over the plain BST. It does, though, make provisions for such operations as finding the previous or the next node (in some traversal order), finding the parent node, etc. Such provisions do come at a price, not necessarily big - some operations may even be faster than over the plain BST.

The parent pointer BST reserves some extra memory for each node to record the parent node address. Such, operations on local nodes, like the ones supported by the threaded BST, are possible. The extra allocation may carry some speed penalty - it much depends on whether the new node side prompts the memory allocator for a different allocation class. Generally, though, the parent pointer BST is faster than the threaded one, and often (due to the block alignment policies of the memory allocator) uses just as much memory.

The AVL trees are the fastest. The red/black trees are still interesting, may even be faster than the AVL ones on selected operations. The AA trees are of no practical interest, the randomized trees are worse yet.

• Plain AVL Associative Array
• Threaded AVL Associative Array
• Parent Pointer AVL Associative Array
• Plain red/black Associative Array
• Parent Pointer red/black Associative Array
• Parent Pointer AA Associative Array
• Plain RBST Associative Array