Inserts label into the subtree rooted at self, performs any rotations necessary to maintain balance, and then returns the new root to this subtree (likely self). This is guaranteed to run in O(log(n)) time.
(self, label: int)
| 85 | return left |
| 86 | |
| 87 | def insert(self, label: int) -> RedBlackTree: |
| 88 | """Inserts label into the subtree rooted at self, performs any |
| 89 | rotations necessary to maintain balance, and then returns the |
| 90 | new root to this subtree (likely self). |
| 91 | This is guaranteed to run in O(log(n)) time. |
| 92 | """ |
| 93 | if self.label is None: |
| 94 | # Only possible with an empty tree |
| 95 | self.label = label |
| 96 | return self |
| 97 | if self.label == label: |
| 98 | return self |
| 99 | elif self.label > label: |
| 100 | if self.left: |
| 101 | self.left.insert(label) |
| 102 | else: |
| 103 | self.left = RedBlackTree(label, 1, self) |
| 104 | self.left._insert_repair() |
| 105 | elif self.right: |
| 106 | self.right.insert(label) |
| 107 | else: |
| 108 | self.right = RedBlackTree(label, 1, self) |
| 109 | self.right._insert_repair() |
| 110 | return self.parent or self |
| 111 | |
| 112 | def _insert_repair(self) -> None: |
| 113 | """Repair the coloring from inserting into a tree.""" |