NDLI: Rank-Balanced Trees

Please wait, while we are loading the content...

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

ACM Transactions on Algorithms (TALG) : Volume 11

Issue 4, June 2015

On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost

Computing Shortest Paths among Curved Obstacles in the Plane

Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Rank-Balanced Trees

Optimal Lower and Upper Bounds for Representing Sequences

Testing Planarity of Partially Embedded Graphs

Mapping Simple Polygons: The Power of Telling Convex from Reflex

A Bounded Budget Network Creation Game

An Improved Competitive Algorithm for Reordering Buffer Management

Issue 3, January 2015

Issue 2, November 2014

Issue 1, October 2014

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

ACM Transactions on Algorithms (TALG) : Volume 7

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

Rank-Balanced Trees

Content Provider	ACM Digital Library
Author	Sen, Siddhartha Tarjan, Robert E. Haeupler, Bernhard
Copyright Year	2015
Abstract	Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of $\textit{ranks}$ and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree), whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/2689412
Volume Number	11
Issue Number	4
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	AVL trees Balanced binary trees Amortized complexity Data structures Exponential potential function Red-black trees Search trees
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Deletion Without Rebalancing in Binary Search Trees

Rank-balanced trees (2009)

Rank-balanced trees (2009)

Comparative performance evaluation of the AVL and red-black trees

On-the-fly optimization of data structures

Deletion without rebalancing in multiway search trees

Insertions and deletions in one-sided height-balanced trees

Balancing binary trees by internal path reduction

An analytic approach for the analysis of rotations in fringe-balanced binary search trees

Rank-Balanced Trees

Similar Documents

Deletion Without Rebalancing in Binary Search Trees

Rank-balanced trees (2009)

Rank-balanced trees (2009)

Comparative performance evaluation of the AVL and red-black trees

On-the-fly optimization of data structures

Deletion without rebalancing in multiway search trees

Insertions and deletions in one-sided height-balanced trees

Balancing binary trees by internal path reduction

An analytic approach for the analysis of rotations in fringe-balanced binary search trees

Rank-Balanced Trees