Red-black Tree

From NovaOrdis Knowledge Base
Revision as of 04:49, 13 October 2021 by Ovidiu (talk | contribs) (→‎Overview)
Jump to navigation Jump to search

External

Internal

Overview

Red-black trees had been invented by Bayer (1972) and Guibas, Sedgewick (1978). They are a type of binary search tree that self-balances on insertion and deletion, thus keeping its height to a minimum, which leads to efficient operations. Almost all binary search tree operations have a running time bounded by the tree height, and in this case the tree height stays constant at log n, yielding O(log n) operations.