Remove a key from a non-leaf node by replacing with predecessor/successor. Args: node: The non-leaf node containing the key. key_index: The index of the key to remove.
(
self, node: Node, key_index: int
)
| 279 | self.root = to_merge_node |
| 280 | |
| 281 | def _remove_from_nonleaf_node( |
| 282 | self, node: Node, key_index: int |
| 283 | ) -> None: |
| 284 | """Remove a key from a non-leaf node by replacing with predecessor/successor. |
| 285 | |
| 286 | Args: |
| 287 | node: The non-leaf node containing the key. |
| 288 | key_index: The index of the key to remove. |
| 289 | """ |
| 290 | key = node.keys[key_index] |
| 291 | left_subtree = node.children[key_index] |
| 292 | if len(left_subtree.keys) > self.min_numbers_of_keys: |
| 293 | largest_key = self._find_largest_and_delete_in_left_subtree(left_subtree) |
| 294 | elif len(node.children[key_index + 1].keys) > self.min_numbers_of_keys: |
| 295 | largest_key = self._find_largest_and_delete_in_right_subtree( |
| 296 | node.children[key_index + 1] |
| 297 | ) |
| 298 | else: |
| 299 | self._merge(node, key_index, key_index + 1) |
| 300 | return self._remove_key(node, key) |
| 301 | |
| 302 | node.keys[key_index] = largest_key |
| 303 | |
| 304 | def _find_largest_and_delete_in_left_subtree(self, node: Node) -> int: |
| 305 | """Find and remove the largest key in the left subtree. |
no test coverage detected