SELF-ADJUSTING BINARY SEARCH-TREES
SELF-ADJUSTING BINARY SEARCH-TREES
复制标题
DOI：
10.1145/3828.3835
复制
发表时间：
1985-01-01
影响因子：
2.5
通讯作者：
TARJAN, RE
中科院分区：
文献类型：
--
作者：
SLEATOR, DD;TARJAN, RE
提出并分析了一种自调整的二叉查找树--播放树。二叉搜索树是一种用于表示表和列表的数据结构，以便访问，插入和删除项很容易。在ann-节点splay树上，所有标准搜索树操作的摊销时间边界为O（logn）/操作，其中“摊销时间”是指在最坏情况的操作序列上平均的时间/操作。因此，当总运行时间是感兴趣的度量时，展开树和平衡树一样有效。此外，对于足够长的访问序列，展开树是有效的，在一个恒定的因素，作为静态的最佳搜索树。splay树的效率不是来自于一个明确的结构约束，就像平衡树一样，而是来自于在每次访问树时应用一个简单的重组启发式，称为playing。展开的扩展给出了另外两种数据结构的简化形式：字典式或多维搜索树和链接/切割树。
Thesplaytree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On ann-node splay tree, all the standard search tree operations have an amortized time bound ofO(logn) per operation, where by “amortized time” is meant the time per operation averaged over a worst-case sequence of operations. Thus splay trees are as efficient as balanced trees when total running time is the measure of interest. In addition, for sufficiently long access sequences, splay trees are as efficient, to within a constant factor, as static optimum search trees. The efficiency of splay trees comes not from an explicit structural constraint, as with balanced trees, but from applying a simple restructuring heuristic, calledsplaying, whenever the tree is accessed. Extensions of splaying give simplified forms of two other data structures: lexicographic or multidimensional search trees and link/cut trees.