Editing 2–3 tree (section)

{{Short description|Data structure in computer science}}
{{Infobox data structure-amortized
| name = 2–3 tree
| type = tree
| invented_by = [[John Hopcroft]]
| invented_year = 1970
| 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>
}}

In [[computer science]], a '''2–3 tree''' is a [[tree data structure]], where every [[Node (computer science)|node]] with children ([[Tree (data structure)#Internal nodes|internal node]]) has either two children (2-node) and one [[data element]] or three children (3-node) and two data elements. A 2–3 tree is a [[B-tree]] of order 3.<ref>{{cite book| title=The Art of Computer Programming |volume=3| chapter=6.2.4 |quote=The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. |first1=Donald M |last1=Knuth |edition=2 |isbn=978-0-201-89685-5 |publisher=Addison Wesley|year=1998}}</ref> Nodes on the outside of the tree ([[leaf node]]s) have no children and one or two data elements.<ref>{{Cite book
  | title = Estructura de Datos y Algoritmos
  |author=R. Hernández |author2=J. C. Lázaro |author3=R. Dormido |author4=S. Ros
  | publisher = Prentice Hall
  | year = 2001
  | isbn = 84-205-2980-X
}}</ref><ref>{{cite book
|first1=Alfred V.
|last1=Aho
|first2=John E.
|last2=Hopcroft
|first3=Jeffrey D.
|last3=Ullman
|title=The Design and Analysis of Computer Algorithms
|url=https://archive.org/details/designanalysisof00ahoarich
|url-access=registration
|publisher=Addison-Wesley
|year=1974|isbn=978-0-201-00029-0
}}, pp.145–147</ref> 2–3 trees were invented by [[John Hopcroft]] in 1970.<ref>{{Cite book|title = Introduction to Algorithms|url = https://archive.org/details/introductiontoal00corm_805|url-access = limited|last = Cormen|first = Thomas|publisher = The MIT Press|year = 2009|isbn = 978-0-262-03384-8|location = London|pages = [https://archive.org/details/introductiontoal00corm_805/page/n524 504]}}</ref>

2–3 trees are required to be balanced, meaning that each leaf is at the same level. It follows that each right, center, and left subtree of a node contains the same or close to the same amount of data.