1
$\begingroup$

How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).

$\endgroup$
1
$\begingroup$

Actually any BST can be transformed into balanced BST using $\mathcal{O}(n)$ rotations.

High level explanation: We convert given BST to right going chain(see fig-1 below). Then we convert that chain to balanced BST.

First convert given BST into right-going chain. Which can be accomplished using $n-1$ right rotations as follow.

Consider initial-right-chain $C$ of $root$ and all node that can be reachable from $root$ by following only right pointers.

Now, note that for any node $N$ in $C$ left child of node $N$ can be added into $C$ by right-rotating $N$. In doing that we don't loss any node from $C$.

So, by at most $n-1$ right rotation all node will be in $C$ because root will always be in $C$ from start.

Now, consider sequence of rotations $R: r_1, r_2, ..., r_m$ required to convert tree $T_1$ to right-going chain.

Now, consider sequence of rotations $S: s_1, s_2, ..., s_k$ required to convert balanced BST (containing same number of node as $T_1$) to right_going chain.

Then apply $r_1, r_2, ..., r_m, s_k', s_{k-1}', ..., s_1'$ to $T_1$. Here $s_i'$ denotes inverse operation of $s_i$.

Which will transform $T_1$ to balanced BST using at most $2n-2$ rotations.


   1
    \
     2
      \
       3

 figure - 1

Ref: CLRS 3e exercise 13.2.4

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.