## Lecture 21 - 03/08

### Binary Search Trees

• Ordered search tree of nodes and edges connecting nodes

• Only one path between any two nodes
• In binary trees, all nodes have 0$0$, 1$1$, or 2$2$ children
• All keys in left subtree of node X are less than X's key; all keys in right subtree of X are greater than X's key
• Search in binary tree: compare search key to root's key, if less/greater than root, search recursively in left/right tree respectively; else return current node

• Runtime of search on balanced/bushy binary tree: logN$\log N$ (since height of tree is logN$\log N$)
• Bushy trees are very fast
static BST find(BST T, Key sk) {
if (T == null)
return null;
if (sk.keyequals(T.label()))
return T;
else if (sk ≺ T.label())
return find(T.left, sk);
else
return find(T.right, sk);
}

• Inserting new key into tree:

• Search for key; if found do nothing
• If not found after search, create new node at current location after the search
static BST insert(BST T, Key ik) {
if (T == null)
return new BST(ik);
if (ik ≺ T.label())
T.left = insert(T.left, ik);
else if (ik ≻ T.label())
T.right = insert(T.right, ik);
return T;
}

• Deleting a key from a BST:

• Three cases: key has no children, one child, or two children
• Case 1 - no children:
• simply sever link to parent, the now isolated key gets reclaimed by memory
• Case 2 - one child:
• Make key node's parent point to key node's child (can do this because of BST property - just like the key node is smaller/larger than parent, the key node's lone child is also smaller/larger than the key node's parent)
• If deleting root node and root has only one child (no parent), then child simply becomes new root
• Case 3 - two children:

• If deleting a node k, use Hibbard deletion to select a new node to go at position k
• Replace with the rightmost(largest)/leftmost(smallest) element of the left/right subtree respectively (in this case g or m; let's choose g)
• Any children of the replacing node (such as f) now become children of replacing node's parent (in this case, e)

Example before and after replacement: