About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
A method for constructing binary search trees by making insertions at the root
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. © 1980 Plenum Publishing Corporation.