Editing 2–3 tree (section)

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