2–3 tree

In computer science, a 2–3 tree is a tree data structure, where every node with children (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>Template:Cite book</ref> Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.<ref>Template:Cite book</ref><ref>Template:Cite book, pp.145–147</ref> 2–3 trees were invented by John Hopcroft in 1970.<ref>Template:Cite book</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.

• 2-3-4 tree 2-node.svg

  2 node

• 2-3-4-tree 3-node.svg

  3 node

We say that Template:Mvar is a 2–3 tree if and only if one of the following statements hold:<ref name="A4"/>

• Template:Mvar is empty. In other words, Template:Mvar does not have any nodes.
• Template:Mvar is a 2-node with data element Template:Mvar. If Template:Mvar has left child Template:Mvar and right child Template:Mvar, then
  • Template:Mvar and Template:Mvar are 2–3 trees of the same height;
  • Template:Mvar is greater than each element in Template:Mvar; and
  • Template:Mvar is less than each data element in Template:Mvar.
• Template:Mvar is a 3-node with data elements Template:Mvar and Template:Mvar, where Template:Mvar Template:Math Template:Mvar. If Template:Mvar has left child Template:Mvar, middle child Template:Mvar, and right child Template:Mvar, then
  • Template:Mvar, Template:Mvar, and Template:Mvar are 2–3 trees of equal height;
  • Template:Mvar is greater than each data element in Template:Mvar and less than each data element in Template:Mvar; and
  • Template:Mvar is greater than each data element in Template:Mvar and less than each data element in Template:Mvar.

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.

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

Insertion

Insertion maintains the balanced property of the tree.<ref name="A4">Template:Cite book</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

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>"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 trees, 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