research-article

AVL Trees with Relaxed Balance

Author:

Kim S. LarsenAuthors Info & Claims

Journal of Computer and System Sciences, Volume 61, Issue 3

Pages 508 - 522

https://doi.org/10.1006/jcss.2000.1705

Published: 01 December 2000 Publication History

Abstract

The idea of relaxed balance is to uncouple the rebalancing in search trees from the updating in order to speed up request processing in main-memory databases. In this paper, we describe a relaxed version of AVL trees. We prove that each update gives rise to at most a logarithmic number of rebalancing operations and that the number of rebalancing operations in the semidynamic case is amortized constant.

References

[1]

G.M. Adel'son-Vel'skiı, E.M. Landis, An algorithm for the organisation of information, Dokl. Akad. Nauk SSSR, 146 (1962) 263-266.

[2]

A.V. Aho, J.E. Hopcroft, J.D. Ullman, Addison¿Wesley, Reading, 1974.

[3]

R. Bayer, E. McCreight, Organization and maintenance of large ordered indexes, Acta Inform., 1 (1972) 173-189.

Digital Library

[4]

J. Boyar, R. Fagerberg, K.S. Larsen, Amortization results for chromatic search trees, with an application to priority queues, Springer-Verlag, Berlin/New York, 1995.

[5]

J. Boyar, R. Fagerberg, K.S. Larsen, Amortization results for chromatic search trees, with an application to priority queues, J. Comput. System Sci., 55 (1997) 504-521.

Digital Library

[6]

J.F. Boyar, K.S. Larsen, Efficient rebalancing of chromatic search trees, Springer-Verlag, Berlin/New York, 1992.

[7]

J.F. Boyar, K.S. Larsen, Efficient rebalancing of chromatic search trees, J. Comput. System Sci., 49 (1994) 667-682.

Digital Library

[8]

L.J. Guibas, R. Sedgewick, A dichromatic framework for balanced trees, 1978.

[9]

S. Hanke, The performance of concurrent red¿black tree algorithms, Springer-Verlag, Berlin/New York, 1999.

[10]

S. Hanke, T. Ottmann, E. Soisalon-Soininen, Relaxed balanced red¿black trees, Springer-Verlag, Berlin/New York, 1997.

[11]

S. Huddleston, K. Mehlhorn, A new data structure for representing sorted lists, Acta Inform., 17 (1982) 157-184.

Digital Library

[12]

J.L.W. Kessels, On-the-fly optimization of data structures, Commun. Assoc. Comput. Mach., 26 (1983) 895-901.

Digital Library

[13]

D.E. Knuth, Addison¿Wesley, Reading, 1968.

[14]

K.S. Larsen, AVL trees with relaxed balance, IEEE Comput. Soc. Press, Los Alamitos, 1994.

[15]

K.S. Larsen, Amortized constant relaxed rebalancing using standard rotations, Acta Inform., 35 (1998) 859-874.

[16]

K.S. Larsen, R. Fagerberg, B-trees with relaxed balance, IEEE Comput. Soc. Press, Los Alamitos, 1995.

[17]

K.S. Larsen, R. Farenberg, Efficient rebalancing of B-trees with relaxed balance, Internat. J. Found. Comput. Sci., 7 (1996) 169-186.

[18]

K.S. Larsen, T. Ottmann, E. Soisalon-Soininen, Relaxed balance for search trees with local rebalancing, Springer-Verlag, Berlin/New York, 1997.

[19]

K.S. Larsen, E. Soisalon-Soininen, P. Widmayer, Relaxed balance through standard rotations, Springer-Verlag, Berlin/New York, 1997.

[20]

D. Maier, S.C. Salveter, Hysterical B-trees, Inform. Process. Lett., 12 (1981) 199-202.

[21]

L. Malmi, E. Soisalon-Soininen, Group updates for relaxed height-balanced trees, 1999.

[22]

K. Mehlhorn, A. Tsakalidis, An amortized analysis of insertion into AVL-trees, SIAM J. Comput., 15 (1986) 22-33.

[23]

O. Nurmi, E. Soisalon-Soininen, Uncoupling updating and rebalancing in chromatic binary search trees, 1991.

[24]

O. Nurmi, E. Soisalon-Soininen, Chromatic binary search trees¿A structure for concurrent rebalancing, Acta Inform., 33 (1996) 547-557.

