平衡树——2-3树(Binary Search Tree - 2-3 Tree)

平衡树——2-3树(Binary Search Tree - 2-3 Tree)

简介(Introduction)
2-3 trees and 2-3-4 trees are binary search trees that allow one node have more than one items stored.

For BSTs, a node that holds a single item has at most two children. It is called 2-node.

For 2-3 tree, a node that can hold two items has at most three children. It is called 3-node.

For 2-3-4 tree, a node that can hold three items has at most four children. It is called 4-node.

构造2-3树(Building 2-3 tree)
We can build a 2-3 tree by inserting item one by one. To insert a key k, we pretend to search for it. This will take us to a leaf node in the tree, where k should now be inserted. If the node we find is a 2-node, k can be inserted without further ado. Otherwise we get a 3-node. The two inhabitants together with k form a node with three elements. We call them k1, k2 and k3 in sorted order. We now split the node, k1 and k3 forms their individual 2-node and k2 is promoted to the parent node. If the promotion cause the parent node overflow, split parent node in the same way.

示例(Example)
Build a 2-3 tree from 9, 5, 8, 3, 2, 4, 7.

时间复杂度(Time Complexity)
Searching, insertion and deletion are O(logn).

写在后面的话(PS)
Welcome questions always and forever.