patternMinor
Unique keys in a binary search tree
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?
"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:
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.