Red Black Tree versus B Tree
A red/black tree is more or less equivalent to a 2-3-4 tree, which is just a type of B-tree. The worst-case performance is identical, provided you do a binary search of the B-tree node values. The obvious disadvantage of a B-tree is wasted space, but depending on the language/memory allocator used, you may find that … Read more