Why can't RB-Tree be a list?
- by Alex
Hey everyone.
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.
