Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black?
Would the height still be O(logn)? Would you have to have a totally different insertion scheme to maintain the height?
Yes it stays $O(\log n)$. Compared to the proof of the original one, we have no three red consecutive on a path from the root to a leaf. The bound on the blacks stays the same in a path. The length of the path is now at most three times the number of blacks which is at most $3O(\log n)=O(\log n)$.
The insertion changes indeed. Now we have strictly more cases, since we are supposed to regard two levels up in the tree after inserting and rotating. However, I think a case distinction suffices as well similar to the one in the original r-b trees.
