Binary search trees with binary comparison cost |
| |
Authors: | Thomas Ottmann Arnold L. Rosenberg Hans-Werner Six Derick Wood |
| |
Affiliation: | (1) Institute für Angewande Informatik und Formalebeschreibungsverfahren, Universität Karlsruhe, Postfach 6380, D-7500 Karlsruhe, W. Germany;(2) Department of Computer Science, Duke University, 27706 Durham, North Carolina, USA;(3) Data Structuring Group, Computer Science Department, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
Abstract: | We introduce a new variant of the cost measure usually associated with binary search trees. This cost measure BCOST, results from the observation that during a search, a decision to branch left need require only one binary comparison, whereas branching right or not branching at all requires two binary comparisons. This is in contrast with the standard cost measure TCOST, which assumes an equal number of comparisons is required for each of the three possible actions. With BCOST in mind we re-examine its effect with respect to minimal and maximal BCOST trees, minimal and maximal BCOST-height trees, and introduce a class of BCOST-height balanced trees, which have a logarithmically maintainable stratified subclass. Finally, a number of other issues are briefly touched upon.This work was partially supported by NATO Grant GR 155.81, Natural Sciences and Engineering Research Council of Canada Grant No. A-5692, and National Science Foundation Grant No. MCS-8116522. |
| |
Keywords: | Binary search trees binary comparison cost ternary comparison cost node visit cost stratified trees height balanced trees Fibonacci trees left Fibonacci trees |
本文献已被 SpringerLink 等数据库收录! |
|