Recursively delete a key from the tree. Returns True if the key was found and deleted, False otherwise.
(self, node: "Node", key: Any)
| 259 | raise KeyError(key) |
| 260 | |
| 261 | def _delete_recursive(self, node: "Node", key: Any) -> bool: |
| 262 | """ |
| 263 | Recursively delete a key from the tree. |
| 264 | Returns True if the key was found and deleted, False otherwise. |
| 265 | """ |
| 266 | if node.is_leaf(): |
| 267 | # Base case: delete from leaf |
| 268 | # Note: underflow handling will be done by parent |
| 269 | return self._delete_from_leaf(node, key) |
| 270 | |
| 271 | # Recursive case: find the correct child and recurse |
| 272 | child_index = node.find_child_index(key) |
| 273 | child = node.children[child_index] |
| 274 | deleted = self._delete_recursive(child, key) |
| 275 | if not deleted: |
| 276 | return False |
| 277 | |
| 278 | # Handle child underflow after deletion |
| 279 | if len(child) == 0 or child.is_underfull(): |
| 280 | # Child is underfull (including completely empty), try redistribution or merging |
| 281 | self._handle_underflow(node, child_index) |
| 282 | |
| 283 | # If parent became underfull it will be handled by the calling recursive call. |
| 284 | |
| 285 | # Handle root collapse: if root has only one child, make that child the new root |
| 286 | if node == self.root and not node.is_leaf() and len(node.children) == 1: |
| 287 | self.root = node.children[0] |
| 288 | |
| 289 | return deleted |
| 290 | |
| 291 | def _handle_underflow(self, parent: "BranchNode", child_index: int) -> None: |
| 292 | """Handle underflow in a child node by trying redistribution first""" |
no test coverage detected