2–3 tree

2-3 tree
2-3 tree
Type	tree
Invented	1970
Invented by	John Hopcroft
Operation
Time complexity in big O notation
Operation	Average
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Space complexity
Space	O(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. A 2-3 tree is a B-tree of order 3.^[1] Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements.^[2]^[3] 2−3 trees were invented by John Hopcroft in 1970.^[4]

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 $T$ is a 2–3 tree if and only if one of the following statements hold:^[5]

$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 p and right child q, then
- $p$ and $q$ are 2–3 trees of the same height;
- $a$ is greater than each element in $p$ ; and
- $a$ is less than or equal to each data element in $q$ .
T is a 3-node with data elements a and b, where a < b. If T has left child p, middle child q, and right child r, then
- $p$ , $q$ , and $r$ are 2–3 trees of equal height;
- $a$ is greater than each data element in $p$ and less than or equal to each data element in $q$ ; and
- $b$ is greater than each data element in $q$ 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.

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.
Let $t$ be the root of $T$ .
Suppose t is a leaf.
- If $d$ is not in $t$ , then $d$ is not in $T$ . Otherwise, $d$ is in $T$ . We need no further steps and we're done.
Suppose t is a 2-node with left child p and right child q. Let a be the data element in t. There are three cases:
- If $d$ is equal to $a$ , then we've found $d$ in $T$ and we're done.
- If $d<a$ , then set $T$ to $p$ , which by definition is a 2–3 tree, and go back to step 2.
- If $d>a$ , then set $T$ to $q$ and go back to step 2.
Suppose t is a 3-node with left child p, middle child q, and right child r. Let a and b be the two data elements of t, where $a<b$ $a<b$ . There are four cases:
- If $d$ is equal to $a$ or $b$ , then $d$ is in $T$ and we're done.
- If $d<a$ , then set $T$ to $p$ and go back to step 2.
- If $a<d<b$ , then set $T$ to $q$ and go back to step 2.
- If $d>b$ , then set $T$ to $r$ and go back to step 2.

Insertion

Insertion maintains the balanced property of the tree.^[5]

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.

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.

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.

References

^ Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855. The 2-3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.
^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley., p.145-147
^ Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. pp. 504. ISBN 978-0262033848.
^ ^a ^b Sedgewick, Robert; Wayne, Kevin. "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 9780321573513.

External links

2–3 Tree In-depth description

[1] Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855. The 2-3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.

[2] Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X.{{cite book}}: CS1 maint: multiple names: authors list (link)

[3] Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley., p.145-147

[4] Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. pp. 504. ISBN 978-0262033848.

[A4-5] Sedgewick, Robert; Wayne, Kevin. "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 9780321573513.

[1]

[2]

[3]

[4]

[5]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures