Merge an underfull child with one of its siblings
(self, parent: "BranchNode", child_index: int)
| 355 | parent.keys[child_index] = new_separator |
| 356 | |
| 357 | def _merge_with_sibling(self, parent: "BranchNode", child_index: int) -> None: |
| 358 | """Merge an underfull child with one of its siblings""" |
| 359 | child = parent.children[child_index] |
| 360 | |
| 361 | # Validate parent structure before merging |
| 362 | if child_index >= len(parent.children): |
| 363 | raise ValueError( |
| 364 | f"Invalid child_index {child_index} for parent with {len(parent.children)} children" |
| 365 | ) |
| 366 | if len(parent.keys) != len(parent.children) - 1: |
| 367 | raise ValueError( |
| 368 | f"Parent structure invalid: {len(parent.keys)} keys but {len(parent.children)} children" |
| 369 | ) |
| 370 | |
| 371 | # Prefer merging with left sibling (arbitrary choice) |
| 372 | if child_index > 0: |
| 373 | # Merge with left sibling |
| 374 | left_sibling = parent.children[child_index - 1] |
| 375 | |
| 376 | if child.is_leaf(): |
| 377 | # Check if merging would exceed capacity |
| 378 | total_keys = len(left_sibling.keys) + len(child.keys) |
| 379 | if total_keys <= self.capacity: |
| 380 | # Safe to merge |
| 381 | left_sibling.merge_with_right(child) |
| 382 | # Remove the merged child and its separator |
| 383 | parent.children.pop(child_index) |
| 384 | parent.keys.pop(child_index - 1) |
| 385 | else: |
| 386 | # Cannot merge without exceeding capacity - leave nodes separate |
| 387 | # This preserves tree structure but may leave underfull nodes |
| 388 | pass |
| 389 | else: |
| 390 | # Check if merging would exceed capacity |
| 391 | total_keys = ( |
| 392 | len(left_sibling.keys) + len(child.keys) + 1 |
| 393 | ) # +1 for separator |
| 394 | total_children = len(left_sibling.children) + len(child.children) |
| 395 | if total_keys <= self.capacity and total_children <= self.capacity + 1: |
| 396 | # Safe to merge |
| 397 | separator_key = parent.keys[child_index - 1] |
| 398 | left_sibling.merge_with_right(child, separator_key) |
| 399 | # Remove the merged child and its separator |
| 400 | parent.children.pop(child_index) |
| 401 | parent.keys.pop(child_index - 1) |
| 402 | else: |
| 403 | # Cannot merge without exceeding capacity - leave nodes separate |
| 404 | pass |
| 405 | |
| 406 | elif child_index < len(parent.children) - 1: |
| 407 | # Merge with right sibling |
| 408 | right_sibling = parent.children[child_index + 1] |
| 409 | |
| 410 | if child.is_leaf(): |
| 411 | # Check if merging would exceed capacity |
| 412 | total_keys = len(child.keys) + len(right_sibling.keys) |
| 413 | if total_keys <= self.capacity: |
| 414 | # Safe to merge |
no test coverage detected