# 2–3 tree

2-3 tree
Typetree
Invented1970
Invented byJohn Hopcroft
Time complexity in big O notation
Algorithm Space Average Worst case O(n) O(n) O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)

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-nodes) and two data elements. According to Knuth, "a B-tree of order 3 is a 2-3 tree." Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.[1][2] 2−3 trees were invented by John Hopcroft in 1970.[3]

2–3 trees are balanced, meaning that each right, center, and left subtree 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.

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

• T is empty. In other words, T does not have any nodes.
• T is a 2-node with data element a. If T has left child L and right child R, then
• L and R are non-empty 2–3 trees of the same height;
• a is greater than each element in L; and
• a is less than or equal to each data element in R.
• T is a 3-node with data elements a and b, where a < b. If T has left child L, middle child M, and right child R, then
• L, M, and R are non-empty 2–3 trees of equal height;
• a is greater than each data element in L and less than or equal to each data element in M; and
• b is greater than each data element in M and less than or equal to each data element in 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.

1. Let T be a 2–3 tree and d be the data element we want to find. If T is empty, then d is not in T and we're done.
2. Let r be the root of T.
3. Suppose r is a leaf. If d is not in r, then d is not in T. Otherwise, d is in T. In particular, d can be found at a leaf node. We need no further steps and we're done.
4. Suppose r is a 2-node with left child L and right child R. Let e be the data element in r. There are three cases:
• If d is equal to e, then we've found d in T and we're done.
• If ${\displaystyle d, then set T to L, which by definition is a 2–3 tree, and go back to step 2.
• If ${\displaystyle d>e}$, then set T to R and go back to step 2.
5. Suppose r is a 3-node with left child L, middle child M, and right child R. Let a and b be the two data elements of r, where ${\displaystyle a. There are four cases:
• If d is equal to a or b, then d is in T and we're done.
• If ${\displaystyle d, then set T to L and go back to step 2.
• If ${\displaystyle a, then set T to M and go back to step 2.
• If ${\displaystyle d>b}$, then set T to R and go back to step 2.

### Insertion

Insertion works by searching for the proper location of the key and adding it there. If the node becomes a 4-node then the node is split into two 2-nodes and the middle key is moved up to the parent. The diagram illustrates the process.

Insertion of a number in a 2-3 tree for the 3 possible cases.