Growing with the Web



Red-black tree

Published , updated

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.