Tree Search in Major/Minor Loop Magnetic Bubble Memories

In this paper we analyze various search schemes in a major/minor loop bubble memory. Specifically, we study balanced tree search, one-sided height-balanced tree search, and one-sided k-height-balanced tree search. Two parameters are of interest in the present framework, namely, the number of comparisons and the amount of record movement required for a search. One-sided height-balanced tree search seems to offer the best compromise. Other related issues such as insertion and deletions are also discussed. Copyright © 1981 by The Institute of Electrical and Electronics Engineers, Inc.