Optimal multiway generalized split trees
Gen-Huey Chen, Lung-Tien Liu · International Journal of Computer Mathematics · 1991
Split trees are a suitable data structure for storing records with different access frequencies. The keys in the root node are required to have the highest access frequencies among all keys in the tree. If the requirement of the highest frequency keys in the root node is ignored, the resulting trees are called generalized split trees. Previously, Huang and Wong have designed an O(n 5) time algorithm to construct an optimal binary generalized split tree of size n. In this paper, we extend Huang and Wong's work to an (m+ 1)-way generalized split tree, where m>1. The proposed algorithm takes o(n 5 m)time.