Why can't RB-Tree be a list?
Posted
by Alex
on Stack Overflow
See other posts from Stack Overflow
or by Alex
Published on 2010-04-26T12:08:38Z
Indexed on
2010/04/26
12:23 UTC
Read the original article
Hit count: 257
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.
© Stack Overflow or respective owner