Editing Red–black tree (section)

{{Short description|Self-balancing binary search tree data structure}}

{{Infobox data structure-amortized
| name = Red–black tree
| type = [[Tree (data structure)|Tree]]
| invented_by = [[Leonidas J. Guibas]] and [[Robert Sedgewick (computer scientist)|Robert Sedgewick]]
| invented_year = 1978
| space_avg = <math>O(n)</math>
| search_avg = <math>O(\log n)</math>
| search_worst = <math>O(\log n)</math>
| insert_avg = <math>O(\log n)</math>
| insert_worst = <math>O(\log n)</math>
| delete_avg = <math>O(\log n)</math>
| delete_worst = <math>O(\log n)</math>
}}
[[File:Red-black tree example with sockets.svg|thumb|right|275px|Example of a red-black tree]]

In [[computer science]], a '''red–black tree''' is a [[self-balancing binary search tree]] [[data structure]] noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.<ref name="Cormen2001">{{Anchor|Cormen}}{{Cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |year=2001 |title=Introduction to Algorithms |edition=2nd |isbn=978-0-262-03293-3 |chapter=Red&ndash;Black Trees |pages=[https://archive.org/details/introductiontoal00corm_691/page/n735 273]–301 |title-link=Introduction to Algorithms |publisher=MIT Press}}</ref>

When the tree is modified, the new tree is rearranged and "repainted" to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.

The (re-)balancing is not perfect, but guarantees searching in <math>O(\log n)</math> time, where <math>n</math> is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in <math>O(\log n)</math> time.<ref name="wiscurl2">{{cite web |last=Paton |first=James |title=Red–Black Trees |url=http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/}}</ref><ref>{{cite web |url=https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html |title=Red–Black Trees |first=John |last=Morris |date=1998 |work=Data Structures and Algorithms}}</ref>

Tracking the color of each node requires only one bit of information per node because there are only two colors (due to memory alignment present in some programming languages, the real memory consumption may differ). The tree does not contain any other data specific to it being a red–black tree, so its [[memory footprint]] is almost identical to that of a classic (uncolored) [[binary search tree]]. In some cases, the added bit of information can be stored at no added memory cost.

{{TOC limit|4}}