Karim Douieb
We present a linear-time algorithm for constructing multiway search trees with near-optimal search cost whose running time is independent of the size of the node in the tree. This problem is well-studied in the literature for the case of binary search trees. Using our new construction method, we are able to provide the tightest upper bound on the average search cost for an optimal binary search tree.