(Node t, Object key, Box found)
| 355 | } |
| 356 | |
| 357 | Node remove(Node t, Object key, Box found){ |
| 358 | if(t == null) |
| 359 | return null; //not found indicator |
| 360 | int c = doCompare(key, t.key); |
| 361 | if(c == 0) |
| 362 | { |
| 363 | found.val = t; |
| 364 | return append(t.left(), t.right()); |
| 365 | } |
| 366 | Node del = c < 0 ? remove(t.left(), key, found) : remove(t.right(), key, found); |
| 367 | if(del == null && found.val == null) //not found below |
| 368 | return null; |
| 369 | if(c < 0) |
| 370 | { |
| 371 | if(t.left() instanceof Black) |
| 372 | return balanceLeftDel(t.key, t.val(), del, t.right()); |
| 373 | else |
| 374 | return red(t.key, t.val(), del, t.right()); |
| 375 | } |
| 376 | if(t.right() instanceof Black) |
| 377 | return balanceRightDel(t.key, t.val(), t.left(), del); |
| 378 | return red(t.key, t.val(), t.left(), del); |
| 379 | // return t.removeLeft(del); |
| 380 | // return t.removeRight(del); |
| 381 | } |
| 382 | |
| 383 | static Node append(Node left, Node right){ |
| 384 | if(left == null) |
no test coverage detected