View source for 2–3 tree

{{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.

==Definitions==
We say that an internal node is a '''2-node''' if it has ''one'' data element and ''two'' children.

We say that an internal node is a '''3-node''' if it has ''two'' data elements and ''three'' children.

A '''4-node''', with three data elements, may be temporarily created during manipulation of the tree but is never persistently stored in the tree.

<gallery heights="95px">
Image:2-3-4 tree 2-node.svg|2 node
Image:2-3-4-tree 3-node.svg|3 node
</gallery>

We say that {{mvar|T}} is a '''2–3 tree''' if and only if one of the following statements hold:<ref name="A4"/>

* {{mvar|T}} is empty. In other words, {{mvar|T}} does not have any nodes.
* {{mvar|T}} is a 2-node with data element {{mvar|a}}. If {{mvar|T}} has left child {{mvar|p}} and right child {{mvar|q}}, then 
** {{mvar|p}} and {{mvar|q}} are 2–3 trees of the same [[Tree (data structure)#Terminology|height]];
** {{mvar|a}} is greater than each element in {{mvar|p}}; and
** {{mvar|a}} is less than each data element in {{mvar|q}}.
* {{mvar|T}} is a 3-node with data elements {{mvar|a}} and {{mvar|b}}, where {{mvar|a}} {{Math| <}} {{mvar|b}}. If {{mvar|T}} has left child {{mvar|p}}, middle child {{mvar|q}}, and right child {{mvar|r}}, then
** {{mvar|p}}, {{mvar|q}}, and {{mvar|r}} are 2–3 trees of equal height;
** {{mvar|a}} is greater than each data element in {{mvar|p}} and less than each data element in {{mvar|q}}; and
** {{mvar|b}} is greater than each data element in {{mvar|q}} and less than each data element in {{mvar|r}}.

==Properties==
* Every internal node is a 2-node or a 3-node.
* All leaves are at the same level.
* All data is kept in sorted order.

==Operations==

===Searching===
Searching for an item in a 2–3 tree is similar to searching for an item in a [[binary search tree]]. Since the data elements in each node are ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.

# Let {{mvar|T}} be a 2–3 tree and {{mvar|d}} be the data element we want to find. If {{mvar|T}} is empty, then {{mvar|d}} is not in {{mvar|T}} and we're done.
# Let {{mvar|t}} be the root of {{mvar|T}}.
# Suppose {{mvar|t}} is a leaf.
#* If {{mvar|d}} is not in {{mvar|t}}, then {{mvar|d}} is not in {{mvar|T}}. Otherwise, {{mvar|d}} is in {{mvar|T}}. We need no further steps and we're done.
# Suppose {{mvar|t}} is a 2-node with left child {{mvar|p}} and right child {{mvar|q}}. Let {{mvar|a}} be the data element in {{mvar|t}}. There are three cases:
#* If {{mvar|d}} is equal to {{mvar|a}}, then we've found {{mvar|d}} in {{mvar|T}} and we're done. 
#* If <math>d < a</math>, then set {{mvar|T}} to {{mvar|p}}, which by definition is a 2–3 tree, and go back to step 2.
#* If <math>d > a</math>, then set {{mvar|T}} to {{mvar|q}} and go back to step 2.
# Suppose {{mvar|t}} is a 3-node with left child {{mvar|p}}, middle child {{mvar|q}}, and right child {{mvar|r}}. Let {{mvar|a}} and {{mvar|b}} be the two data elements of {{mvar|t}}, where <math>a < b</math>. There are four cases:
#* If {{mvar|d}} is equal to {{mvar|a}} or {{mvar|b}}, then {{mvar|d}} is in {{mvar|T}} and we're done.
#* If <math>d < a</math>, then set {{mvar|T}} to {{mvar|p}} and go back to step 2.
#* If <math>a < d < b</math>, then set {{mvar|T}} to {{mvar|q}} and go back to step 2.
#* If <math>d > b</math>, then set {{mvar|T}} to {{mvar|r}} and go back to step 2.

===Insertion===
Insertion maintains the balanced property of the tree.<ref name="A4">{{cite book|section=3.3 |title=Algorithms|edition=4|first1=Robert |last1=Sedgewick |first2=Kevin |last2=Wayne |date=2011 |publisher=Addison Wesley |isbn=978-0-321-57351-3}}</ref>

To insert into a 2-node, the new key is added to the 2-node in the appropriate order.

To insert into a 3-node, more work may be required depending on the location of the 3-node. If the tree consists only of a 3-node, the node is split into three 2-nodes with the appropriate keys and children.

[[File:2-3 insertion.svg|framed|none|Insertion of a number in a 2–3 tree for 3 possible cases]]

If the target node is a 3-node whose parent is a 2-node, the key is inserted into the 3-node to create a temporary 4-node. In the illustration, the key 10 is inserted into the 2-node with 6 and 9. The middle key is 9, and is promoted to the parent 2-node. This leaves a 3-node of 6 and 10, which is split to be two 2-nodes held as children of the parent 3-node.

If the target node is a 3-node and the parent is a 3-node, a temporary 4-node is created then split as above. This process continues up the tree to the root. If the root must be split, then the process of a single 3-node is followed: a temporary 4-node root is split into three 2-nodes, one of which is considered to be the root. This operation grows the height of the tree by one.

===Deletion===
Deleting a key from a non-leaf node can be done by replacing it by its immediate predecessor or successor, and then deleting the predecessor or successor from a leaf node.  Deleting a key from a leaf node is easy if the leaf is a 3-node.  Otherwise, it may require creating a temporary 1-node which may be absorbed by reorganizing the tree, or it may repeatedly travel upwards before it can be absorbed, as a temporary 4-node may in the case of insertion.  Alternatively, it's possible to use an algorithm which is both top-down and bottom-up, creating temporary 4-nodes on the way down that are then destroyed as you travel back up.  Deletion methods are explained in more detail in the references.<ref name="A4" /><ref>[https://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf "2-3 Trees"], Lyn Turbak, handout #26, course notes, CS230 Data Structures, Wellesley College, December 2, 2004.  Accessed Mar. 11, 2024.</ref> 
===Parallel operations===
Since 2–3 trees are similar in structure to [[red–black tree]]s, [[Red–black_tree#Parallel_algorithms|parallel algorithms for red–black trees]] can be applied to 2–3 trees as well.

==See also==
* [[2–3–4 tree]]
* [[2–3 heap]]
* [[AA tree]]
* [[B-tree]]
* [[(a,b)-tree]]
* [[Finger tree]]
{{clear}}

==References==
{{Reflist}}

{{CS-Trees}}
{{Data structures}}

{{DEFAULTSORT:2-3 tree}}
[[Category:B-tree]]
[[Category:Amortized data structures]]