Question

How many comparisons are needed to locate or to add each of the words in the search tree for Exercise 2, starting fresh each time?

a) palmistry

b) etymology

c) paleontology

d) glaciology

Short answer

a)3

b)3

c)3

d)3

Step-by-step solution

Firstly, Use the whole binary search tree from the exercise 2.

From the exercise 2,

We get,

Now find the how many comparisons are needed to locate or to add palmistrywordin the tree.

To add palmistry, compare with oenology. Palmistry is greater thanoenology. so, moves towards right sub-tree, there compare with phrenology. phrenology isgreater thanoenology moves towards left of phrenology, and then compare to ornithology. Palmistry is greater than ornithology so will be added to right of ornithology.

Hence, the number of comparisons to locate the wordpalmistryis 3.

Now find the how many comparisons are needed to locate or to add etymology word in the tree.

Compare etymology with root of the tree. Etymology is less than oenology thenmoves towards left sub- tree. Greater than campanology so moves towards right sub-tree of campanology. Etymology is less than ichthyology, so add to left of ichthyology.

Hence, the number of comparisons to locate the word etymology is 3.

Now find the how many comparisons are needed to locate or to add Paleontology wordin the tree.

Paleontology is compared with oenology, since it is greater than oenology moves towards right side and then compare with phrenology in which paleontology is less than phrenology. So, move towards left sub-tree and compare with ornithology. So, three comparisons to add paleontology.

Hence, the number of comparisons to locate the word Paleontology is 3.

 Step 5: Now find the how many comparisons are needed to locate or to add Glaciology word in the tree.

Glaciology is compared with oenology. Glaciology is less than oenology so moves towards left sub-tree. Compare with campanology. Glaciology is greater than campanology So move towards right of campanology. Compare with ichthyology. Glaciology is less than ichthyology so adds as the left child of it.

Hence, the number of comparisons to locate the word Orange is 3.