2-3 search trees
We introduce in this section a type of binary search tree where costs are guaranteed to be logarithmic. Our trees have near-perfect balance, where the height is guaranteed to be no larger than 2 lg N.
Proposition.
Search and insert operations in a 2-3 tree with N keys are guaranteed to visit at most lg N nodes.