Binary Search Trees

Definition

A binary search tree is a binary tree in which every node holds a value >= every value in its left subtree and <= every value in its right subtree.

Uses

BSTs are used for sorting and searching.

How They Work

Search

To find value $v$ in tree $t$,

1. If $t$ is empty, return failure.
2. If $v$ is at the root, return success.
3. If $v$ < the value at the root, (recursively) search the left subtree
4. Else (recursively) search the right subtree.

Insertion

To insert value $v$ into tree $t$,

1. If $t$ is empty, make a new node with $v$, then return
2. If $v$ < the value at the root, (recursively) insert into the left subtree
3. Else (recursively) insert into the right subtree.

Deletion

To delete the value V from tree T,

1. Let $d$ be the node to be deleted (the one containing $v$)
2. If $d$ has an empty subtree then point the link to d to the other subtree, then you are done.
3. Otherwise, let $r$ be the rightmost node in $d$'s left subtree. Replace the contents of $d$ with the contents of $r$ then (recursively) delete $r$.

Rotation

Not every BST gives logarithmic search performance:

To deal with the problem of "degenerate" (tall and thin) trees, rotation can help. Rotations usually make a tree shorter.

In general:

There are many different strategies for applying rotations. Generally you'll want to rotate after any insertion or deletion that causes a tree to get "too tall" — AVL trees and Red-Black trees do this. Another approach is to constantly rotate after every insertion, deletion, and lookup to so as to bubble the most likely to be looked up elements near the top. Splay trees do this.

Sorting with BSTs

Look at any BST, for example, this one again:

Mentally, traverse it inorder. That’s a sorted sequence.

The Tree Sort algorithm is:

1. For each node in the input list, add it to a BST
2. Traverse the tree inorder, reading the elements out into the output list.

Space complexity: $\Theta(n)$ extra space. Time complexity: Best case is $\Theta(n \log n)$ if your tree is nearly balanced; worst case is $\Theta(n^2)$ if degenerate.

With an existing BST implementation, this is quite an easy sorting algorithm to implement.

Summary