Editing Red–black tree (section)

== Applications and related data structures ==
Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as [[real-time computing|real-time application]]s, but it makes them valuable building blocks in other data structures that provide worst-case guarantees. For example, many data structures used in [[computational geometry]] are based on red–black trees, and the [[Completely Fair Scheduler]] and [[epoll]] system call of the [[Linux kernel]] use red–black trees.<ref>{{cite web |title=IBM Developer |url=https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ |website=developer.ibm.com |access-date=25 May 2024}}</ref><ref>{{Cite web |url=https://idndx.com/2014/09/01/the-implementation-of-epoll-1/
|title=The Implementation of epoll (1)
|work=Datong's Random Thoughts
|date=September 2014}}</ref>
The [[AVL tree]] is another structure supporting <math>O(\log n)</math> search, insertion, and removal. AVL trees can be colored red–black, and thus are a subset of red-black trees. The worst-case height of AVL is 0.720 times the worst-case height of red-black trees, so AVL trees are more rigidly balanced. The performance measurements of Ben Pfaff with realistic test cases in 79 runs find AVL to RB ratios between 0.677 and 1.077, median at 0.947, and geometric mean 0.910.<ref>[[#Pfaff b|Pfaff 2004]]</ref> The performance of [[WAVL tree]]s lie in between AVL trees and red-black trees.{{cn|date=April 2024}}

Red–black trees are also particularly valuable in [[functional programming]], where they are one of the most common [[persistent data structure]]s, used to construct [[associative array]]s and [[set (computer science)|set]]s that can retain previous versions after mutations. The persistent version of red–black trees requires <math>O(\log n)</math> space for each insertion or deletion, in addition to time.

For every [[2–3–4 tree]], there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2–3–4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2–3–4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2–3–4 trees just before red–black trees, even though 2–3–4 trees are not often used in practice.

In 2008, [[Robert Sedgewick (computer scientist)|Sedgewick]] introduced a simpler version of the red–black tree called the [[left-leaning red–black tree]]<ref name="LLRB">{{cite web|url=http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf|title=Robert Sedgewick|website=Cs.princeton.edu|date=4 June 2020 |access-date=26 March 2022}}</ref> by eliminating a previously unspecified degree of freedom in the implementation. The LLRB maintains an additional invariant that all red links must lean left except during inserts and deletes. Red–black trees can be made isometric to either [[2–3 tree]]s,<ref>{{cite web|url=http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf|title=Balanced Trees|website=Cs.princeton.edu|access-date=26 March 2022}}</ref> or 2–3–4 trees,<ref name="LLRB"/> for any sequence of operations. The 2–3–4 tree isometry was described in 1978 by Sedgewick.<ref name="GS78"/> With 2–3–4 trees, the isometry is resolved by a "color flip," corresponding to a split, in which the red color of two children nodes leaves the children and moves to the parent node.

The original description of the [[tango tree]], a type of tree optimised for fast searches, specifically uses red–black trees as part of its data structure.<ref name="DHIP">{{cite journal 
|doi=10.1137/S0097539705447347
|url=http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf 
|title=Dynamic Optimality—Almost
|journal=SIAM Journal on Computing
|volume=37
|issue=1 
|pages=240|year=2007
|last1=Demaine 
|first1=E. D. 
|last2=Harmon |first2=D. 
|last3=Iacono |first3=J. 
|last4=Pătraşcu 
|first4=M. 
|s2cid=1480961}}</ref>

As of [[Java (programming language)|Java]] 8, the [[Hashtable|HashMap]] has been modified such that instead of using a [[LinkedList]] to store different elements with [[Hash function#Uniformity|colliding]] [[hashcode]]s, a red–black tree is used. This results in the improvement of time complexity of searching such an element from <math>O(m)</math> to <math>O(\log m)</math> where <math>m</math> is the number of elements with colliding hashes.<ref>{{cite web |url=http://coding-geek.com/how-does-a-hashmap-work-in-java/#JAVA_8_improvements |title= How does a HashMap work in JAVA |publisher=coding-geek.com}}</ref>