I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees):


And I do know that the correct one is number three from the left. However, I can't figure out why it is the correct one.

I know that the first one from the left is wrong, because it contains a red node with a red child which is not allowed. Regarding number two from the left, I guess it is wrong because of it's balance (height?).

I have read something about that a red-black tree must have a height equal to log2(n) where n is the number of nodes, but when I calculate this I still can't figure out why number three is the correct answer.

Can someone help me? Thank you!

  • $\begingroup$ Have you heard of cs.stackexchange.com? Not sure if it is on-topic there though. $\endgroup$ – Aryabhata Jun 2 '16 at 20:09
  • $\begingroup$ Of course I have heard of cs.stackexchange.com. But my experience is that people at math.stackexchange.com are really good at topics including math (algorithms etc.) $\endgroup$ – Daniel S Jun 2 '16 at 20:11

Your Answer

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

Browse other questions tagged or ask your own question.