Red-Black tree
lastmod 2020-09-20created 2020-09-133 edits
A red-black tree is a self-balancing binary search tree, a data structure typically used to implement associative arrays and the like. The original structure was invented by Rudolf Bayer in 1972, who called it the "symmetric binary B-tree"; the name red-black tree first appeared in a 1978 paper by Leo J. Guibas and Robert Sedgewick. The red-black tree is a complex data structure, but it is efficient in practice and has quite good running time even in the worst case: with n elements in the tree, insertion, deletion, and search take O(log n) time complexity.