Red-black Tree: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 9: Line 9:


=Overview=
=Overview=
Red-black trees were 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).
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).
 
* Self-balancing.
* O(log n) operations.

Revision as of 04:48, 13 October 2021

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).