A node merge repairs a tree after deletion makes a node smaller than the minimum entry count by combining it with an adjacent sibling. The parent then replaces both children with their merged result, preserving the tree’s structural invariants. section 10.2.2 section 10.3.5
An implementation follows these operations:
- Check that both nodes are leaves or both are internal nodes; merging unlike node types is rejected. section 10.3.5
- Combine leaf point collections or internal child collections into a new node. section 10.3.5
- Remove the original children from the parent and add the merged child in their place. section 10.3.5
Deletion in an SS-tree
A deletion can trigger cases involving borrowing and merging. After the merge, the tree remains valid, but a resulting bounding sphere may occupy most of its parent’s envelope and overlap sibling regions, potentially degrading balance and search performance. section 10.3.5
Figure 10.19 Deleting a point. This example shows, in order, cases 2(c), 2(b), and 1 described in this section.
Trace the deletion sequence through cases 2(c), 2(b), and 1, including the final merged-tree geometry. section 10.3.5
