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.
Abstract
A parameterized binary search tree called iR tree is defined in this paper. A user is allowed to select a level of balance he desires. SR tree is a special case of iR tree when i=1. There are two new concepts in SR trees: (1) local balancing scheme that balances the tree locally; (2) consecutive storage for brother nodes that reduces pointer space. Although we may introduce empty nodes into the tree, we can show that only 1/8 of the nodes may be empty on the average, so it may still be advantageous in cases when record sizes are small. Insertion (and deletion) into SR trees can be done in time h + O(1) where h is the height of the tree. The average searching time for SR trees is shown to be 1.188 log<inf>2</inf>k where k is the number of keys. Generalization of the results of SR trees to iR in general is also given. © 1983 BIT Foundations.