binary search trees
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree must each also be a binary search tree.
- There must be no duplicate nodes.
- 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
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.
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>
-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.
-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 BerkeleyHis lecture via Youtube