Digital Library

[25]

O. Nurmi, E. Soisalon-Soininen, D. Wood, Concurrency control in database structures with relaxed balance, 1987.

[26]

O. Nurmi, E. Soisalon-Soininen, D. Wood, Relaxed AVL trees, main-memory databases and concurrency, Internat. J. Comput. Math., 62 (1996) 23-44.

[27]

T. Ottmann, E. Soisalon-Soininen, Technical Report (1995).

[28]

E. Soisalon-Soininen, P. Widmayer, Relaxed balancing in search trees, Kluwer Academic, Dordrecht/Norwell, 1997.

[29]

R.E. Tarjan, Amortized computational complexity, SIAM J. Algebraic Discrete Methods, 6 (1985) 306-318.

Cited By

Blelloch GFerizovic DSun Y(2022)Joinable Parallel Balanced Binary TreesACM Transactions on Parallel Computing10.1145/35127699:2(1-41)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1145/3512769
Singh MGroves LPotanin A(2020)A Relaxed Balanced Lock-Free Binary Search TreeParallel and Distributed Computing, Applications and Technologies10.1007/978-3-030-69244-5_27(304-317)Online publication date: 28-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-69244-5_27
Sun YFerizovic DBelloch G(2018)PAMACM SIGPLAN Notices10.1145/3200691.317850953:1(290-304)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178509
Show More Cited By

Index Terms

AVL Trees with Relaxed Balance
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

B-trees with relaxed balance
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

B-trees with relaxed balance have been defined to facilitate first updating on shared-memory asynchronous parallel architectures. To obtain this, rebalancing has been uncoupled from the updating such that extensive locking can be avoided in connection ...
Search Trees with Relaxed Balance and Near-Optimal Height
WADS '01: Proceedings of the 7th International Workshop on Algorithms and Data Structures

We introduce the relaxed k-tree, a search tree with relaxed balance and a height bound, when in balance, of (1 + Ɛ) log₂ n + 1, for any Ɛ > 0. The rebalancing work is amortized O(1/Ɛ) per update. This is the first binary search tree with relaxed balance ...
B-Trees With Relaxed Balance

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 61, Issue 3

Dec. 2000

247 pages

ISSN:0022-0000

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Blelloch GFerizovic DSun Y(2022)Joinable Parallel Balanced Binary TreesACM Transactions on Parallel Computing10.1145/35127699:2(1-41)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1145/3512769
Singh MGroves LPotanin A(2020)A Relaxed Balanced Lock-Free Binary Search TreeParallel and Distributed Computing, Applications and Technologies10.1007/978-3-030-69244-5_27(304-317)Online publication date: 28-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-69244-5_27
Sun YFerizovic DBelloch G(2018)PAMACM SIGPLAN Notices10.1145/3200691.317850953:1(290-304)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178509
Sun YFerizovic DBelloch GKrall AGross T(2018)PAMProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178509(290-304)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178509
Blelloch GFerizovic DSun YScheideler CGilbert S(2016)Just Join for Parallel Ordered SetsProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935768(253-264)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935768
Brown TEllen FRuppert E(2014)A general technique for non-blocking treesACM SIGPLAN Notices10.1145/2692916.255526749:8(329-342)Online publication date: 6-Feb-2014
https://dl.acm.org/doi/10.1145/2692916.2555267
Brown TEllen FRuppert EMoreira JLarus J(2014)A general technique for non-blocking treesProceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/2555243.2555267(329-342)Online publication date: 6-Feb-2014
https://dl.acm.org/doi/10.1145/2555243.2555267
Larsen K(2003)Relaxed multi-way trees with group updatesJournal of Computer and System Sciences10.1016/S0022-0000(03)00027-866:4(657-670)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1016/S0022-0000%2803%2900027-8
Jacobsen LLarsen K(2001)Complexity of Layered Binary Search Trees with Relaxed BalanceProceedings of the 7th Italian Conference on Theoretical Computer Science10.5555/646293.687372(269-284)Online publication date: 4-Oct-2001
https://dl.acm.org/doi/10.5555/646293.687372
Larsen KBuneman P(2001)Relaxed multi-way trees with group updatesProceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/375551.375566(93-101)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1145/375551.375566
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents