@Test public void testSequentialInsetAndRemove() { RedBlackBST<Integer, Integer> expect = new RedBlackBST<>(); BST<Integer, Integer> bst = new RedBlackBSTWithNoExtraMemory<>(); for (int i = 0; i < N; i++) { expect.put(i, i); bst.put(i, i); } for (int i = 0; i < N; i++) { assertEquals(expect.get(i), bst.find(i)); } for (int i = N - 1; i >= N / 2; i--) { expect.delete(i); bst.remove(i); assertEquals(expect.get(i), bst.find(i)); } for (int i = N / 2 - 1; i >= 0; i--) { assertEquals(expect.get(i), bst.find(i)); } for (int i = 0; i < N / 2; i++) { expect.delete(i); bst.remove(i); assertEquals(expect.get(i), bst.find(i)); } assertTrue(bst.isEmpty()); }
@Override public boolean remove(Key key) { if (key == null) throw new IllegalArgumentException("key not null"); if (!contains(key)) return false; if (!isRed(root.left) && !isRed(root.right)) setRed(root); boolean res = super.remove(key); if (!isEmpty()) setBlack(root); return true; }
RedBlackBSTWithNoExtraMemory extends BST<Key, Val> { @Override public boolean remove(Key key) { if (key == null) throw new IllegalArgumentException("key not null"); if (!contains(key)) return false; if (!isRed(root.left) && !isRed(root.right)) setRed(root); boolean res = super.remove(key); if (!isEmpty()) setBlack(root); return true; } }
RedBlackBSTWithNoExtraMemory extends BST<Key, Val> { @Override public boolean remove(Key key) { if (key == null) throw new IllegalArgumentException("key not null"); if (!contains(key)) return false; if (!isRed(root.left) && !isRed(root.right)) setRed(root); boolean res = super.remove(key); if (!isEmpty()) setBlack(root); return true; }  }
RedBlackBSTWithNoExtraMemory extends BST<Key, Val> { @Override public boolean remove(Key key) { if (key == null) throw new IllegalArgumentException("key not null"); if (!contains(key)) return false; if (!isRed(root.left) && !isRed(root.right)) setRed(root); boolean res = super.remove(key); if (!isEmpty()) setBlack(root); return true; }  @Override boolean remove(Key key); }
RedBlackBSTWithNoExtraMemory extends BST<Key, Val> { @Override public boolean remove(Key key) { if (key == null) throw new IllegalArgumentException("key not null"); if (!contains(key)) return false; if (!isRed(root.left) && !isRed(root.right)) setRed(root); boolean res = super.remove(key); if (!isEmpty()) setBlack(root); return true; }  @Override boolean remove(Key key);  }