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

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.

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 $r$ be the root of $T$ .
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.
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 $d<e$ , then set $T$ to $L$ , which by definition is a 2–3 tree, and go back to step 2.
- If $d>e$ , then set $T$ to $R$ and go back to step 2.
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 $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 $L$ and go back to step 2.
- If $a<d<b$ , then set $T$ to $M$ and go back to step 2.
- If $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.

References

^ 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. p. 504. ISBN 978-0262033848.

External links

2–3 Tree Visualization (click one "Init" button)
2–3 Tree In-depth description
2–3 Tree in F#

[1] 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)

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

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

[1]

[2]

[3]

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