In computer science, a 2–3 tree is a tree data structure, where every node with children has either two children and one data element or three children and two data elements. A B-tree of order 3 is a 2-3 tree. Nodes on the outside of the tree 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. We say that is a 2–3 treeif and only if one of the following statements hold:
is empty. In other words, does not have any nodes.
is a 3-node with data elements and, where . If has left child, middle child, and right child, then
*,, and are non-empty 2–3 trees of equal height;
* is greater than each data element in and less than or equal to each data element in ; and
* is greater than each data element in and less than or equal to each data element in.
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 be a 2–3 tree and be the data element we want to find. If is empty, then is not in and we're done.
Let be the root of.
Suppose is a leaf.
* If is not in, then is not in. Otherwise, is in. We need no further steps and we're done.
Suppose is a 2-node with left child and right child. Let be the data element in. There are three cases:
* If is equal to, then we've found in and we're done.
* If, then set to, which by definition is a 2–3 tree, and go back to step 2.
* If, then set to and go back to step 2.
Suppose is a 3-node with left child, middle child, and right child. Let and be the two data elements of, where. There are four cases:
* If is equal to or, then is in and we're done.
* If, then set to and go back to step 2.
* If, then set to and go back to step 2.
* If, then set to 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 require 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. 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.
