Java Reference
In-Depth Information
data structure for storing such data is the R-tree, which was originally proposed by
Guttman [Gut84].
13.5
Exercises
13.1 Show the binary trie (as illustrated by Figure 13.1) for the following collec-
tion of values: 42, 12, 100, 10, 50, 31, 7, 11, 99.
13.2 Show the PAT trie (as illustrated by Figure 13.3) for the following collection
of values: 42, 12, 100, 10, 50, 31, 7, 11, 99.
13.3 Write the insertion routine for a binary trie as shown in Figure 13.1.
13.4 Write the deletion routine for a binary trie as shown in Figure 13.1.
13.5 (a) Show the result (including appropriate rotations) of inserting the value
39 into the AVL tree on the left in Figure 13.4.
(b) Show the result (including appropriate rotations) of inserting the value
300 into the AVL tree on the left in Figure 13.4.
(c) Show the result (including appropriate rotations) of inserting the value
50 into the AVL tree on the left in Figure 13.4.
(d) Show the result (including appropriate rotations) of inserting the value
1 into the AVL tree on the left in Figure 13.4.
13.6 Show the splay tree that results from searching for value 75 in the splay tree
of Figure 13.10(d).
13.7 Show the splay tree that results from searching for value 18 in the splay tree
of Figure 13.10(d).
13.8 Some applications do not permit storing two records with duplicate key val-
ues. In such a case, an attempt to insert a duplicate-keyed record into a tree
structure such as a splay tree should result in a failure on insert. What is
the appropriate action to take in a splay tree implementation when the insert
routine is called with a duplicate-keyed record?
13.9 Show the result of deleting point A from the k-d tree of Figure 13.11.
13.10
(a) Show the result of building a k-d tree from the following points (in-
serted in the order given). A (20, 20), B (10, 30), C (25, 50), D (35,
25), E (30, 45), F (30, 35), G (55, 40), H (45, 35), I (50, 30).
(b) Show the result of deleting point A from the tree you built in part (a).
13.11
(a) Show the result of deleting F from the PR quadtree of Figure 13.16.
(b) Show the result of deleting records E and F from the PR quadtree of
Figure 13.16.
13.12
(a) Show the result of building a PR quadtree 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).
