Section 6.5: Retrieval on Secondary Keys

Exercise 14. [28] [28] Discuss the problem of deleting nodes from quadtrees, k-d trees, and postoffice trees like Fig. 45.

Verified: no
Solve time: 3m35s

---

Corrected Solution

The three structures all support dynamic sets of points in the plane, but they differ in what is structurally invariant. Deletion is therefore easy in none of them: it either destroys a recursively defined decomposition (quadtrees), preserves a weak ordering but requires local repair (k-d trees), or invalidates auxiliary search information that must be recomputed (postoffice trees).

1. Quadtrees

We consider the point quadtree model: each node stores a point $p=(x,y)$, and its four subtrees correspond to the four quadrants determined by comparisons with $p$. The structure depends on insertion order.

Invariant

For every node storing $p$:

• All points in its NE subtree satisfy $x > p_x, y > p_y$,
• NW: $x < p_x, y > p_y$,
• SW: $x < p_x, y < p_y$,
• SE: $x > p_x, y < p_y$,

recursively.

There is no global balancing condition.

Deletion

To delete a point $p$:

1. Locate the node $v$ containing $p$.
2. Remove $v$.
3. Let $S$ be the set of all points in the subtree rooted at $v$, excluding $p$.
4. Reinsert all points of $S$ into the remaining quadtree using the standard insertion algorithm.

Correctness

After removing $v$, all points in $S$ lose the partition constraints induced by $p$. There is no canonical local replacement that preserves all quadrant relations simultaneously.

Reinsertion restores the defining invariant because each point is reinserted using exactly the same recursive comparison rule that originally defines a quadtree. No points are lost or duplicated, and every subtree again satisfies the quadrant constraints.

Discussion of difficulty

Deletion is expensive: a single deletion may require reinserting $\Theta(n)$ points in the worst case, and repeated deletions can significantly degrade performance. This reflects the fact that the quadtree structure is insertion-defined rather than deletion-stable.

2. $k$-d trees

A $k$-d tree stores a point at each node and uses cyclic splitting dimensions. At a node $v$ at depth $d$, the splitting coordinate is $i = d \bmod k$.

Invariant

At node $v$ storing point $x$:

• All points in the left subtree satisfy $x_i' < x_i$,
• All points in the right subtree satisfy $x_i' \ge x_i$,

and this holds recursively.

Deletion procedure

To delete a point stored at node $v$:

Case 1: $v$ is a leaf

Remove it directly.

Case 2: $v$ is internal

Let $i$ be the splitting dimension at $v$.

1. If the right subtree is nonempty, find

$$ y = \arg\min_{z \in \text{right}(v)} z_i. $$ 2. Replace the point at $v$ by $y$. 3. Recursively delete $y$ from the right subtree.

(If the right subtree is empty, symmetrically use the left subtree and the maximum.)

Correctness of the split invariant

We verify the key step carefully.

Let $x$ be the original point at $v$, replaced by $y$.

By definition of $y$,

• For every point $z$ in the right subtree, $z_i \ge y_i$.

For the left subtree:

• Before replacement, all $z$ in the left subtree satisfy $z_i < x_i$.
• Since $y$ is chosen from the right subtree, we have $x_i \le y_i$ (because every right-subtree point satisfies $z_i \ge x_i$).

Thus,

$$ z_i < x_i \le y_i $$

for all $z$ in the left subtree.

Therefore:

• Left subtree still satisfies the required inequality relative to the new key $y$,
• Right subtree satisfies $z_i \ge y_i$ by minimality of $y$,
• No other parts of the tree are affected except removal of $y$, which preserves all remaining comparisons.

Hence the $k$-d tree invariant is preserved.

Discussion of difficulty

Deletion is not symmetric: it requires finding a suitable replacement from a subtree, and this operation may cost $\Theta(n^{1-1/k})$ in typical balanced cases. Although structurally correct, repeated deletions may degrade balance unless additional rebalancing heuristics are used.

3. Postoffice trees

Postoffice trees (as in TAOCP Fig. 45) are hierarchical spatial search structures in which each node represents a region and stores auxiliary information used for search pruning, typically one or more representative points of that region.

The key point is that, unlike quadtrees or k-d trees, correctness depends not only on the geometric decomposition but also on the auxiliary representatives used in search decisions.

Correct model of invariants

Each node $v$ has:

1. A region $R(v)$, determined by the tree structure.
2. A finite set of points $P(v)$ stored in its subtree.
3. One or more representative points $\mathrm{rep}(v) \in P(v)$.

The crucial invariant is:

• The representative $\mathrm{rep}(v)$ is chosen according to a fixed rule used by the search algorithm, typically depending on proximity properties within $P(v)$ or on bounding heuristics used for pruning.

This means:

$\mathrm{rep}(v)$ is not arbitrary. It is part of the correctness-critical auxiliary data structure.

Search correctness depends on the guarantee that representatives are valid for pruning decisions, not merely members of the subtree.

What deletion must preserve

After deletion of a point $p$, we must preserve:

1. The region decomposition $R(v)$ (unchanged structurally).
2. For every node $v$, the representative $\mathrm{rep}(v)$ must satisfy the same selection criterion used in the original construction from $P(v)$.

If this criterion is violated, search may incorrectly prune subtrees or fail to consider the true nearest neighbor.

Deletion procedure

To delete a point $p$:

Step 1: remove from leaves

Locate the leaf containing $p$ and remove it.

Step 2: propagate updates upward

For every ancestor $v$ such that $p \in P(v)$:

• Remove $p$ from $P(v)$.

Step 3: recompute representatives

For each such node $v$, recompute

$$ \mathrm{rep}(v) \leftarrow \text{the representative chosen by the original rule applied to } P(v). $$

This is essential: the representative cannot be chosen arbitrarily.

Step 4: handle empty subtrees

If $P(v)=\varnothing$, remove $v$, since it no longer represents a meaningful region in the search structure.

Correctness argument

The geometric decomposition $R(v)$ is unchanged by deletion, since it depends only on the tree shape, not on point membership.

The only potentially invalid component is the representative function. By recomputing $\mathrm{rep}(v)$ from the same rule used during construction, we restore exactly the invariant required by the search algorithm.

This is necessary because postoffice-tree search correctness depends on inequalities of the form:

• “the best possible candidate in region $R(v)$ cannot beat $\mathrm{rep}(v)$ beyond a bound,”

or similar pruning conditions. These bounds are valid only when $\mathrm{rep}(v)$ is correctly chosen according to the defining rule.

Arbitrary replacement is insufficient because it may destroy these bounds even if the point remains inside $P(v)$.

Thus deletion is correct only if representative recomputation is performed, and this recomputation may propagate up to the root.

Discussion of difficulty

Deletion is therefore potentially expensive:

• It requires updating all ancestors on the search path,
• and recomputing representative points, which may cost $\Theta(|P(v)|)$ per affected node in the worst case.

This reflects the essential difficulty: postoffice trees maintain auxiliary optimization data, not just structural partitioning, and deletion invalidates that optimization.

Conclusion

• Quadtrees: deletion requires full reinsertion because structure is insertion-defined and locally non-repairable.
• $k$-d trees: deletion is handled by replacement with a subtree extremal, preserving coordinate ordering invariants.
• Postoffice trees: deletion must preserve not only region structure but also correctness-critical representative choices; therefore representatives must be recomputed, not arbitrarily replaced.

$\square$