0

I followed the rules of the insert operation listed at GeeksforGeeks. I used them to solve example 2 here. My solution below is different than the one in the same document.

                32 (black)
           /                \
         21 (black)          64 (black)
        /                     \
      15 (red)                 75 (red)

My questions are:

Are there many sets of rules for rotations and recoloring? Should the red black tree be unique for a sequence of insert operations for a set of numbers, using different rules? Is the tree in my solution considered "balanced"?

P.s. to clarify, what is different is that when I insert a node to a red node with a black grandparent that has a red sibling, I should recolor the parent and the sibling black, and recolor the grandparent red. If that creates two reds, then the recoloring is propagated until it reaches the root, which should be colored black.

Ahmad Abdelzaher
  • 19

1 Answers1

0

Red-black trees are characterized by a set of invariants. As long as those invariants are satisfied, you have a legal red-black tree. There is no uniqueness property. In fact, the second solution shown in the link you posted is exactly your solution, which is indeed balanced.

Some implementations only produce trees where red nodes cannot be right children of their parents. That produces yet another red-black tree for your example that differs from yours in that a black 75 is the right child of the root and has a red 64 as left child.

Fabio Somenzi
  • 7,676
  • Thank you. My teacher argued that such a tree is not balanced. What defines a balanced tree? Afaik the height has to be logarithmic in the number of nodes. Does the base of the logarithm matter? What if I have 16 nodes and I constructed a tree in such a way that it will be a one inverted v like the one above. Would that still be balanced? – Ahmad Abdelzaher May 29 '17 at 04:07
  • The relevant notion of balancing for red-black trees is perfect black balance: every path from the root to NULL has the same number of black nodes. This is true in your tree. It wouldn't be true if 15 or 75 (or both) were black instead of red. For example, the left-right path reaches NULL after going through two black nodes. Hence left-left-left and left-left-right paths can only go through two black nodes. Perfect black balance guarantees approximate balancing of the tree--seen as a binary search tree--which in turn leads to logarithmic time bounds. – Fabio Somenzi May 29 '17 at 04:27
  • Thanks, but what about the base of the logarithm? Does it matter? – Ahmad Abdelzaher Jun 01 '17 at 08:37
  • No, the base of the logarithm doesn't matter because logarithms in different bases are related by a constant factor, which the big-Oh notation makes irrelevant: $\log_b n = \log_b a \cdot \log_a n$. – Fabio Somenzi Jun 01 '17 at 14:18