Remove label from this tree.
(self, label: int)
| 148 | self.grandparent._insert_repair() |
| 149 | |
| 150 | def remove(self, label: int) -> RedBlackTree: |
| 151 | """Remove label from this tree.""" |
| 152 | if self.label == label: |
| 153 | if self.left and self.right: |
| 154 | # It's easier to balance a node with at most one child, |
| 155 | # so we replace this node with the greatest one less than |
| 156 | # it and remove that. |
| 157 | value = self.left.get_max() |
| 158 | if value is not None: |
| 159 | self.label = value |
| 160 | self.left.remove(value) |
| 161 | else: |
| 162 | # This node has at most one non-None child, so we don't |
| 163 | # need to replace |
| 164 | child = self.left or self.right |
| 165 | if self.color == 1: |
| 166 | # This node is red, and its child is black |
| 167 | # The only way this happens to a node with one child |
| 168 | # is if both children are None leaves. |
| 169 | # We can just remove this node and call it a day. |
| 170 | if self.parent: |
| 171 | if self.is_left(): |
| 172 | self.parent.left = None |
| 173 | else: |
| 174 | self.parent.right = None |
| 175 | # The node is black |
| 176 | elif child is None: |
| 177 | # This node and its child are black |
| 178 | if self.parent is None: |
| 179 | # The tree is now empty |
| 180 | return RedBlackTree(None) |
| 181 | else: |
| 182 | self._remove_repair() |
| 183 | if self.is_left(): |
| 184 | self.parent.left = None |
| 185 | else: |
| 186 | self.parent.right = None |
| 187 | self.parent = None |
| 188 | else: |
| 189 | # This node is black and its child is red |
| 190 | # Move the child node here and make it black |
| 191 | self.label = child.label |
| 192 | self.left = child.left |
| 193 | self.right = child.right |
| 194 | if self.left: |
| 195 | self.left.parent = self |
| 196 | if self.right: |
| 197 | self.right.parent = self |
| 198 | elif self.label is not None and self.label > label: |
| 199 | if self.left: |
| 200 | self.left.remove(label) |
| 201 | elif self.right: |
| 202 | self.right.remove(label) |
| 203 | return self.parent or self |
| 204 | |
| 205 | def _remove_repair(self) -> None: |
| 206 | """Repair the coloring of the tree that may have been messed up.""" |