Reports

 

Random Entry Searching of Binary Trees ; CU-CS-035-73 Public Deposited

Downloadable Content

Download PDF
https://scholar.colorado.edu/concern/reports/d791sg918
Abstract
  • A new technique for searching lexically ordered binary trees is analyzed. Searching starts at a randomly selected node, rather than at the root node. Searching progresses in the usual manner until the item of interest is found, or until a leaf node is encountered. Leaf nodes contain pointers to the root of the tree. If the desired item is not found upon first encounter of a leaf node, the tree is reentered at the root, and the usual binary search follows. If the desired item is not found upon second encounter of a leaf node, the item is not in the tree. The average number of probes to retrieve an item of information from a balanced binary tree having 2^k-1 nodes, for integer k, is shown to be bounded above by k+1, as k becomes large. Thus, on the average, this technique requires at most 2 more probes than conventional searching. The maximum number of probes is shown to be 2k-1, as compared to k for conventional proving. However, the maximum number of probes occurs with probability s^-(k+1), as compared to probability 1/2 for conventional searching. Computer simulation and analytical analysis of the random searching strategy are both presented, with complete agreement of results.
Creator
Date Issued
  • 1973-12-01
Academic Affiliation
Last Modified
  • 2019-12-21
Resource Type
Rights Statement
Language

Relationships

Items