Problem 3: ``Meow Meow: The Revenge of Genghis Kitty" (30 pts)

Last, but not least, here lies a bunch questions that didn't fit elsewhere because Genghis mixed up my pile of notes for the exam. You only have to do five (5) of these, not all of them, and if you do more, i'll give you credit for whatever you do.

They are tailored to a variety of skills; so, don't give up even after reading them all.

3.1 (6)

Genghis claims that the number of leaves in a full binary tree containing $n$ nodes is $(n-1)/2$ plus 1. Is he correct? Explain for full credit.

3.2 (6)

Genghis thinks that search in a binary search tree is a $\theta(n)$ operation. Do you? Explain your answer for full credit.

3.3 (6)

Genghis told me that there cannot exist a binary tree yielding the same output order for both preorder and inorder traversals. Is he correct?

3.4 (6)

Why did I choose a hybrid data structure, such as the PR quadtree plus B$+$ tree, for our project? Genghis thinks it's because I'm a sadist. Is he right? Or, can you think of a logical reason that I might have done this? That is, what motivates using more than one abstract data type in an application?

3.5 (6)

Since Genghis has no front claws, he can't climb a general tree. But, YOU can. Just give me a definition of a general tree, along with on way of representing general trees that supports dynamic allocation of objects of uniform size.

3.6 (6)

Genghis is very interested in finding the shortest path out of the house. Let's help him.

Define the null path length (npl) of a node in a K-ary tree to be the distance between the node and an empty child. A leftist tree satisfies the property that for any node, X, in the binary tree, npl(left_child(X)) is greater than or equal to npl(right_child(X)).

Your job is to explain why a leftist tree rooted at X and having $r$ nodes on the right path must have at least $(2^r -1)$ nodes.

3.7 (6)

Genghis has given up and gone to sleep. However, he left you one last challenge. A dictionary system is maintained and modified heavily throughout the month, and then archived permanently onto a CDROM. Items can be added, deleted, and modified at any time during the month. But, after archiving, only search operations need to be supported.

What structure(s) would you use to implement this dictionary system throughout its life cycle? Explain for full credit.