TAOCP 6.2.3 Exercise 30
Let each available area be represented by a node $P$ with fields $\text{LOW}(P), \text{HIGH}(P), \text{SIZE}(P)=\text{HIGH}(P)-\text{LOW}(P)+1,$ and let all free areas be stored in a balanced binary t...
Exercise 30. [26] [26] (E. McCreight.) Section 2.5 discusses several strategies for dynamic storage allocation, including best-fit (choosing an available area as small as possible from among all those that fulfill the request) and first-fit (choosing the available area with lowest address among all those that fulfill the request). Show that if the available space is linked together as a balanced tree in an appropriate way, it is possible to do (a) best-fit (b) first-fit allocation in only O(log n) units of time, where n is the number of available areas. (The algorithms given for those methods in Section 2.5 take order n steps.)
Verified: yes
Solve time: 1m07s
Setup
Let each available area be represented by a node $P$ with fields
$\text{LOW}(P), \text{HIGH}(P), \text{SIZE}(P)=\text{HIGH}(P)-\text{LOW}(P)+1,$
and let all free areas be stored in a balanced binary tree $T$ in the sense of Section 6.2.3, with $O(\log n)$ height where $n$ is the number of nodes.
Two independent orderings are required.
One tree $T_A$ is ordered by increasing $\text{LOW}(P)$ (first-fit structure). Each node $P$ is augmented with
$M(P)=\max{\text{SIZE}(X)\mid X \text{ in subtree of } P}.$
A second tree $T_S$ is ordered by increasing $\text{SIZE}(P)$ (best-fit structure). No augmentation beyond the AVL balance fields is required.
Both trees contain the same set of nodes, linked by cross pointers so that each physical free area appears in both structures.
The problem is to support allocation of a request of size $r$ by:
(a) best-fit: find an available area of minimum size $\ge r$.
(b) first-fit: find the lowest-address area with size $\ge r$.
Each operation must take $O(\log n)$ time.
Solution
(a) Best-fit allocation
The tree $T_S$ is a balanced binary search tree ordered by $\text{SIZE}(P)$.
Given request $r$, the search proceeds from the root as follows.
At a node $P$, if $\text{SIZE}(P) < r$, the search moves to $RLINK(P)$ since all nodes in the left subtree have size not exceeding $\text{SIZE}(P)$ and therefore also fail the constraint.
If $\text{SIZE}(P) \ge r$, then $P$ is a candidate and the search continues in $LLINK(P)$ to find a smaller feasible size.
During the descent, a variable $Q$ stores the best candidate encountered, initialized to $A$ (null). Whenever a node $P$ satisfies $\text{SIZE}(P)\ge r$, set $Q \leftarrow P$.
When the search terminates at a null link, $Q$ is the smallest-size node among all nodes with size at least $r$, since every discarded node with $\text{SIZE}(P)\ge r$ has a left subtree containing only nodes with size not exceeding $\text{SIZE}(P)$, and every time a right move occurs all nodes in the left subtree and the current node are excluded from the candidate set.
The height of $T_S$ is $O(\log n)$, hence the number of link traversals is $O(\log n)$.
After locating $Q$, the area represented by $Q$ is removed from both $T_S$ and $T_A$ using standard AVL deletion, and if splitting is required, the remainder is reinserted.
(b) First-fit allocation
The tree $T_A$ is ordered by increasing $\text{LOW}(P)$ and augmented with subtree maxima $M(P)$.
Given request $r$, the goal is to find the smallest $\text{LOW}(P)$ such that $\text{SIZE}(P)\ge r$.
At a node $P$, first examine $LLINK(P)$. If $LLINK(P)\ne A$ and $M(LLINK(P))\ge r$, then a feasible block exists in the left subtree, so the search moves to $LLINK(P)$.
Otherwise, no node in the left subtree can satisfy the size constraint, and $\text{SIZE}(P)\ge r$ is tested. If it holds, $P$ is the first-fit candidate and the search moves to $LLINK(P)$ to find an earlier one.
If $\text{SIZE}(P)<r$ and $M(LLINK(P))<r$, then neither the left subtree nor $P$ is feasible, so the search moves to $RLINK(P)$.
The invariant maintained is that the search space is always restricted to nodes whose subtrees may still contain a feasible block; this is certified by $M(\cdot)$.
Each step eliminates at least one subtree at the boundary of a balanced tree path, so the number of visited nodes is bounded by the height of $T_A$, hence $O(\log n)$.
When the search terminates, the last recorded feasible node is the smallest-address node with size at least $r$, since any node skipped due to left-subtree infeasibility cannot contain a valid candidate in address order.
Deletion proceeds in both trees as in the best-fit case.
Verification
In $T_S$, every comparison with $\text{SIZE}(P)$ partitions the remaining search interval into nodes with strictly smaller size or potentially valid nodes, and every descent follows a child link, so no node is revisited. The height of an AVL tree is bounded by $O(\log n)$ by Theorem A of Section 6.2.3, so the search uses $O(\log n)$ steps.
Minimality of the returned node follows from the BST ordering: whenever a node $P$ with $\text{SIZE}(P)\ge r$ is encountered, all nodes in $LLINK(P)$ have size at most $\text{SIZE}(P)$, so any smaller feasible node must lie in that subtree, and the algorithm descends accordingly until no such node remains.
In $T_A$, the condition $M(LLINK(P))<r$ implies that every node in the left subtree has size strictly less than $r$, so no feasible candidate is discarded incorrectly when moving right. Conversely, when $M(LLINK(P))\ge r$, at least one feasible node exists in the left subtree, so moving left preserves completeness of the search region. Thus the algorithm never bypasses a valid first-fit candidate.
Since each move follows one child pointer in a balanced tree, the path length is bounded by the height of $T_A$, hence $O(\log n)$.
Both structures maintain AVL balance under insertions and deletions as in Algorithm 6.2.3A, so the height bound is preserved throughout updates.
This completes the proof. ∎
Notes
A single balanced tree can also support both operations by storing both keys $(\text{LOW}(P), \text{SIZE}(P))$ and maintaining a more elaborate augmentation, but the dual-tree representation matches the natural decomposition of the two orderings used by the algorithms of Section 2.5.