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.
Fairley, Richard E., "Random Entry Searching of Binary Trees ; CU-CS-035-73" (1973). Computer Science Technical Reports. 34.