Java Reference
In-Depth Information
(c) Show the result of deleting point F from the resulting tree in part (b).
13.13 On average, how many leaf nodes of a PR quadtree will typically be empty?
Explain why.
13.14 When performing a region search on a PR quadtree, we need only search
those subtrees of an internal node whose corresponding square falls within
the query circle. This is most easily computed by comparing the x and y
ranges of the query circle against the x and y ranges of the square corre-
sponding to the subtree. However, as illustrated by Figure 13.13, the x and
y ranges might overlap without the circle actually intersecting the square.
Write a function that accurately determines if a circle and a square intersect.
13.15 (a) Show the result of building a bintree from the following points (inserted
in the order given). Assume the tree is representing a space of 64 by 64
units. A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (30,
35), G (45, 25), H (45, 30), I (50, 30).
(b) Show the result of deleting point C from the tree you built in part (a).
(c) Show the result of deleting point F from the resulting tree in part (b).
13.16 Compare the trees constructed for Exercises 12 and 15 in terms of the number
of internal nodes, full leaf nodes, empty leaf nodes, and total depths of the
two trees.
13.17 Show the result of building a point quadtree from the following points (in-
serted in the order given). Assume the tree is representing a space of 64 by
64 units. A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (31,
35), G (45, 26), H (44, 30), I (50, 30).
13.6
Projects
13.1 Use the trie data structure to devise a program to sort variable-length strings.
The program's running time should be proportional to the total number of
letters in all of the strings. Note that some strings might be very long while
most are short.
13.2 Define the set of suffix strings for a string S to be S, S without its first char-
acter, S without its first two characters, and so on. For example, the complete
set of suffix strings for “HELLO” would be
fHELLO; ELLO; LLO; LO; Og:
A suffix tree is a PAT trie that contains all of the suffix strings for a given
string, and associates each suffix with the complete string. The advantage
of a suffix tree is that it allows a search for strings using “wildcards.” For
example, the search key “TH*” means to find all strings with “TH” as the
first two characters. This can easily be done with a regular trie. Searching
for “*TH” is not efficient in a regular trie, but it is efficient in a suffix tree.
