Question

How many comparisons are needed to locate or to add each of these words in the search tree for the words oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy, and astrology using alphabetic order starting fresh each time?

a) palmistry
b) etymology
c) paleontology
d) glaciology

Answer 1

To add each of the words 'palmistry', 'etymology', 'paleontology', and 'glaciology' to the search tree, 2 comparisons are needed for each word. The comparisons are based on the location in alphabetical order compared to the existing words in the tree.

Step-by-step explanation:

When adding words to a search tree, you make comparisons at each node starting from the root of the tree. The number of comparisons depends on the position of the word in the alphabetical order relative to the other words. Let's solve this step by step for each word.

palmistry: It falls between 'alchemy' and 'oenology' in alphabetical order. Starting fresh each time, first, compare it with 'alchemy'. Since 'palmistry' comes after 'alchemy', we move to the next comparison with 'oenology', before which 'palmistry' fits. So, 2 comparisons are needed.

etymology: This word comes after 'alchemy' but before 'campanology'. Therefore, first compare it with 'alchemy', and then with 'campanology'. Hence, 2 comparisons as well.

paleontology: It will be compared with 'oenology' first since it starts with 'p'. Then it should be compared with 'phrenology' because it comes after 'oenology' but before 'phrenology'. Thus, 2 comparisons are needed.

glaciology: Coming before 'ichthyology' but after 'campanology', the word 'glaciology' will be compared first with 'campanology', then with 'ichthyology'. Therefore, it requires 2 comparisons as well.

Answer 2

(a) 3

(b) 3

(c) 3

(d) 3

Step-by-step explanation:

(a) Comparing palmistry to oenology, it comes alphabetically after oenology, hence we move on to compare it to phrenology. Now, palmistry come first alphabetically, meaning we move on to compare it to ornithology. As ornithology has no children, there isn't any comparison needed so we end up with 3 comparisons.

(b) Comparing etymology to oenology, it comes alphabetically before oenology, hence we move on to compare it to campanology. Now, palmistry is latter alphabetically, meaning we move on to compare it to ichthyology. Etymology comes first alphabetically and as ichthyology has no rightward children, no more comparison is needed and we end up with 3 comparisons.

(c) Comparing paleontology to oenology, it comes alphabetically after oenology, hence we move on to compare it to phrenology. Now, palmistry is first alphabetically, so we move on to compare it to ornithology. As ornithology has no children, we won't make any more comparisons so we end up with 3 comparisons.

(d) Comparing glaciology to oenology, it comes alphabetically before oenology, so we move on to compare it to campanology. Now, palmistry comes latter alphabetically, so we move on to compare it to ichthyology. Glaciology is first alphabetically in this case and as ichthyology has no rightward children, no more comparisons are necessary and we end up with 3 comparisons