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
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
randomEntrySearchingOfBinaryTreesCuCs03573.pdf | 2019-12-21 | Public | Download |