Category:Red-black tree
From LiteratePrograms
A red-black tree is a type of self-balancing binary search tree typically used to implement associative arrays. It has O(log n) worst-case time for each operation and is quite efficient in practice. Unfortunately, it's also quite complex to implement, requiring a number of subtle cases for both insertion and deletion.
