Why can't RB-Tree be a list?
-
01-10-2019 - |
Question
I have a problem with the rb-trees. according to wikipedia, rb-tree needs to 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 analysis.)
- All leaves are black.
- Both children of every red node are black.
- Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
As we know, an rb-tree needs to be balanced and has the height of O(log(n)). But, if we insert an increasing series of numbers (1,2,3,4,5...) and theoretically we will get a tree that will look like a list and will have the height of O(n) with all its nodes black, which doesn't contradict the rb-tree properties mentioned above. So, where am I wrong??
thanks.
Solution
Your example contradicts property number 5, so it's not a valid Red-Black tree.
The tree we have is:
b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))
so to get to the last two leaves (the children of node 5
), we have to visit five black nodes (represented by each b
), to get to the leaf under node 4
we have to visit four black nodes, etc. That means that there are simple paths from the root to some of this descendants containing a different number of black nodes, which invalidates property 5.
OTHER TIPS
A bit further down in the article:
Insertion begins by adding the node much as binary search tree insertion does and by coloring it red.