Search Trees

Notes

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. Useful for implementing Priority Queues.
• 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.

We cover the functionality that any search tree should define in the following order:

• Navigation - methods for moving through the tree
• Find/Search - methods for finding a position corresponding to a particular key
• Get/Set/Delete - methods for getting/setting/deleting a node with a particular key/value in the tree

Navigation

We can navigate a sorted binary tree by providing our tree class with a way of navigating the tree. Specifically:

• First node - keep traversing left in the tree until we hit the left-most node. This will be the minimum key. (This uses find min subtree method below)
• Last node - keep traversing right in the tree until we hit the right-most node. This will be the maximum key.
• Before position - get the position of the node whose key immediately precedes this node's key
• After position - get the position of the node whose key comes immediately after this node's key
• In order traversal
• Reverse order traversal

See Binary Search Trees for more detail on how these can be implemented for a concrete class.

Find

A couple of basic find methods that should be available in a search tree class. It is important to note that the utility methods are defined for SUBTREES, and that means we can apply them to the root node, or we can apply them in other algorithms like rebalancing.

• Find key - find the node corresponding to key k in SUBTREE
• Find min - find the node corresponding to the minimum value in SUBTREE
• Find max - find the value corresponding to the max value in SUBTREE
• Find tree min - returns first
• Find tree max - returns first
• Find greater than or equal to
• Find less than or equal to
• Find range

Get/Set/Delete

The get/set/delete methods require us to be able to search for a node in the tree, so before you can implement get/set/delete methods, you must implement find methods. Once you do, the get/set/delete methods can be implemented:

• First, each of the following methods contains a hook method to rebalance the tree as we access it.
• Get item - Search for a key, and rebalance the tree. If we find the key, return the value at that position
• Set item - Take a key-value pair. Start with the empty case, adding as root; otherwise,
  • If we find the key in the tree, update the value; otherwise,
    • Add the key-value pair as a new node wherever our search ended
• Delete item - Take a key. Start with the empty case - nothing. Search the subtree; if we find something, delete it. Otherwise, rebalance the search tree.

Object Oriented Programming Concepts

Notes on using object-oriented programming when assembling a binary search tree class.