Red-black Tree

From NovaOrdis Knowledge Base
Revision as of 04:48, 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-balance on insertion and deletion, thus keeping their height to a minimum, which leads to efficient operations (almost all operations on binary trees have running time bounded by the tree height, and in this case the tree height stays constant at log n).