binary search trees

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

His lecture via Youtube

comments powered by Disqus