Java Reference
In-Depth Information
Implement the suffix tree for a dictionary of words or phrases, with support
for wildcard search.
13.3 Revise the BST class of Section 5.4 to use the AVL tree rotations. Your new
implementation should not modify the original BST class ADT. Compare
your AVL tree against an implementation of the standard BST over a wide
variety of input data. Under what conditions does the splay tree actually save
time?
13.4 Revise the BST class of Section 5.4 to use the splay tree rotations. Your new
implementation should not modify the original BST class ADT. Compare
your splay tree against an implementation of the standard BST over a wide
variety of input data. Under what conditions does the splay tree actually save
time?
13.5 Implement a city database using the k-d tree. Each database record contains
the name of the city (a string of arbitrary length) and the coordinates of the
city expressed as integer x- and y-coordinates. Your database should allow
records to be inserted, deleted by name or coordinate, and searched by name
or coordinate. You should also support region queries, that is, a request to
print all records within a given distance of a specified point.
13.6 Implement a city database using the PR quadtree. Each database record con-
tains the name of the city (a string of arbitrary length) and the coordinates
of the city expressed as integer x- and y-coordinates. Your database should
allow records to be inserted, deleted by name or coordinate, and searched by
name or coordinate. You should also support region queries, that is, a request
to print all records within a given distance of a specified point.
13.7 Implement and test the PR quadtree, using the composite design to imple-
ment the insert, search, and delete operations.
13.8 Implement a city database using the bintree. Each database record contains
the name of the city (a string of arbitrary length) and the coordinates of the
city expressed as integer x- and y-coordinates. Your database should allow
records to be inserted, deleted by name or coordinate, and searched by name
or coordinate. You should also support region queries, that is, a request to
print all records within a given distance of a specified point.
13.9 Implement a city database using the point quadtree. Each database record
contains the name of the city (a string of arbitrary length) and the coordinates
of the city expressed as integer x- and y-coordinates. Your database should
allow records to be inserted, deleted by name or coordinate, and searched by
name or coordinate. You should also support region queries, that is, a request
to print all records within a given distance of a specified point.
13.10 Use the PR quadtree to implement an efficient solution to Problem 6.5. That
is, store the set of points in a PR quadtree. For each point, the PR quadtree
is used to find those points within distance D that should be equivalenced.
What is the asymptotic complexity of this solution?
