Handle underflow in a child node by trying redistribution first
(self, parent: "BranchNode", child_index: int)
| 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""" |
| 293 | child = parent.children[child_index] |
| 294 | |
| 295 | # If child is not underfull, nothing to do |
| 296 | if not child.is_underfull(): |
| 297 | return |
| 298 | |
| 299 | # Handle empty children by merging them (they can't redistribute) |
| 300 | if len(child) == 0: |
| 301 | self._merge_with_sibling(parent, child_index) |
| 302 | return |
| 303 | |
| 304 | # Try to redistribute from siblings |
| 305 | redistributed = False |
| 306 | |
| 307 | # Try to borrow from right sibling |
| 308 | if child_index < len(parent.children) - 1: |
| 309 | right_sibling = parent.children[child_index + 1] |
| 310 | if right_sibling.can_donate(): |
| 311 | self._redistribute_from_right(parent, child_index) |
| 312 | redistributed = True |
| 313 | |
| 314 | # If no redistribution from right, try left sibling |
| 315 | if not redistributed and child_index > 0: |
| 316 | left_sibling = parent.children[child_index - 1] |
| 317 | if left_sibling.can_donate(): |
| 318 | self._redistribute_from_left(parent, child_index) |
| 319 | redistributed = True |
| 320 | |
| 321 | # If redistribution failed, try to merge with a sibling |
| 322 | if not redistributed: |
| 323 | self._merge_with_sibling(parent, child_index) |
| 324 | |
| 325 | def _redistribute_from_left(self, parent: "BranchNode", child_index: int) -> None: |
| 326 | """Redistribute keys from left sibling to child""" |
no test coverage detected