Editing Red–black tree (section)

== Properties ==
In addition to the requirements imposed on a [[binary search tree]] the following must be satisfied by a {{nowrap|red–black tree:<ref name="Cormen2009">{{cite book
|last1=Cormen |first1=Thomas |author-link1=Thomas H. Cormen
|last2=Leiserson |first2=Charles |author-link2=Charles E. Leiserson
|first3=Ronald |last3=Rivest |author-link3=Ron Rivest
|first4=Clifford |last4=Stein |author-link4=Clifford Stein
|chapter=13. Red–Black Trees
|title=Introduction to Algorithms |title-link=Introduction to Algorithms
|edition=4th |year=2022 |publisher=[[MIT Press]] |isbn=9780262046305
|pages=[https://archive.org/details/introductiontoal00corm_805/page/n328 331]–332
}}</ref>}}

# Every node is either red or black.
# {{Anchor|consideredBlack}}All null nodes are considered black.
# {{anchor|req3}}A red node does not have a red child.
# {{anchor|req4}}Every [[path (graph theory)|path]] from a given node to any of its leaf nodes goes through the same number of black nodes.
#{{anchor|con5}}(Conclusion) If a node '''N''' has exactly one child, the child must be red. If the child were black, its leaves would sit at a different black depth than '''N''''s null node (which is considered black by rule 2), violating [[#req4|requirement 4]].

Some authors, e.g. Cormen & al.,<ref name="Cormen2009"/> claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders<ref name="Mehlhorn2008"/> or Sedgewick & Wayne.<ref name="Algs4"/>{{rp|432–447}} Since the root can always be changed from red to black, this rule has little effect on analysis.
This article also omits it, because it slightly disturbs the recursive algorithms and proofs.

As an example, every [[Binary tree#Types of binary trees|perfect binary tree]] that consists only of black nodes is a red–black tree.

The read-only operations, such as search or tree traversal, do not affect any of the requirements. In contrast, the modifying operations [[#Insertion|insert]] and [[#Removal: simple cases|delete]] easily maintain requirements 1 and 2, but with respect to the other requirements some extra effort must be made, to avoid introducing a violation of requirement 3, called a {{anchor|ViolR}}'''red-violation''', or of requirement 4, called a {{anchor|ViolB}}'''black-violation'''.

The requirements enforce a critical property of red–black trees: ''the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf''. The result is that the tree is [[Height-balanced binary search tree|height-balanced]]. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height <math>h</math> of the tree, this upper bound on the height allows red–black trees to be efficient in the worst case, namely [[Logarithmic growth|logarithmic]] in the number <math>n</math> of entries, i.e. {{nowrap|<math>h \in O(\log n)</math>}} (a property which is shared by all self-balancing trees, e.g., [[AVL tree]] or [[B-tree]], but not the ordinary [[binary search tree]]s). For a mathematical proof see section [[#Proof of bounds|Proof of bounds]].

Red–black trees, like all [[binary search tree]]s, allow quite efficient sequential access (e.g. [[in-order traversal]], that is: in the order Left–Root–Right) of their elements. But they support also asymptotically optimal [[Random access|direct access]] via a traversal from root to leaf, resulting in <math>O(\log n)</math> search time.