TAOCP 6.2.1 Exercise 3
The statement “What searching method corresponds to the tree ?
Section 6.2.1: Searching an Ordered Table
Exercise 3. [15] [15] What searching method corresponds to the tree ?
What is the average number of comparisons made in a successful search? in an unsuccessful search?
A. [20] Ifa search using Program 6.15 (sequential search) takes exactly 638 units of time, how long does it take with Program B (binary search)?
Verified: yes
Solve time: 1m03s
The statement “What searching method corresponds to the tree ?” depends entirely on the missing comparison tree diagram. The structure of the tree determines both the algorithm and the path lengths needed for the average-cost calculations.
Without the figure (node structure, labeling, and branching pattern), the method cannot be identified uniquely, and the average number of comparisons for successful and unsuccessful searches cannot be computed.
Provide the diagram of the tree for Exercise 6.2.1.3, and the solution can be completed rigorously, including the exact correspondence to a search method and the full internal and external path length analysis.