Self-adjusting binary search trees：（自动调节的二叉有哪些信誉好的足球投注网站树）.pdfVIP

Self-Adjusting Binary Search Trees DANIEL DOMINIC SLEATOR AND ROBERT ENDRE TARJAN ATT Bell Laboratories, Murray Hill, NJ Abstract. The splay tree, 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 an n-node splay tree, all the standard search tree operations have an amortized time bound of O(log n) 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 accesssequences, splay trees are as efficient, to within a constant factor, as static optimum search trees. The efftciency of splay trees comes not from an explicit structural constraint, as with balanced trees, but from applying a simple restructuring heuristic, called splaying, 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. Categories and Subject Descriptors: E. 1 [Data]: Data Structures-trees; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems--sorting and searching General Terms: Algorithms, Theory Additional Key Words and Phrases:Amortized complexity, balanced trees, multidimensional searching, network optimization, self-organizing data structures 1. Introduction In this paper we apply the related concepts of amortized complexity and self- adjustment to binary search trees. We are