Week 9. Search Tree Structures

Binary Search Trees

Binary Search Tree

A binary search tree is a binary tree storing keys (or key-value entries) at its internal nodes and satisfying the following property:

• If we let $u$, $v$, and $w$ be three nodes such that $u$ is in the left subtree of $v$ and $w$ is in the right subtree of $v$. We have that $key(u)\le key(v)\le key(w)$.
• External nodes do not store items.
• An In-order traversal of binary search tree visits the keys in increasing order.

Link to original

Binary Search Tree ADT

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)

Link to original

Performance

Consider a map with $n$ items implemented by a binary search tree of height $h$.

• Space used is $O(n)$
• Methods get, put, and remove take $O(h)$ time (assuming we spend $O(1)$ at each node)
• The height $h$ is $O(n)$ in worst case and $O(\log n)$ in best case.

Binary Search

Binary Search

Binary Search is a method by which we search through a sorted list by halving the list we are looking at for each comparison we take.

def binarySearch(k, A, N):
	min = 1
	max = N
	repeat
		mid = (min + max) div 2
		if k > A[mid]:
			min = mid + 1
		else:
			max = mid - 1
	until (A[mid] == k) or (min > max)

Link to original

Assume that we have an ordered array $A$ of size $N$. For example, $[\mathrm{0..}N]$ of integers and we want to find key $k$. Search for $k=12$.