Search Trees

A search tree is a type of data structure that uses a tree to store sorted data. This is a basic idea with many variations, some listed below.

In our notes on Trees, we introduced trees generally as having arbitrary ordering and arbitrary numbers of children per node. Our definition of a tree was recursive:

"A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root."

- Wikipedia, "Tree (data structure)" [1]

Some examples of types of sorted trees:

• Heaps - a tree in which values progress from smallest (at the root node) to largest (at the leaf nodes). The invariant in this case is that any tree position at height h has a key that is smaller than any tree position at height h+1.
• Binary Search Trees - a search tree in which each node is limited to having at most 2 children. Insert and delete methods maintain sorted order. There is no limitation to the height of this tree, so in the worst case the height of the tree is equal to the number of nodes (completely expanded tree).
• AVL Search Trees - these are balanced binary trees that enforce the constraint that the difference in heights of the left and right subtree is 0 or 1.
• Splay Trees - Splay trees are interesting data structures that maintain the most recently accessed keys at the top of the tree, providing an advantage for applications where some keys are accessed more frequently. With a splay tree data structure, these will be accessed faster. You can use Amortization and the Amortization/Accounting Method to show that these structures have an amortized log(N) cost for operations.