Adjusts the tree balance. @param nd node to be adjusted
(final int nd)
| 256 | * @param nd node to be adjusted |
| 257 | */ |
| 258 | private void adjust(final int nd) { |
| 259 | int n = nd; |
| 260 | mod.set(n, true); |
| 261 | |
| 262 | while(n != -1 && n != root && mod.get(parent(n))) { |
| 263 | if(parent(n) == left(parent(parent(n)))) { |
| 264 | final int y = right(parent(parent(n))); |
| 265 | if(y != -1 && mod.get(y)) { |
| 266 | mod.set(parent(n), false); |
| 267 | mod.set(y, false); |
| 268 | mod.set(parent(parent(n)), true); |
| 269 | n = parent(parent(n)); |
| 270 | } else { |
| 271 | if(n == right(parent(n))) { |
| 272 | n = parent(n); |
| 273 | rotateLeft(n); |
| 274 | } |
| 275 | mod.set(parent(n), false); |
| 276 | mod.set(parent(parent(n)), true); |
| 277 | if(parent(parent(n)) != -1) rotateRight(parent(parent(n))); |
| 278 | } |
| 279 | } else { |
| 280 | final int y = left(parent(parent(n))); |
| 281 | if(y != -1 && mod.get(y)) { |
| 282 | mod.set(parent(n), false); |
| 283 | mod.set(y, false); |
| 284 | mod.set(parent(parent(n)), true); |
| 285 | n = parent(parent(n)); |
| 286 | } else { |
| 287 | if(n == left(parent(n))) { |
| 288 | n = parent(n); |
| 289 | rotateRight(n); |
| 290 | } |
| 291 | mod.set(parent(n), false); |
| 292 | mod.set(parent(parent(n)), true); |
| 293 | if(parent(parent(n)) != -1) rotateLeft(parent(parent(n))); |
| 294 | } |
| 295 | } |
| 296 | } |
| 297 | mod.set(root, false); |
| 298 | } |
| 299 | |
| 300 | /** |
| 301 | * Left rotation. |
no test coverage detected