Repair the tree after a deletion to maintain B-tree properties. Args: node: The parent node of the child that may need repair. child_index: The index of the child to check. Returns: True if a structural repair was performed, False otherwise.
(self, node: Node, child_index: int)
| 190 | return self._remove_key(node.children[i], key) |
| 191 | |
| 192 | def _repair_tree(self, node: Node, child_index: int) -> bool: |
| 193 | """Repair the tree after a deletion to maintain B-tree properties. |
| 194 | |
| 195 | Args: |
| 196 | node: The parent node of the child that may need repair. |
| 197 | child_index: The index of the child to check. |
| 198 | |
| 199 | Returns: |
| 200 | True if a structural repair was performed, False otherwise. |
| 201 | """ |
| 202 | child = node.children[child_index] |
| 203 | if self.min_numbers_of_keys < len(child.keys) <= self.max_number_of_keys: |
| 204 | return False |
| 205 | |
| 206 | if ( |
| 207 | child_index > 0 |
| 208 | and len(node.children[child_index - 1].keys) > self.min_numbers_of_keys |
| 209 | ): |
| 210 | self._rotate_right(node, child_index) |
| 211 | return True |
| 212 | |
| 213 | if ( |
| 214 | child_index < len(node.children) - 1 |
| 215 | and len(node.children[child_index + 1].keys) > self.min_numbers_of_keys |
| 216 | ): |
| 217 | self._rotate_left(node, child_index) |
| 218 | return True |
| 219 | |
| 220 | if child_index > 0: |
| 221 | self._merge(node, child_index - 1, child_index) |
| 222 | else: |
| 223 | self._merge(node, child_index, child_index + 1) |
| 224 | |
| 225 | return True |
| 226 | |
| 227 | def _rotate_left(self, parent_node: Node, child_index: int) -> None: |
| 228 | """Take a key from the right sibling and transfer it to the child. |
no test coverage detected