HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Unique keys in a binary search tree

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
uniquesearchkeysbinarytree

Problem

I'm studying for my finals and I can across this statement.

"For a fixed set of (unique) keys, any binary search tree containing those keys can
be converted to any other BST on the same set of keys via a sequence of left- and/or right-
rotations."

I'm interested in a proof. Does anyone know any references?

Solution

Here's a short method of transforming a BST $T_1$ into any other BST $T_2$ on the same set of keys, taken from notes written by Doug Hogan at Penn State:


Define the right spine of a BST as the root and all descendants of
the root that are reachable by following only right pointers from the
root. A right-linear chain is a BST that has all n nodes in the
right spine.


Let $T'$ be the (unique) right-linear chain of $n$ keys. Let $r = (r_1, r_2, ..., r_k)$
be a sequence of right rotations that transforms $T_1$
into $T'$, and let $r' = (r'_1, r'_2, ...,r'_{k'})$ be a sequence of
right rotations that transforms $T_2$ to $T'$. We know there exist
sequences $r$ and $r'$ with $k, k' \leq n-1$, since a right rotation
adds exactly one node to the right spine. For each right rotation
$r'_i$ let $l'_i$ be the corresponding left rotation. Then, the
sequence $(r_1, r_2, ..., r_k,l'_{k'},l'_{k'-1}, ..., l'_2, l'_1)$
transforms $T_1$ to $T_2$ in at most $2n-2$ rotations.

...and here's another explanation, which gives a nice recursive algorithm.

Google search terms: binary search tree transform rotation proof.

Context

StackExchange Computer Science Q#23481, answer score: 2

Revisions (0)

No revisions yet.