(Node<K, V> x)
| 2180 | } |
| 2181 | |
| 2182 | private void fixup(Node<K, V> x) { |
| 2183 | Node<K, V> w; |
| 2184 | while (x != root && !x.color) { |
| 2185 | if (x == x.parent.left) { |
| 2186 | w = x.parent.right; |
| 2187 | if (w == null) { |
| 2188 | x = x.parent; |
| 2189 | continue; |
| 2190 | } |
| 2191 | if (w.color) { |
| 2192 | w.color = false; |
| 2193 | x.parent.color = true; |
| 2194 | leftRotate(x.parent); |
| 2195 | w = x.parent.right; |
| 2196 | if (w == null) { |
| 2197 | x = x.parent; |
| 2198 | continue; |
| 2199 | } |
| 2200 | } |
| 2201 | if ((w.left == null || !w.left.color) |
| 2202 | && (w.right == null || !w.right.color)) { |
| 2203 | w.color = true; |
| 2204 | x = x.parent; |
| 2205 | } else { |
| 2206 | if (w.right == null || !w.right.color) { |
| 2207 | w.left.color = false; |
| 2208 | w.color = true; |
| 2209 | rightRotate(w); |
| 2210 | w = x.parent.right; |
| 2211 | } |
| 2212 | w.color = x.parent.color; |
| 2213 | x.parent.color = false; |
| 2214 | w.right.color = false; |
| 2215 | leftRotate(x.parent); |
| 2216 | x = root; |
| 2217 | } |
| 2218 | } else { |
| 2219 | w = x.parent.left; |
| 2220 | if (w == null) { |
| 2221 | x = x.parent; |
| 2222 | continue; |
| 2223 | } |
| 2224 | if (w.color) { |
| 2225 | w.color = false; |
| 2226 | x.parent.color = true; |
| 2227 | rightRotate(x.parent); |
| 2228 | w = x.parent.left; |
| 2229 | if (w == null) { |
| 2230 | x = x.parent; |
| 2231 | continue; |
| 2232 | } |
| 2233 | } |
| 2234 | if ((w.left == null || !w.left.color) |
| 2235 | && (w.right == null || !w.right.color)) { |
| 2236 | w.color = true; |
| 2237 | x = x.parent; |
| 2238 | } else { |
| 2239 | if (w.left == null || !w.left.color) { |
no test coverage detected