Properties

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree must each also be a binary search tree.
4. There must be no duplicate nodes.

Benefits

• Insert, find and remove any entry
• Quickly find entry with min/max key
• Entry nearest another entry, like in a dictionary, but cannot remember how to spell the word

BST Invariant

For any node x, every key in the left subtree of x is <= x’s key

For any node x, every key in the right subtree of x is >= x’s key

Inorder traversal of a binary search tree visits nodes in sorted order, the left of root (18) are displayed before the right.

Operations

Entry Find (Object k)

• Object looking for compared to object stored in key (if it is there)
• If true, returns the entry
• Else returns nil
• Good for exact matches, can do faster with hash table

How to find smallest key >= k or largest key <= k?

When searching down the tree for a key k that is not in the tree, we encounter both.

• Node containing smallest key > k, and
• Node containing largest key < k

<p>Ex. search for 27 as k (from above pic)</p>
<ul>
    <li>Keeps searching nodes to the right, gets to 28 and returns nil</li>
    <li>encounters 25 < k and 28 > k</li>
</ul>

Entry first();
-If empty return null, otherwise start at root and walk down left repeatedly until you reach node with no left child, that node has minimum key.

Entry last();
-Mirror of left, but walks down right tree

Entry insert(Object k, Object v);

• Follow same path through the tree as find();
• When you reach null reference, replace null with reference to new node with entry(k, v), duplicate keys are allowed.
• Puts new entry on the left subtree of old one

The delete operations (where shit gets complex)

Entry remove(Object k);

• Find node n with key k, if k not found return null
• If n has no children, detach it from parent
• If n has one child, move child up to take n’s place
• If node has 2 children
• Suppose we want to remove 12 from above pic
• Let x be the node in n’s right subtree with smallest key
• Keep going to the left, in this case, 13 is node x, only has one child
• Remove x, has no left child and therefore, is easily removed
• Replace n’s key with x’s key

h/t Jonathan Shewchuk at UC Berkeley