Access Restriction

Author Gonnet, Gaston H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Avl trees ♦ Balanced trees ♦ Binary search trees ♦ Analysis of algorithms ♦ Weighted-balanced trees ♦ Internal path length ♦ Rotations
Abstract We present an algorithm for balancing binary search trees. In this algorithm single or double rotations are performed when they decrease the internal path of the total tree. It is shown that the worst internal path on such trees is never more than 5 percent worse than optimal and that its height is never more than 44 percent taller than optimal. This compares favorably with the AVL trees whose internal path may be 28 percent worse than optimal and the same 44 percent worst height, and with the weight-balanced trees which may be 15 and 100 percent worse than optimal, respectively. On the other hand, the number of rotations during a single insertion/deletion can be O(n), although the amortized worst-case number of rotations is O(log n) per update.
Description Affiliation: Univ. of Waterloo, Waterloo, Ont., Canada (Gonnet, Gaston H.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 26
Issue Number 12
Page Count 8
Starting Page 1074
Ending Page 1081

Open content in new tab

   Open content in new tab
Source: ACM Digital Library