Randomized splay trees: Theoretical and experimental results

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor.     

Rehabilitation of an unloved child: semi‐splaying

Splay trees are widely considered as the classic examples of self‐adjusting binary search trees and are part of most courses on data structures and algorithms. Already in the first seminal paper on splay trees (J. Assoc. Comput. Mach. 1985; 32(3):652–686) alternative operations were introduced, among which is semi‐splaying. On the one hand, the analysis of semi‐splaying gives a smaller constant for the amortized complexity, but on the other hand the authors write: Whether any version of semi‐splaying is an improvement over splaying depends on the access sequence. Semi‐splaying may be better when the access pattern is stable, but splaying adapts much faster to changes in usage. Maybe this sentence was the reason that nobody seriously ran tests to compare the performance of semi‐splaying and splaying. Semi‐splaying is conceptually simpler than splaying, has the same asymptotic amortized complexity and, as will be clear from empirical data presented in this paper, the practical performance is better for a very broad variety of access patterns. Therefore, its efficiency is a good reason to use semi‐splaying for applications instead of its more prominent brother. Moreover, its simplicity also makes it very attractive for teaching purposes. Copyright © 2008 John Wiley & Sons, Ltd.     

When to use splay trees

In this paper we present new empirical results for splay trees. These results provide a better understanding of how cache performance affects query execution time. Our results show that splay trees can have faster lookup times compared with randomly built binary search trees (BST) under certain settings. In contrast, previous experiments have shown that because of the instruction overhead involved in splaying, splay trees are less efficient in answering queries than randomly built BSTs—even when the data sets are heavily skewed (a favorable setting for splay trees). We show that at large tree sizes the difference in cache performance between the two types of trees is significant. This difference means that splay trees are faster than BSTs for this setting—despite still having a higher instruction count. Based on these results we offer guidelines in terms of tree size, access pattern, and cache size as to when splay trees will likely be more efficient. We also present a new splaying heuristic aimed at reducing instruction count and show that it can improve on standard splaying by 10–27%. Copyright © 2007 John Wiley & Sons, Ltd.     

An evaluation of self-adjusting binary search tree techniques

Much has been said in praise of self-adjusting data structures, particularly self-adjusting binary search trees. Self-adjusting trees are most suited to skewed key-access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst-case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self-adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key-access-frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self-adjusting trees, in almost all cases the AVL tree outperforms all the self-adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self-adjusting trees. Self-adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition.     

Effective splaying with restricted rotations

The splay tree is a well-known binary search tree with many remarkable properties. It is a self-adjusting data structure whose amortized performance matches any of the many forms of balanced search trees. Furthermore, splay trees are adaptive, and have superior performance in many specialized cases. It is a long-standing open problem whether splay trees are dynamically optimal. Most search tree algorithms are based on the fundamental rotation operation. In 2002 Cleary introduced the concept of restricted rotations, which severely limits where the rotation can be performed. We show that splaying can still be effected using only restricted rotations, while maintaining the same properties as regular splay trees.     

Untangling the balancing and searching of balanced binary search trees

A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.     

Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem

We present a class of O(n log n) heuristics for the Steiner tree problem in the Euclidean plane. These heuristics identify a small number of subsets with few, geometrically close, terminals using minimum spanning trees and other well-known structures from computational geometry: Delaunay triangulations, Gabriel graphs, relative neighborhood graphs, and higher-order Voronoi diagrams. Full Steiner trees of all these subsets are sorted according to some appropriately chosen measure of quality. A tree spanning all terminals is constructed using greedy concatenation. New heuristics are compared with each other and with heuristics from the literature by performing extensive computational experiments on both randomly generated and library problem instances. Received October 27, 1997; revised May 7, 1998.     

Encoding search trees in lists †

We study the optimal encoding of search trees in lists and, in particular, in single-linked lists. We are able to provide an 0(n²) construction algorithm for weighted binary search trees, which can be generalized to give an 0(n² log m) algorithm for weighted m-ary search trees.     

An efficient algorithm for estimating rotation distance between two binary trees

There are a number of ways of measuring the difference in shape between two rooted binary trees with the same number of leaves. Pallo (Computer Journal, 9, 171–175, 1986) introduced a left weight sequence, which is a sequence of positive integers, to characterize the structure of a binary tree. By applying the AVL tree transformation on binary trees, we develop an algorithm for the efficient transformation of the left weight sequences between two binary trees.     

Online shape learning using binary search trees

