3
$\begingroup$

This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne.

"Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than the height of the red-black BST, or prove that no such sequence is possible."

I think that in most cases, if not all, the height of a RBT is less than the height of a BST because the RBT ensures balance. However, is it possible for the height of a BST to be less than the height of a RBT? If so, how? Else, how to prove it?

$\endgroup$
  • $\begingroup$ have you cross posted? I would suggest not to do so, it is against SE policy. Also, since I do not have answer yet, what have you tried? Maybe generating some nodes would produce counterexample or encourage to take proof? $\endgroup$ – Evil Feb 8 '16 at 1:28
  • 1
    $\begingroup$ What would happen if you try this: First construct a sequence that leads to some rotations in the red-black tree. Now your regular BST and red-black BST are no longer "synchronised". Then continue with a sequence that perfectly fills in all gaps in the regular BST, so that it becomes perfectly balanced ($2^k-1$ nodes, depth $k$). Is the red-black tree also perfectly balanced at this point? In particular, can you engineer the sequence of insertions so that this does not happen? $\endgroup$ – Jukka Suomela Feb 8 '16 at 13:05
2
$\begingroup$

The fact that a red-black tree is balanced just means that if it contains $n$ nodes then its depth is $O(\log n)$. There is no requirement for the depth to be optimal (i.e. $\lceil \log_2 (n+1) \rceil-1$), only for it to be optimal up to constants. Therefore it is definitely possible for a red-black tree to be deeper than some other binary search tree.

The advantage of balanced trees is that they are guaranteed to be balanced even after operations on the data structure. Since the running time of operations is usually linear in the depth, it is enough for the depth to be $O(\log n)$ rather than the optimal $\approx \log_2 n$.

$\endgroup$
  • 1
    $\begingroup$ I thought the OP asked about the very same sequence added to BST and RBT at the same time, which is a bit different, because for example AVL is 1.44logn while RBT is 2logn, but it was explicit about BST (not self balancing) a this is how I understood the question. $\endgroup$ – Evil Feb 7 '16 at 20:58
  • $\begingroup$ Right, so you need to engineer a sequence which causes this to happen. But it's not ruled out by red-black trees being self-balancing. $\endgroup$ – Yuval Filmus Feb 7 '16 at 22:05
1
$\begingroup$

It is possible.

One example is the sequence of keys: 5 1 10 15 6 0

I'm considering the left-leaning red-black BSTs since that is the data structure used on Sedgewick and Wayne's book.

Sequence of insertions on a BST:

Insert  5     5

        1     5
            1

       10     5
            1   10

       15     5
            1   10
                 15

        6     5
            1    10
                6  15

        0     5
            1    10
           0    6  15

Height: 2

Sequence of insertions on a Red-black BST:

Insert  5       (B)5

        1        (B)5
               (R)1

       10         (B)5
               (R)1  (R)10

       10         (R)5
               (B)1  (B)10

       10         (B)5
               (B)1  (B)10

       15         (B)5
              (B)1  (B)10
                      (R)15

       15         (B)5
              (B)1    (B)15
                    (R)10

       6           (B)5
              (B)1      (B)15
                      (R)10
                    (R)6

       6            (B)5
              (B)1      (B)10
                      (R)6  (R)15

       6            (B)5
              (B)1      (R)10
                      (B)6  (B)15

       6           (B)10
               (R)5      (B)15
           (B)1   (B)6

       0           (B)10
               (R)5      (B)15
           (B)1   (B)6
         (R)0

Height: 3

$\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.