Access Restriction

Author Stout, Q. F ♦ Warren, B. L
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract A simple algorithm is given which takes an arbitrary binary search tree and rebalances it to form another of optimal shape, using time linear in the number of nodes and only a constant amount of space (beyond that used to store the initial tree). This algorithm is therefore optimal in its use of both time and space. Previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees. When the nodes of the tree are stored in an array, a simple addition to this algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using linear time and constant space.
Description Affiliation: Eastern Michigan Univ., Ypsilanti (Warren, B. L) || Univ. of Michigan, Ann Arbor (Stout, Q. F)
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 29
Issue Number 9
Page Count 7
Starting Page 902
Ending Page 908

Open content in new tab

   Open content in new tab
Source: ACM Digital Library