Optimal multiway generalized split trees.
Journal
Int. J. Comput. Math.
Journal Volume
41
Journal Issue
1-2
Pages
39-47
Date Issued
1991
Author(s)
Abstract
Abstract 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. Keywords: Dynamic programminggeneralized split treessplit treesC.R.Categories: E.11.1.2
Type
journal article