Previous: , Up: Variable Size Data Sequences   [Index]


2.1.2 BST Based Variable Size Data Sequences

There are available sequences constructed over binary search trees such as AVL trees. The sequences may be constructed over such BST flavors as plain, threaded and parent pointer.

The sequences allow for proper random access with O(logN) time.

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.

Three BST supported sequence designs are available.

The first BST supported sequence design stores for each tree node the population of the corresponding subtree (node included) with the node.

The third BST supported sequence design stores for each tree node the population of the subtree corresponding the left child (and including the child) with the node. The design is faster than the first for most operations.


Previous: , Up: Variable Size Data Sequences   [Index]