# binary search trees

## Properties

- 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.

### 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