More Web Proxy on the site http://driver.im/

article

Effective splaying with restricted rotations

Author:

Joan M. LucasAuthors Info & Claims

International Journal of Computer Mathematics, Volume 85, Issue 5

Pages 717 - 726

https://doi.org/10.1080/00207160701435219

Published: 01 May 2008 Publication History

Abstract

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.

References

[1]

Adelson-Velskii, G. M. and Landis, E. M. (1962) An algorithm for the organization of information. Soviet Mathematics - Doklady, 3, pp. 1259-1262.

[2]

Andersson, A. (1999) General balanced trees. Journal of Algorithms, 30, pp. 1-18.

Digital Library

[3]

Bayer, R. (1972) Symmetric binary B-trees: data structure and maintenance algorithms. Acta Informatica, 1, pp. 290-306.

Digital Library

[4]

Guibas, L. J. and Sedgewick, R. (1978) A dichromatic framework for balanced trees. New York Proceedings of the 19th Annual Symposium on Foundations of Computer Scienc, pp. 8-21.

Digital Library

[5]

Larsen, K. S., Soisalon-Soininen, E. and Widmayer, P. (2001) Relaxed balance using standard rotations. Algorithmica, 31, pp. 501-512.

[6]

Mahmoud, H. (1998) On rotations in fringe-balanced binary trees. Information Processing Letters, 65, pp. 41-46.

Digital Library

[7]

Mehlhorn, K. (1979) Dynamic binary search trees. SIAM Journal on Computing, 8, pp. 175-198.

[8]

Nievergelt, J. and Reingold, E. M. (1973) Binary search trees of bounded balance. SIAM Journal on Computing, 2, pp. 33-43.

[9]

Sleator, D. D. and Tarjan, R. E. (1985) Self-adjusting binary search trees. Journal of the ACM, 32, pp. 652-686.

Digital Library

[10]

Sleator, D. D., Tarjan, R. E. and Thurston, W. (1988) Rotation distance, triangulations and hyperbolic geometry. Journal of the American Mathematical Society, 1, pp. 647-681.

[11]

Pallo, J. M. (1986) Enumerating, ranking and unranking binary trees. The Computer Journal, 29, pp. 171-175.

[12]

Pallo, J. M. (1987) On the rotation distance in the lattice of binary trees. Information Processing Letters, 25, pp. 369-373.

Digital Library

[13]

Pallo, J. M. (1988) Some properties of the rotation lattice of binary trees. The Computer Journal, 31, pp. 564-565.

Digital Library

[14]

Sundar, R. (1992) On the deque conjecture for the splay algorithm. Combinatorica, 12, p. 95124.

[15]

Bonnin, A. and Pallo, J. M. (1992) A shortest path metric on unlabeled binary trees. Pattern Recognition Letters, 13, pp. 411-415.

Digital Library

[16]

Pallo, J. M. (2003) Right-arm rotation distance between binary trees. Information Processing Letters, 87, pp. 173-177.

Digital Library

[17]

Ruiz, A., Luccio, F., Enriquez, A. and Pagli, L. (2005) k-restricted Rotation with an Application to Search Tree Rebalancing. Proceedings of the 9th International Workshop on Algorithms and Data Structures. Lecture Notes in Comptuer Science, 3608, pp. 2-13.

Digital Library

[18]

Chen, Y., Chang, J. and Wang, Y. (2005) An efficient algorithm for estimating rotation distance between two binary trees. International Journal of Computer Mathematics, 82, pp. 1095-1106.

[19]

Wu, R., Chang, J. and Wang, Y. (2006) A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations. Theoretical Computer Science, 355, pp. 303-314.

Digital Library

[20]

Cleary, S. (2002) Restricted rotation distance between binary trees. Information Processing Letters, 84, pp. 333-338.

Digital Library

[21]

Cleary, S. and Taback, J. (2003) Bounding restricted rotation distance. Information Processing Letters, 88, pp. 251-256.

Digital Library

[22]

Lucas, J. M. (2004) A direct algorithm for restricted rotation distance. Information Processing Letters, 90:3, pp. 129-134.

Digital Library

Cited By

Pallo J(2019)Root-restricted Kleenean rotationsInformation Processing Letters10.1016/j.ipl.2010.10.014111:1(46-50)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2010.10.014
Pallo J(2019)Weak associativity and restricted rotationInformation Processing Letters10.1016/j.ipl.2009.01.014109:10(514-517)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2009.01.014

Index Terms

Effective splaying with restricted rotations

Recommendations

k-Restricted rotation with an application to search tree rebalancing
WADS'05: Proceedings of the 9th international conference on Algorithms and Data Structures

The restricted rotation distanced_R(S, T) between two binary trees S, T of n vertices is the minimum number of rotations by which S can be transformed into T, where rotations can only take place at the root of the tree, or at the right child of the root. ...
Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying

We present an extension of the splay technique, the chain-splay. Chain-splay trees 'splay' the accessed element to the root as classical splay trees do, but also perform some local 'house-keeping' splay operations below the accessed element. We prove ...
Splaying for Compression: An Experimental Study
PCI '11: Proceedings of the 2011 15th Panhellenic Conference on Informatics

In this paper, we propose novel randomized versions of the splay trees. We have evaluated the practical performance of these structures in comparison with the original version of splay trees and with their loglogn-competitive variations, in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Computer Mathematics

International Journal of Computer Mathematics Volume 85, Issue 5

May 2008

141 pages

ISSN:0020-7160

EISSN:1029-0265

Issue’s Table of Contents

Publisher

Taylor & Francis, Inc.

United States

Publication History

Published: 01 May 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pallo J(2019)Root-restricted Kleenean rotationsInformation Processing Letters10.1016/j.ipl.2010.10.014111:1(46-50)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2010.10.014
Pallo J(2019)Weak associativity and restricted rotationInformation Processing Letters10.1016/j.ipl.2009.01.014109:10(514-517)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ipl.2009.01.014

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents