Home → Magazine Archive → May 1988 (Vol. 31, No. 5) → An insertion algorithm for a minimal internal path... → Abstract

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

By Thomas E. Gerasch

Communications of the ACM, Vol. 31 No. 5, Pages 579-585

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.

The full text of this article is premium content


No entries found