0
$\begingroup$

Exam question:

Draw the Red Black Tree that results from inserting the following values in the given order:

[10, 20, 30, 4, 5, 50]

Draw the red connections with a dotted line and the black ones with a continuous line.

What I understand about Red Black Trees:

  1. Every node is either red or black.

  2. The root and leaves are black.

  3. If a node is red, then its parent is black.

  4. For every leaf, the path has the same number of black nodes (the tree is balanced).

My profs solution:

enter image description here

Solution from this website

enter image description here

I'm very confused as to how to solve this, my prof's PPTs say that all the red connections are to the left, I've found places that say that all reds are to the right, others where it's irrelevant. Can someone explain how to solve this?

$\endgroup$
4
  • $\begingroup$ You have two trees and in none of them the leaves are black. What do you mean with "my prof's solution"? Surely they didn't give you an all-red tree as an example of a red black tree? $\endgroup$
    – Pål GD
    Feb 7 at 19:04
  • $\begingroup$ @PålGD the continuous lines = black (child), the dotted = red. I explained as much on the question. Leaves = null values at the end, implicit here. $\endgroup$ Feb 7 at 19:07
  • $\begingroup$ You must have learned an algorithm for inserting a value into a red-black tree. All you have to do is follow it. No thinking required – even a mindless computer can do it (literally). $\endgroup$ Feb 7 at 19:28
  • 2
    $\begingroup$ The algorithm performed by the website is consistent with the version of the algorithm I have learned (with rotations and flag-flips). There is a more restricted form of trees where indeed single red children go to the left (wikipedia suggest "left-leaning red–black tree") and perhaps your professor uses that implementation. $\endgroup$ Feb 8 at 1:45

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.