CentralNotice Red–black tree From Wikipedia, the free encyclopedia Jump to: navigation , search This article needs additional citations for verification . Please help improve this article by adding citations to reliable sources . Unsourced material may be challenged and removed. (October 2012) Red–black tree Type Tree Invented 1972 Invented by Rudolf Bayer Time complexity in big O notation Average Worst case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n) A red–black tree is a data structure which is a type of self-balancing binary search tree . Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the wor...