(x *RBNode[T], key T)
| 173 | } |
| 174 | |
| 175 | func (t *RB[T]) pushHelper(x *RBNode[T], key T) { |
| 176 | y := t._NIL |
| 177 | for x != t._NIL { |
| 178 | y = x |
| 179 | switch { |
| 180 | case key < x.Key(): |
| 181 | x = x.left |
| 182 | case key > x.Key(): |
| 183 | x = x.right |
| 184 | default: |
| 185 | return |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | node := &RBNode[T]{ |
| 190 | key: key, |
| 191 | left: t._NIL, |
| 192 | right: t._NIL, |
| 193 | parent: y, |
| 194 | color: Red, |
| 195 | } |
| 196 | if y == t._NIL { |
| 197 | t.Root = node |
| 198 | } else if node.key < y.key { |
| 199 | y.left = node |
| 200 | } else { |
| 201 | y.right = node |
| 202 | } |
| 203 | |
| 204 | if node.parent == t._NIL { |
| 205 | node.color = Black |
| 206 | return |
| 207 | } |
| 208 | |
| 209 | if node.parent.parent == t._NIL { |
| 210 | return |
| 211 | } |
| 212 | |
| 213 | t.pushFix(node) |
| 214 | } |
| 215 | |
| 216 | func (t *RB[T]) leftRotate(x *RBNode[T]) { |
| 217 | y := x.right |