RedBlackTree extends AbstractSelfBalancingBinarySearchTree { @Override public Node insert(int element) { Node newNode = super.insert(element); newNode.left = nilNode; newNode.right = nilNode; root.parent = nilNode; insertRBFixup((RedBlackNode) newNode); return newNode; }  @Override Node insert(int element);  }
@Test public void testInsertionFixupColoring() throws Exception { RedBlackTree tree = new RedBlackTree(); Node node8 = tree.insert(8); Node node3 = tree.insert(3); Node node4 = tree.insert(4); assertThat(((RedBlackNode)node3).color, equalTo(ColorEnum.RED)); assertThat(((RedBlackNode)node4).color, equalTo(ColorEnum.BLACK)); assertThat(((RedBlackNode)node8).color, equalTo(ColorEnum.RED)); }
@Test public void testInsert() { RedBlackTree tree = new RedBlackTree(); tree.insert(20); tree.insert(15); tree.insert(25); tree.insert(10); Assert.assertEquals(((RedBlackNode)tree.root).color, ColorEnum.BLACK); Assert.assertEquals(((RedBlackNode)tree.search(15)).color, ColorEnum.BLACK); Assert.assertEquals(((RedBlackNode)tree.search(25)).color, ColorEnum.BLACK); tree.insert(17); tree.insert(8); Assert.assertEquals(((RedBlackNode)tree.search(15)).color, ColorEnum.RED); Assert.assertEquals(((RedBlackNode)tree.search(10)).color, ColorEnum.BLACK); Assert.assertEquals(((RedBlackNode)tree.search(17)).color, ColorEnum.BLACK); Assert.assertEquals(((RedBlackNode)tree.search(8)).color, ColorEnum.RED); tree.insert(9); Assert.assertEquals(((RedBlackNode)tree.search(10)).color, ColorEnum.RED); Assert.assertEquals(((RedBlackNode)tree.search(8)).color, ColorEnum.RED); Assert.assertEquals(((RedBlackNode)tree.search(9)).left.value, (Integer)8); testTreeBSTProperties(tree.root); }