TAOCP 6.2.3 Exercise 33
Let $T$ be an AVL tree in the sense of Section 6.
Exercise 33. [25] [25] (A. L. Buchsbaum.) Explain how to encode the balance factors of an AVL tree implicitly, thus saving two bits per node, at the expense of additional work when the tree is accessed.
Samuel considered the nation of Israel, tribe by tribe,
and the tribe of Benjamin was picked by lot.
Then he considered the tribe of Benjamin, family by family, and the family of Matri was picked by lot.
Then he considered the family of Matri, man by man,
and Saul son of Kish was picked by lot.
But when they looked for Saul he could not be found., 1 Samuel 10:20-21
6.2.4. Multiway Trees
The tree search methods we have been discussing were developed primarily for internal searching, when we want to look at a table that is contained entirely within a computer’s high-speed internal memory. Let’s now consider the problem of external searching, when we want to retrieve information from a very large file that appears on direct access storage units such as disks or drums. (An introduction to disks and drums appears in Section 5.4.9.)
Tree structures lend themselves nicely to external searching, if we choose an appropriate way to represent the tree. Consider the large binary search tree shown in Fig. 29, and imagine that it has been stored in a disk file. (The LLINKs and RLINKs of the tree are now disk addresses instead of internal memory addresses.) If we search this tree in a naive manner, simply applying the algorithms we have learned for internal tree searching, we will have to make about lg N disk accesses before our search is complete. When N is a million, this means we will need 20 or so seeks. But suppose we divide the table into 7-node “pages,” as shown by the dotted lines in Fig. 29; if we access one page at a time, we need only about one third as many seeks, so the search goes about three times as fast!
Grouping the nodes into pages in this way essentially changes the tree from a binary tree to an octonary tree, with 8-way branching at each page-node. If we let the pages be still larger, with 128-way branching after each disk access, we can find any desired key in a million-entry table after looking at only three pages. We can keep the root page in the internal memory at all times, so that only two references to the disk are required even though the internal memory never needs to hold more than 254 keys at any time.
Of course we don’t want to make the pages arbitrarily large, since the internal memory size is limited and also since it takes a long time to read a large page. For example, suppose that it takes 72.5-+0.05m milliseconds to read a page that allows m-way branching. The internal processing time per page will
A482 SEARCHING 6.2.4
Fig. 29. A large binary search tree can be divided into “pages.”
be about a+ blgm, where a is small compared to 72.5ms, so the total amount of time needed for searching a large table is approximately proportional to lg N times
(72.5 +. 0.05m)/lgm + b.
This quantity achieves a minimum when m ®% 307; actually the minimum is very “broad”, a nearly optimum value is achieved for all m between 200 and 500. In practice there will be a similar range of good values for m, based on the characteristics of particular external memory devices and on the length of the records in the table.
W. I. Landauer [IEEE Trans. EC-12 (1963), 863-871] suggested building an m-ary tree by requiring level | to become nearly full before anything is allowed to appear on level 1+ 1. This scheme requires a rather complicated rotation method, since we may have to make major changes throughout the tree just to insert a single new item; Landauer was assuming that we need to search for items in the tree much more often than we need to insert or delete them.
When a file is stored on disk, and is subject to comparatively few insertions and deletions, a three-level tree is appropriate, where the first level of branching determines what cylinder is to be used, the second level of branching determines the appropriate track on that cylinder, and the third level contains the records themselves. This method is called indered-sequential file organization [see JACM 16 (1969), 569-571).
R. Muntz and R. Uzgalis [Proc. Princeton Conf. on Inf. Sciences and Systems 4 (1970), 345-349] suggested modifying the tree search and insertion method, Algorithm 6.2.2T, so that all insertions go onto nodes belonging to the same page as their parent node, whenever possible; if that page is full, a new page is started, whenever possible. If the number of pages is unlimited, and if the data arrives in random order, it can be shown that the average number of page accesses is approximately Hy /(H;»,, 1), only slightly more than we would obtain in the best possible m-ary tree. (See exercise 8.)
B-trees. A new approach to external searching by means of multiway tree branching was discovered in 1970 by R. Bayer and E. McCreight [Acta Informa-
Verified: no
Solve time: 1m15s
Solution
Let $T$ be an AVL tree in the sense of Section 6.2.3, except that the field $B(P)$ is not stored in each node. Each node contains only $KEY(P)$, $LLINK(P)$, and $RLINK(P)$.
Define the height function recursively by
$$ h(P) = \begin{cases} 0, & P = \Lambda,\ 1 + \max(h(LLINK(P)), h(RLINK(P))), & P \neq \Lambda. \end{cases} $$
For any node $P$, the balance factor that would have been stored in Algorithm A is therefore
$$ B(P) = h(RLINK(P)) - h(LLINK(P)). $$
During a search or insertion, the algorithm of Section 6.2.3 maintains a path from the root to the current node. Replace every use of the stored field $B(P)$ by a computation of the above expression using subtree heights.
For a node $P$ encountered during the downward search, both $h(LLINK(P))$ and $h(RLINK(P))$ are computed only when required. Each such computation is performed by recursive evaluation of $h(\cdot)$ using the defining equation, terminating at null pointers $\Lambda$.
After insertion of a new node $Q$, rebalancing requires access to balance factors along the path from $Q$ to the root. This path is explicitly known from the search history. For each node $P$ on this path, the value of $h(P)$ is recomputed from its children using the same recursive rule, and then $B(P)$ is obtained from the defining difference.
When a rotation is applied, only finitely many nodes are affected. Each affected node is relabeled by recomputing its height from its two children after the pointer changes caused by the rotation. No stored balance information is required, since all comparisons between subtree heights are performed directly through $h(\cdot)$.
Correctness follows because at every point where Algorithm A uses a stored balance factor, the value substituted is exactly $h(RLINK(P)) - h(LLINK(P))$, which is the definition of the balance factor in Section 6.2.3. Hence every rotation decision coincides with the original algorithm, and every structural transformation is identical.
The additional work arises from recomputation of subtree heights rather than reading a stored field. Since height evaluation is performed only when a node is accessed during search or rebalancing, the balance information is obtained implicitly from structure rather than explicitly stored. This removes the need for two bits per node while preserving correctness of all operations.
This completes the proof. ∎