ISSN:
1573-7640
Keywords:
Binary search trees
;
sorting
;
symbol tables
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract It is possible to construct a binary search tree by inserting items at the root instead of adding them as leaves. When used for sorting, the method has several desirable properties, including (a) fewer comparisons in the best case, (b) fewer comparisons in the worst case, (c) a reduced variance, and (d) good performance when the items are already nearly sorted or nearly reverse sorted. For applications in which the tree is searched for existing items as well as having new items added to it (e.g., in the construction of a symbol table), the tree can be made to exhibit stacklike behavior, so that the fewest comparisons are required to locate the most recently used items.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00995807
Permalink
