An insertion algorithm for a minimal internal path length binary search tree

This paper presents an insertion algorithm for maintaining a binary search tree with minimal internal path length. The insertion algorithm maintains minimal internal path length by displacing keys when necessary, in an inorder fashion, until a vacant position is found in the last incomplete level of the tree. The algorithm produces trees that are optimal for searching while exhibiting a runtime behavior that is between logarithmic and linear in the number of nodes in the tree, with linear time being its worst-case behavior.

View this article in the ACM Digital Library.