Binary Search Trees

Ordered dictionary which is a binary tree, T, such that each internal node v of T stores an item (k, e) of dictionary, D, and

• Keys stored at nodes in the left subtree of v are less than or equal to k.

• Keys stored at nodes in the right subtree of v are greater then or equal to k.

External nodes do not store any items, NULL_NODE.

Implements Dictionary.

Example Binary trees: page 382

                       55
           23                75
      20     30                  85
10                                     95

Searching

At each node compare search key, k, with the key at the node v, key(v).

if k < key(v) then go left
if k > key(v) then go right
if k = key(v) then return v

The algorithm can be recursive

Data Structure

Although not necessary, the author implements the search tree using empty externals.  So if the search terminates at an external the key was not found.  Although this simplifies the coding, it double the space cost.

Algorithms

Search

TreeSearch(k, v)  // java implementation is called findPosition and no tree is given because it is a method of the class.

input: search key, k, and node v of binary search tree, T.
output: A node w of the subtree T rooted at v, such that either w is an internal node storing key k, or w is an external node where an item with key k would belong.

// base case
if v is an external node then    // External node
    return v
if k = key (v) then                 // found key
    return v

// recursive cases
if k < key(v) then
    return TreeSearch(k, T.leftChild(v))
else
    return TreeSearch(k, T.rightChild(v))

end TreeSearch

Cost

Constant time, O(1), at each node. Total time is O(h) where h is the height of the tree.  On average h = O(lg n), worst case h = n where n is the number of items in the Dictionary.

Insertion

insert(k, e) of Dictionary implemented with a binary search tree, T.
calling TreeSearch(k, T.root()) returns node w

• if the node w is an external then  insertAtExternal(w, e). And add two empty externals.

• if the node w is an internal (this means a collision or items with the same key) then repeat TreeSerarch on right or left child until we find external.   By consistently using right or left child, collisions will be inserted below the collision point in the appropriate place.

Note how collisions are handled.
Complexity is O(h).

Removal

Implementation of remove(Entry e) is tricky because we do not want to leave a hole in a tree. Recall that the text book  uses empty externals so reaching an external in a search implies there is no such key.

The text book uses removeExternal(v), which replaces v's parent with v's sibling and removes v and v's parent from the treee

Start with TreeSearch(k, T.root()) to find a node, w, that is storing key k.

If the returned node, w, is an external then there is no match and remove returns NO_SUCH_KEY.
If the returned node, w, is an internal then there is a match that we wish to remove. There are two cases:

• If one of w's children is an external, say z, then use removeExternal(z), in effect replace w with the other child.

• If both children of w are internal then:

  • Find first internal node, y,  searching left in w's right subtree that has an external left child, x.  y is safe to replace with w because will be greater then w's leftChild but less then all the nodes in w's right subtree.

• Store item of w in a temporary variable, t, and move item in y to node w.

• patch links such  that  y 's right child point to y 's parent and visa versa. Remove nodes x and y from the tree, T, using removeExternal(x) patches links.

• Return the item store in t.

Complexity is O(h) for removeElement.  removeAllElements is O(h+s), where s is the number of elements with key k.

Cost

We like the height, h, to be O(lg n), but this depends on the order of construction of the tree.