Pruning eliminates branches that cannot contain a valid or better candidate. It reduces unnecessary work during search and can reclaim storage after deletion, but aggressive pruning may trade accuracy for speed. section 6.2.4 section 10.4.3
Apply pruning differently according to the structure and objective:
- During trie deletion, unmark the key node, backtrack along the searched path, and remove nodes that become worthless leaves. Stop at a key node or an intermediate node with remaining children. section 6.2.4
- During R-tree point search, traverse only rectangles that can contain the query point. For nearest-neighbor search, discard branches whose closest possible distance exceeds the current minimum. section 10.2.4
- During approximate nearest-neighbor search, use a more aggressive criterion to visit fewer branches, accepting that the returned result may not be perfectly accurate. section 10.4.3
Removing a key from a trie
After deleting “anti,” its terminal node becomes a worthless leaf, so backtracking removes the edge for “i.” The node for “ant” then also becomes removable. Pruning stops when it reaches a parent that stores a key or still has another child. section 6.2.4
