2-3 tree
| 2-3 tree | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||||||||||
| Invented | 1970 | ||||||||||||||||||||
| Invented by | John Hopcroft | ||||||||||||||||||||
| Time complexity in big O notation | |||||||||||||||||||||
|
|||||||||||||||||||||
| Algorithm | Average | Worst Case | |
|---|---|---|---|
| Space | O(n) | O(n) | |
| Search | O(log n) | O(log n) | |
| Insert | O(log n) | O(log n) | |
| Delete | 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. 2−3 trees were invented by John Hopcroft in 1970.
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.
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:
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.
Insertion works by searching for the proper location of the key and adds 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.
...
Wikipedia