Binary Search Tree (ADT)

The binary search tree usually provides the methods:

• get(k): if the map $M$ has an entry $e=(k,o)$ with key $k$, return its associated value $o$, else null.
• put(k,o): if $M$ does not have an entry $(k,o)$ then add it to the map $M$ and return null, else replace the existing value of the entry with key equal to $k$ with $o$ and return the old value.
• remove(k): if the map $M$ has an entry with key $k$, remove it from $M$ and return its associated value, else return null.

For the examples below, we assume that a binary tree supports:

• insertAtExternal(w, (k,o)): insert the element $(k,o)$ at the external node $w$ and expand $w$ to be internal, having new (empty) external node children
• removeExternal(w): remove an external node $w$ and its parent, replacing $w$‘s parent with $w$‘s sibling.

Search

To perform get(k): we search for a key $k$ and trace a downward path starting from the root. The next node visited depends on the comparison of $k$ with the key of the current node. If we reach a leaf, the key is not found.

Insertion

To perform operation put(k,o), we search for key $k$. We assume $k$ is not already in the tree, and let $w$ be the leaf reached by the search. We insert $k$ at node $w$ and expand $w$ into an internal node using insertAtExternal(w, (k, o)).

Deletion

To perform operation remove(k), we search for key $k$. Assume key $k$ is in the tree, and let $v$ be the node storing $k$. If node $v$ has a leaf child $w$, we remove $v$ and $w$ from the tree with the operation removeExternal(w).

We may also have a case where the key $k$ to be removed is stored at a node $v$ whose children are both internal:

• we find the internal node $w$ that follows $v$ in an in-order traversal
• we copy $key(w)$ into node $v$
• we remove node $w$ and left child $z$ (must be a leaf) by removeExternal(z)