Java Reference
In-Depth Information
13
Advanced Tree Structures
This chapter introduces several tree structures designed for use in specialized ap-
plications. The trie of Section 13.1 is commonly used to store and retrieve strings.
It also serves to illustrate the concept of a key space decomposition. The AVL
tree and splay tree of Section 13.2 are variants on the BST. They are examples of
self-balancing search trees and have guaranteed good performance regardless of the
insertion order for records. An introduction to several spatial data structures used
to organize point data by xy-coordinates is presented in Section 13.3.
Descriptions of the fundamental operations are given for each data structure.
One purpose for this chapter is to provide opportunities for class programming
projects, so detailed implementations are left to the reader.
13.1
Tries
Recall that the shape of a BST is determined by the order in which its data records
are inserted. One permutation of the records might yield a balanced tree while
another might yield an unbalanced tree, with the extreme case becoming the shape
of a linked list. The reason is that the value of the key stored in the root node splits
the key range into two parts: those key values less than the root's key value, and
those key values greater than the root's key value. Depending on the relationship
between the root node's key value and the distribution of the key values for the
other records in the the tree, the resulting BST might be balanced or unbalanced.
Thus, the BST is an example of a data structure whose organization is based on an
object space decomposition, so called because the decomposition of the key range
is driven by the objects (i.e., the key values of the data records) stored in the tree.
The alternative to object space decomposition is to predefine the splitting posi-
tion within the key range for each node in the tree. In other words, the root could be
predefined to split the key range into two equal halves, regardless of the particular
values or order of insertion for the data records. Those records with keys in the
lower half of the key range will be stored in the left subtree, while those records
429
