Optimal search trees using two-way key comparisons
Optimal search trees using two-way key comparisons
复制标题
使用双向键比较的最佳搜索树
DOI：
10.1007/bf01178732
复制
发表时间：
1994
期刊：
影响因子：
0.6
通讯作者：
David A. Spuler
中科院分区：
文献类型：
--
作者：
David A. Spuler
二叉搜索树和二叉树的推广利用了双向键比较：双向比较树。双向比较树对于动态情况几乎没有用处，但是对于静态数据集，它是对最优二叉搜索树和最优二叉分割树的改进。提出了在访问概率相等时构造最优双向比较树的AnO(n)时间和空间算法，并给出了最优代价的精确公式。对于不相等访问频率的最优双向比较树，无论是成功的还是失败的，都可以使用与最优二叉树相似的算法在inO（n5）时间和do （n3）空间上进行计算。与最优二叉搜索树相比，最优的双向比较树可以将搜索成本提高50%。
A generalization of binary search trees and binary split trees is developed that takes advantage of two-way key comparisons: the two-way comparison tree. The two-way comparison tree has little use for dynamic situations but is an improvement over the optimal binary search tree and the optimal binary split tree for static data sets. AnO(n) time and space algorithm is presented for constructing an optimal two-way comparison tree when access probabilities are equal, and an exact formula for the optimal cost is developed. The construction of the optimal two-way comparison tree for unequal access frequencies, both successful and unsuccessful, is computable inO(n5) time andO(n3) space using algorithms similar to those for the optimal binary split tree. The optimal two-way comparison tree can improve search cost by up to 50% over the optimal binary search tree.