Randomized search trees

We present a randomized strategy for maintaining balance in dynamically changing search trees that has optimalexpected behavior. In particular, in the expected case a search or an update takes logarithmic time, with the update requiring fewer than two rotations. Moreover, the update time remains logarithmic, even if the cost of a rotation is taken to be proportional to the size of the rotated subtree. Finger searches and splits and joins can be performed in optimal expected time also. We show that these results continue to hold even if very little true randomness is available, i.e., if only a logarithmic number of truely random bits are available. Our approach generalizes naturally to weighted trees, where the expected time bounds for accesses and updates again match the worst-case time bounds of the best deterministic methods.We also discuss ways of implementing our randomized strategy so that no explicit balance information is maintained. Our balancing strategy and our algorithms are exceedingly simple and should be fast in practice.Supported by NSF Presidential Young Investigator award CCR-9058440.Supported by an AT&T graduate fellowship.This paper is dedicated to the memory of Gene Lawler.     

Restricted rotation distance between binary trees

Restricted rotation distance between pairs of rooted binary trees measures differences in tree shape and is related to rotation distance. In restricted rotation distance, the rotations used to transform the trees are allowed to be only of two types. Restricted rotation distance is larger than rotation distance, since there are only two permissible locations to rotate, but is much easier to compute and estimate. We obtain linear upper and lower bounds for restricted rotation distance in terms of the number of interior nodes in the trees. Further, we describe a linear-time algorithm for estimating the restricted rotation distance between two trees and for finding a sequence of rotations which realizes that estimate. The methods use the metric properties of the abstract group known as Thompson's group F.     

Finding lowest common ancestors in arbitrarily directed trees

It is well known how to preprocess a rooted tree in linear time to yield the lowest common ancestor of any given pair of nodes in constant time. We generalize these algorithms for graphs called Arbitrarily Directed Trees, or ADTs. Such trees are obtained by reversing the directions of some edges in trees with the customary “root-to-leaf” orientation of edges.     

Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

The length-constrained heaviest path (LCHP) in a weighted tree T, where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(nlogn) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al. (1999), which runs in O(nlog²n) time. Our method also improves on a previous O(nlogn) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.     

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.     

Database-backed decision trees with application to biological informatics

We describe a mechanism for the identification of biological organisms through the use of enhanced taxonomic keys-decision trees with nodes augmented by property lists that can serve as arguments to web or local services that access databases or other resources about species, specimens, and ecosystems. Authors of these identification schemes can use simple spreadsheet tools to structure the identification abstractions, and middleware renders the resulting trees into many different forms, with the databases possibly discovered and queried at the time an identification is proposed.     

Bounding restricted rotation distance

Restricted rotation distance between pairs of rooted binary trees quantifies differences in tree shape. Cleary exhibited a linear upper bound of 12n for the restricted rotation distance between two trees with n interior nodes, and a lower bound of (n−1)/3 if the two trees satisfy a reduction condition. We obtain a significantly improved sharp upper bound of 4n−8 for restricted rotation distance between two rooted binary trees with n interior nodes, and a significantly improved sharp lower bound of n−2, again with the requirement that the trees satisfy a reduction condition. These improvements use work of Fordham to compute the word metric in Thompson's group F.     

A direct algorithm for restricted rotation distance

In this paper we present a concise O(n) implementation of Cleary's algorithm for generating a sequence of restricted rotations between any two binary trees. The algorithm is described directly in terms of the binary trees, without using any intermediate representation.     

In-place random list permutations

We give two algorithms to randomly permute a linked list of length n in place using O(nlogn) time and O(logn) stack space in both the expected case and the worst case. The first algorithm uses well-known sequential random sampling, and the second uses inverted sequential random sampling.     

On the existence and construction of non-extreme (a,b)-trees

In amortized analysis of data structures, it is standard to assume that initially the structure is empty. Usually, results cannot be established otherwise. In this paper, we investigate the possibilities of establishing such results for initially non-empty multi-way trees.     

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.     

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.     

Relaxed Balance Using Standard Rotations

Abstract. In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.     

Succinct representation of dynamic trees

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree.We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively.We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time.Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or “poly-log-log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log-log” query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).     

Double hashing with passbits

Double hashing with bucket capacity one is augmented with multiple passbits to obtain significant reduction to unsuccessful search lengths. This improves the analysis of Martini et al. [P.M. Martini, W.A. Burkhard, Double hashing with multiple passbits, Internat. J. Found. Theoret. Comput. Sci. 14 (6) (2003) 1165-1188] by providing a closed form expression for the expected unsuccessful search lengths.     

Relaxed multi-way trees with group updates

Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel applications. We study the version of multi-way trees called (a,b)-trees (which includes B-trees) with the operations insertion, deletion, and group insertion. The latter has applications in for instance document databases, WWW search engines, and differential indexing. We prove that we obtain the optimal asymptotic rebalancing complexities of amortized constant time for insertion and deletion and amortized logarithmic time in the size of the group for group insertion. These results hold even for the relaxed version. This is an improvement over the existing results in the most interesting cases.