A data structure’s remove operation must do more than make an element disappear. It must preserve the properties that let later searches and updates work. The required repair depends on the structure: a priority queue exposes remove(element) in its API, while its implementation is responsible for maintaining its invariants. section 2.4
Start by finding the target, then handle the structural consequences:
- In a trie, search for the key’s terminal node and clear its key marker. If that leaves a branch containing no keys, backtrack and prune nodes until reaching another key or an intermediate node with children. Pruning saves memory but is not required for correct lookup. section 6.2.4
- In a k-d tree, replacing a removed node requires care: moving its child up can change which coordinate governs the split and break the tree’s invariant. The remove method finds a replacement minimum for the node’s split coordinate, then recursively removes that point from its former position. section 9.3.4
- In an SS-tree, delete the point from its leaf and update the bounding envelope. If the leaf falls below its minimum occupancy, repair it by borrowing an entry from a sibling or merging nodes; repair may continue while backtracking. section 10.3.5
Removing a trie key
Removing “anti” clears the key marker at the end of its path. That node is now a leaf with no key, so its parent can drop the edge for “i”. Backtracking can remove another empty intermediate node, but must stop before discarding a node needed by a remaining key such as “ant”. section 6.2.4
Listing 6.8 Method remove (with pruning)
function remove(node, s) #1
if s == “” then #2
deleted ← node.keyNode
node.keyNode ← false #3
return (deleted, node.children.size == 0) #4
c, tail ← s.splitAt(0) #5
if node.children[c] != null then #6
(deleted, shouldPrune) ← remove(node.children[c], tail) #7
if deleted and shouldPrune then #8
node.children[c] ← null #9
if node.keyNode == true or node.children.size > 0 then #10
shouldPrune ← false #11
return (deleted, shouldPrune)
else
return (false, false) #12
The recursive trie implementation returns both whether a key was deleted and whether its node should be pruned, so each parent can decide whether to remove its edge. section 6.2.4
Figure 9.17 An example of a k-d tree deletion for which replacing the deleted node with its only child wouldn’t work. (A) The initial tree, from which we remove node B. This node has only one child, so in a BST it would just be replaced by its child. (B) However, in a k-d tree this might cause violation of the k-d tree invariants, because moving a node one level up changes the coordinate on which the split is performed, when using it as a pivot.
The diagram shows why a one-child deletion rule that works in a binary search tree need not preserve a k-d tree’s split-coordinate invariant. section 9.3.4
Deletion is not always available or equally attractive. A basic Bloom filter forbids it: bits set when a key is added are never cleared, supporting its no-false-negative lookup property. K-d trees are not self-balancing and work best with relatively static points; SS-trees retain balance under substantial insertion and removal. Trie pruning trades extra work during removal for less memory wasted on empty branches. section 4.8.1 section 6.2.4 section 9.3.4 section 10.3.5
