Have Geek Brain

Why can't RB-Tree be a list?

I have a problem with rb trees. according to wikipedia the rb-tree should follow the following:

  • A node is either red or black.
  • The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on the analysis.)
  • All leaves are black.
  • Both children of each red node are black.
  • Every simple path from a given node to any of its children leaves the same number of black nodes.

As you know, an rb-tree should be balanced and have a height of O (log (n)). But if we insert an ascending series of numbers (1,2,3,4,5 ...) and theoretically get a tree that looks like a list and has height O (n) with all its nodes black, which does not contradict the above rb-tree properties. So where am I going wrong?

thanks.

+2


a source to share


2 answers


Your example conflicts with property number 5, so it is not a valid Red-Black tree.

We have a tree:



b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

so to get to the last two leaves (children of a node 5

) we have to visit five black nodes (represented by each b

), to get to a leaf under a node 4

we have to visit four black nodes, etc. This means there are simple paths from the root to some of these descendants containing a different number of black nodes, which invalidates property 5.

+3


a source


A little further in the article :



Insertion starts by adding a node as the insertion of the binary search tree does and colors it red .

+3


a source






More articles:


All Articles