0
$\begingroup$

I'd like to ask what is minimal RBT with black depth 3. Is this following RBT ? Values are not important. And that tree can't have depth 2 or 1.

$\endgroup$
0
$\begingroup$

According to Wikipedia, a red-black tree should be "roughly balanced". The rule is "that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf". In your example, every node has a leaf. The root has a leaf, so the path in between has length $1$. Also, the furthest node has a leaf, with the path from the root having length $3$. Thus, that tree does not meet the requirements of a red-black tree.

You can obtain a red-black tree by adding another node to the root. Since your tree was minimal as a binary tree of depth $3$, the tree you obtain must be minimal as a red-black tree of depth $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.