Thumbnail
Access Restriction
Subscribed

Author Ness, D. N. ♦ Martin, W. A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Global and local optimization ♦ Retrieving information from binary trees ♦ Recursion ♦ Sorting
Abstract Items can be retrieved from binary trees grown with a form of the Algorithm Quicksort in an average time proportional to log n, where n is the number of items in the tree. The binary trees grown by this algorithm sometimes have some branches longer than others; therefore, it is possible to reduce the average retrieval time by restructuring the tree to make the branches as uniform in length as possible. An algorithm to do this is presented. The use of this algorithm is discussed, and it is compared with another which restructures the tree after each new item is added.
Description Affiliation: Massachusetts Institute of Technology, Cambridge, MA (Martin, W. A.; Ness, D. N.)
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 15
Issue Number 2
Page Count 6
Starting Page 88
Ending Page 93


Open content in new tab

   Open content in new tab
Source: ACM Digital Library