Editing Red–black tree (section)

== History ==
In 1972, [[Rudolf Bayer]]<ref name="Bayer72">{{cite journal
|last=Bayer |first=Rudolf
|year=1972
|title=Symmetric binary B-Trees: Data structure and maintenance algorithms
|journal=Acta Informatica
|volume=1
|issue=4
|pages=290–306
|doi=10.1007/BF00289509
|s2cid=28836825
}}</ref> invented a data structure that was a special order-4 case of a [[B-tree]]. These trees maintained all [[path (graph theory)|paths]] from root to leaf with the same number of nodes, creating perfectly balanced trees. However, they were not ''binary'' search trees. Bayer called them a "symmetric binary B-tree" in his paper and later they became popular as [[2–3–4 tree]]s or even 2–3 trees.<ref>{{Cite book |last=Drozdek |first=Adam |title=Data Structures and Algorithms in Java |publisher=Sams Publishing |year=2001 |isbn=978-0534376680 |pages=323 |edition=2}}</ref>

In a 1978 paper, "A Dichromatic Framework for Balanced Trees",<ref name="GS78">{{cite conference
 |last1=Guibas |first1=Leonidas J. |author1-link=Leonidas J. Guibas |last2=Sedgewick |first2=Robert |author2-link=Robert Sedgewick (computer scientist)
 |title=A Dichromatic Framework for Balanced Trees
 |book-title=Proceedings of the 19th Annual Symposium on Foundations of Computer Science
 |year=1978
 |pages=8–21
 |doi=10.1109/SFCS.1978.3}}</ref> [[Leonidas J. Guibas]] and [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] derived the red–black tree from the symmetric binary B-tree.<ref>{{Cite web|title=Red Black Trees|url=http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx|website=eternallyconfuzzled.com|access-date=2015-09-02|archive-url=https://web.archive.org/web/20070927222509/http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx|archive-date=2007-09-27|url-status=dead}}</ref> The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at [[Xerox PARC]].<ref name="Sedgewick12">{{cite AV media
 |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist)
 |year=2012
 |title=Red–Black BSTs
 |url=https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/8acpe/red-black-trees
 |publisher=Coursera
 |quote=A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC that was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, Ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that's why we picked the color red to distinguish red links, the types of links, in three nodes. So, that's an answer to the question for people that have been asking.
}}
</ref> Another response from Guibas states that it was because of the red and black pens available to them to draw the trees.<ref>{{Cite web|title=Where does the term "Red/Black Tree" come from?|url=http://programmers.stackexchange.com/a/116621/40127|website=programmers.stackexchange.com|access-date=2015-09-02}}</ref>

In 1993, Arne Andersson introduced the idea of a right leaning tree to simplify insert and delete operations.<ref>{{Cite book
|chapter=Balanced search trees made simple
|series=Lecture Notes in Computer Science
|type=Proceedings
|publisher=Springer-Verlag Berlin Heidelberg
|date=1993-08-11
|isbn=978-3-540-57155-1
|doi=10.1007/3-540-57155-8_236
|pages=60–71 |volume=709
|first=Arne |last=Andersson
|editor-first=Frank |editor-last=Dehne
|editor-first2=Jörg-Rüdiger
|editor-last2=Sack
|editor-first3=Nicola
|editor-last3=Santoro
|editor-first4=Sue
|editor-last4=Whitesides
|chapter-url=https://www.springer.com/la/book/9783540571551
|title=Algorithms and Data Structures
|archive-url=https://web.archive.org/web/20181208183054/https://www.springer.com/la/book/9783540571551
|archive-date=2018-12-08
|citeseerx=10.1.1.118.6192
}} [http://user.it.uu.se/~arnea/ps/simp.pdf Alt URL]</ref>

In 1999, [[Chris Okasaki]] showed how to make the insert operation purely functional. Its balance function needed to take care of only 4 unbalanced cases and one default balanced case.<ref>{{cite journal |title=Red–black trees in a functional setting |journal=Journal of Functional Programming |date=1999-01-01 |doi=10.1017/S0956796899003494 |issn=1469-7653 |pages=471–477 |volume=9 |issue=4 |first=Chris |last=Okasaki |s2cid=20298262 |doi-access=free }}</ref>

The original algorithm used 8 unbalanced cases, but {{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}} reduced that to 6 unbalanced cases.<ref name="Cormen2001"/> Sedgewick showed that the insert operation can be implemented in just 46 lines of [[Java (programming language)|Java]].<ref name="Algs1">{{cite book
|last=Sedgewick
|first=Robert |author-link=Robert Sedgewick (computer scientist)
|title=Algorithms
|publisher=[[Addison-Wesley]]
|edition=1st
|year=1983
|isbn=978-0-201-06672-2
|url-access=registration
|url=https://archive.org/details/algorithms00sedg
}}</ref><ref>{{cite web
|url=http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/RedBlackBST.java.html
|title=RedBlackBST.java
|last1=Sedgewick
|first1=Robert
|author1-link=Robert Sedgewick (computer scientist)
|last2=Wayne
|first2=Kevin
|website=algs4.cs.princeton.edu
|access-date=7 April 2018}}</ref>
In 2008, Sedgewick proposed the [[left-leaning red–black tree]], leveraging Andersson’s idea that simplified the insert and delete operations. Sedgewick originally allowed nodes whose two children are red, making his trees more like 2–3–4 trees, but later this restriction was added, making new trees more like 2–3 trees. Sedgewick implemented the insert algorithm in just 33 lines, significantly shortening his original 46 lines of code.<ref>{{cite web
|title=Left-leaning Red–Black Trees
|last=Sedgewick
|first=Robert
|author1-link=Robert Sedgewick (computer scientist)
|date=2008
|url=https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf}}</ref><ref name="Algs4">{{Cite book
|last1=Sedgewick
|first1=Robert
|author1-link=Robert Sedgewick (computer scientist)
|last2=Wayne
|first2=Kevin
|title=Algorithms
|edition=4th
|isbn=978-0-321-57351-3
|year=2011
|publisher=Addison-Wesley Professional
|url=http://algs4.cs.princeton.edu}}</ref>