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. Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements. 2–3 trees were invented by John Hopcroft in 1970.

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 node
• 
  3 node

We say that Template:Mvar is a 2–3 tree if and only if one of the following statements hold:

• 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 $d<a$, then set Template:Mvar to Template:Mvar, which by definition is a 2–3 tree, and go back to step 2.
   • If $d>a$, 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 $a<b$. 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 $d<a$, then set Template:Mvar to Template:Mvar and go back to step 2.
   • If $a<d<b$, then set Template:Mvar to Template:Mvar and go back to step 2.
   • If $d>b$, then set Template:Mvar to Template:Mvar and go back to step 2.

Insertion

Insertion maintains the balanced property of the tree.

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.

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.

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