chen0040 /
pyalgs
| @@ 174-188 (lines=15) @@ | ||
| 171 | return None |
|
| 172 | ||
| 173 | compared = cmp(key, x.key) |
|
| 174 | if compared < 0: |
|
| 175 | x.left = self._delete(x.left, key) |
|
| 176 | elif compared > 0: |
|
| 177 | x.right = self._delete(x.right, key) |
|
| 178 | else: |
|
| 179 | if x.left is None: |
|
| 180 | return x.right |
|
| 181 | elif x.right is None: |
|
| 182 | return x.left |
|
| 183 | else: |
|
| 184 | m = self.min(x.right) |
|
| 185 | m.right = self.del_min(x.right) |
|
| 186 | m.left = x.left |
|
| 187 | ||
| 188 | x = m |
|
| 189 | ||
| 190 | if self.is_red(x.right) and not self.is_red(x.left): |
|
| 191 | x = self.rotate_left(x) |
|
| @@ 89-103 (lines=15) @@ | ||
| 86 | return None |
|
| 87 | ||
| 88 | compared = cmp(key, x.key) |
|
| 89 | if compared < 0: |
|
| 90 | x.left = self._delete(x.left, key) |
|
| 91 | elif compared > 0: |
|
| 92 | x.right = self._delete(x.right, key) |
|
| 93 | else: |
|
| 94 | if x.left is None: |
|
| 95 | return x.right |
|
| 96 | elif x.right is None: |
|
| 97 | return x.left |
|
| 98 | else: |
|
| 99 | m = self.min(x.right) |
|
| 100 | m.right = self.del_min(x.right) |
|
| 101 | m.left = x.left |
|
| 102 | ||
| 103 | x = m |
|
| 104 | ||
| 105 | x.count = 1 + _count(x.left) + _count(x.right) |
|
| 106 | return x |
|
