Java Reference
In-Depth Information
Figure10.7
Breaking the BST into blocks.
The BST is divided among disk
blocks, each with space for three nodes.
The path from the root to any leaf is
contained on two blocks.
5
4
3
7
2
6
2
4
6
1
3
5
7
(A)
(B)
Figure10.8
An attempt to re-balance a BST after insertion can be expensive.
(a) A BST with six nodes in the shape of a complete binary tree. (b) A node with
value 1 is inserted into the BST of (a). To maintain both the complete binary tree
shape and the BST property, a major reorganization of the tree is required.
BST. The first is how to keep the tree balanced. The second is how to arrange the
nodes on blocks so as to keep the number of blocks encountered on any path from
the root to the leaves at a minimum.
We could select a scheme for balancing the BST and allocating BST nodes to
blocks in a way that minimizes disk I/O, as illustrated by Figure 10.7. However,
maintaining such a scheme in the face of insertions and deletions is difficult. In
particular, the tree should remain balanced when an update takes place, but doing
so might require much reorganization. Each update should affect only a few blocks,
or its cost will be too high. As you can see from Figure 10.8, adopting a rule such
as requiring the BST to be complete can cause a great deal of rearranging of data
within the tree.
We can solve these problems by selecting another tree structure that automat-
ically remains balanced after updates, and which is amenable to storing in blocks.
There are a number of balanced tree data structures, and there are also techniques
for keeping BSTs balanced. Examples are the AVL and splay trees discussed in
Section 13.2. As an alternative, Section 10.4 presents the 2-3 tree, which has the
property that its leaves are always at the same level. The main reason for discussing
the 2-3 tree here in preference to the other balanced search trees is that it naturally