In this paper we propose an online shape learning algorithm based on the self-balancing binary search tree data structure for the storage and retrieval of shape templates. This structure can also be used for classification purposes. We introduce a similarity measure with which we can make decisions on how to traverse the tree and even backtrack through the search path to find more candidate matches. Then we describe every basic operation a binary search tree can perform adapted to such a tree of shapes. Note that as a property of binary search trees, all operations can be performed in O(logn)$O(\log n)$ time and are very efficient. Finally, we present experimental data evaluating the performance of the proposed algorithm and demonstrating the suitability of this data structure for the purpose it was designed to serve.     

Performance analysis of partial-match search algorithms for BD trees

Database systems are becoming increasingly popular for answering queries. Partial-match search queries are an important class of queries in such a system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A previous study indicated that the k-d tree performance is better than that of the BD tree for partial-match search queries. A recent paper reported some improved algorithms. However, it is unclear whether the improved algorithms show the BD tree in a favourable light for partial-match search queries. This paper explores the performance of these algorithms and compares their performance to that of the k-d tree. Since the BD tree construction process uses some heuristics to make it a better balanced tree, this paper also evaluates the effect of these heuristics on the partial-match search algorithms. The major conclusions of this study are that the BD tree performance for partial-match search is better than that of the k-d tree when an improved algorithm is used for partial-match search, and only the DZ expression rearrangement heuristic has substantial effect on partial-match search performance.     

Random binary search tree with equal elements

We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms given by Martínez and Roura (1998) [4] produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This implies an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees.     

ISA [k] trees: A class of binary search trees with minimal or near minimal internal path length

In recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.     

Updating a balanced search tree in O(1) rotations

Olivié has recently introduced the class of ‘half-balanced’ binary search trees, which have O(log n) access time but require only a constant number of single rotations for rebalancing after an insertion or a deletion. In this paper we show that a well-known class of balanced binary trees, the ‘symmetric binary B-trees’ of Bayer, have the same properties. This is not surprising, for Bayer's class and Oliviés class contain exactly the same binary trees.     

Binary search trees with binary comparison cost

We introduce a new variant of the cost measure usually associated with binary search trees. This cost measure BCOST, results from the observation that during a search, a decision to branch left need require only one binary comparison, whereas branching right or not branching at all requires two binary comparisons. This is in contrast with the standard cost measure TCOST, which assumes an equal number of comparisons is required for each of the three possible actions. With BCOST in mind we re-examine its effect with respect to minimal and maximal BCOST trees, minimal and maximal BCOST-height trees, and introduce a class of BCOST-height balanced trees, which have a logarithmically maintainable stratified subclass. Finally, a number of other issues are briefly touched upon.This work was partially supported by NATO Grant GR 155.81, Natural Sciences and Engineering Research Council of Canada Grant No. A-5692, and National Science Foundation Grant No. MCS-8116522.     

Optimal search trees using two-way key comparisons

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(n ⁵) time andO(n ³) 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.     

Optimal binary search trees with costs depending on the access paths

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n^k+2) and O(n^k+1), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.     

Efficient Algorithms to Detect and Restore Minimality, an Extension of the Regular Restriction of Resolution

A given binary resolution proof, represented as a binary tree, is said to be minimal if the resolutions cannot be reordered to generate an irregular proof. Minimality extends Tseitin"s regularity restriction and still retains completeness. A linear-time algorithm is introduced to decide whether a given proof is minimal. This algorithm can be used by a deduction system that avoids redundancy by retaining only minimal proofs and thus lessens its reliance on subsumption, a more general but more expensive technique.Any irregular binary resolution tree is made strictly smaller by an operation called Surgery, which runs in time linear in the size of the tree. After surgery the result proved by the new tree is nonstrictly more general than the original result and has fewer violations of the regular restriction. Furthermore, any nonminimal tree can be made irregular in linear time by an operation called Splay. Thus a combination of splaying and surgery efficiently reduces a nonminimal tree to a minimal one.Finally, a close correspondence between clause trees, recently introduced by the authors, and binary resolution trees is established. In that sense this work provides the first linear-time algorithms that detect minimality and perform surgery on clause trees.     

Right-arm rotation distance between binary trees

We consider a transformation on binary trees, named right-arm rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes of the right arm of the trees are allowed. Using ordinal tools, we give an efficient algorithm for computing the right-arm rotation distance between two binary trees, i.e., the minimum number of right-arm rotations necessary to transform one tree into the other.     

Randomized local search,evolutionary algorithms,and the minimum spanning tree problem

Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.