RedBlackTree extends AbstractSelfBalancingBinarySearchTree { @Override protected Node delete(Node deleteNode) { Node replaceNode = null; if (deleteNode != null && deleteNode != nilNode) { Node removedOrMovedNode = deleteNode; ColorEnum removedOrMovedNodeColor = ((RedBlackNode)removedOrMovedNode).color; if (deleteNode.left == nilNode) { replaceNode = deleteNode.right; rbTreeTransplant(deleteNode, deleteNode.right); } else if (deleteNode.right == nilNode) { replaceNode = deleteNode.left; rbTreeTransplant(deleteNode, deleteNode.left); } else { removedOrMovedNode = getMinimum(deleteNode.right); removedOrMovedNodeColor = ((RedBlackNode)removedOrMovedNode).color; replaceNode = removedOrMovedNode.right; if (removedOrMovedNode.parent == deleteNode) { replaceNode.parent = removedOrMovedNode; } else { rbTreeTransplant(removedOrMovedNode, removedOrMovedNode.right); removedOrMovedNode.right = deleteNode.right; removedOrMovedNode.right.parent = removedOrMovedNode; } rbTreeTransplant(deleteNode, removedOrMovedNode); removedOrMovedNode.left = deleteNode.left; removedOrMovedNode.left.parent = removedOrMovedNode; ((RedBlackNode)removedOrMovedNode).color = ((RedBlackNode)deleteNode).color; } size--; if (removedOrMovedNodeColor == ColorEnum.BLACK) { deleteRBFixup((RedBlackNode)replaceNode); } } return replaceNode; }  @Override Node insert(int element);  }
@Test public void testDelete() { RedBlackTree tree = new RedBlackTree(); tree.insert(20); tree.insert(15); tree.insert(25); tree.insert(23); tree.insert(27); Assert.assertEquals(((RedBlackNode)tree.root).color, ColorEnum.BLACK); Assert.assertEquals(tree.size, 5); Assert.assertEquals(tree.root.right.value, (Integer)25); Assert.assertEquals(tree.root.right.left.value, (Integer)23); Assert.assertEquals(((RedBlackNode)tree.root.right.left).color, ColorEnum.RED); tree.delete(25); Assert.assertEquals(tree.size, 4); Assert.assertEquals(tree.root.value, (Integer)20); Assert.assertEquals(tree.root.right.value, (Integer)27); Assert.assertEquals(((RedBlackNode)tree.root.right).color, ColorEnum.BLACK); Assert.assertEquals(tree.root.right.right.value, null); Assert.assertEquals(tree.root.right.left.value, (Integer)23); Assert.assertEquals(((RedBlackNode)tree.root.right.left).color, ColorEnum.RED); testTreeBSTProperties(tree.root); }