RedBlackTree extends AbstractRotatingBinarySearchTree<E, RedBlackTreeNode<E>> { @Override public RedBlackTreeNode<E> insert(E value) { final RedBlackTreeNode<E> node = getFactory().createNode(value); RedBlackTreeNode<E> current = getRoot(); RedBlackTreeNode<E> parent = null; while (current != null) { parent = current; if (lessThan(value, current.getValue())) { current = current.getLeftChild(); } else { current = current.getRightChild(); } } node.setParent(parent); node.setColor(NodeColor.RED); postInsert(value, node, parent); insertFix(node); return node; } RedBlackTree(Comparator<E> comparator); @Override RedBlackTreeNode<E> insert(E value); @Override RedBlackTreeNode<E> delete(E value);  }
@Test public void testInsertingTheRoot() throws Exception { final RedBlackTree<Integer> tree = tree(); tree.insert(10); assertThat(tree.getRoot(), is(notNullValue())); assertThat(tree.getRoot().getValue(), is(10)); assertThat(tree.getRoot().getColor(), is(NodeColor.BLACK)); }
@Test public void testInsertingItem() throws Exception { final RedBlackTree<Integer> tree = tree(); tree.insert(10, 7, 13); assertThat(tree.getRoot(), is(notNullValue())); assertThat(tree.getRoot().getValue(), is(10)); assertThat(tree.getRoot().getColor(), is(NodeColor.BLACK)); assertThat(tree.getRoot().getLeftChild(), is(notNullValue())); assertThat(tree.getRoot().getLeftChild().getValue(), is(7)); assertThat(tree.getRoot().getLeftChild().getColor(), is(NodeColor.RED)); assertThat(tree.getRoot().getRightChild(), is(notNullValue())); assertThat(tree.getRoot().getRightChild().getValue(), is(13)); assertThat(tree.getRoot().getRightChild().getColor(), is(NodeColor.RED)); tree.insert(15); assertThat(tree.getRoot(), is(notNullValue())); assertThat(tree.getRoot().getValue(), is(10)); assertThat(tree.getRoot().getColor(), is(NodeColor.BLACK)); assertThat(tree.getRoot().getLeftChild(), is(notNullValue())); assertThat(tree.getRoot().getLeftChild().getValue(), is(7)); assertThat(tree.getRoot().getLeftChild().getColor(), is(NodeColor.BLACK)); assertThat(tree.getRoot().getRightChild(), is(notNullValue())); assertThat(tree.getRoot().getRightChild().getValue(), is(13)); assertThat(tree.getRoot().getRightChild().getColor(), is(NodeColor.BLACK)); assertThat(tree.getRoot().getRightChild().getRightChild(), is(notNullValue())); assertThat(tree.getRoot().getRightChild().getRightChild().getValue(), is(15)); assertThat(tree.getRoot().getRightChild().getRightChild().getColor(), is(NodeColor.RED)); }