Treap extends AbstractSelfBalancingBinarySearchTree { @Override protected Node delete(Node deleteNode) { if (deleteNode != null) { Node replaceNode = rotateDown((TreapNode)deleteNode); super.delete(deleteNode); return replaceNode; } return null; }  @Override Node insert(int element);  }
@Test public void testDelete() { Treap treap = new Treap(); TreapNode root = new TreapNode(20, null, null, null, 100); TreapNode rootLeft = new TreapNode(15, root, null, null, 99); TreapNode rootRight = new TreapNode(25, root, null, null, 98); root.left = rootLeft; root.right = rootRight; TreapNode rootLeftLeft = new TreapNode(14, rootLeft, null, null, 97); TreapNode rootLeftRight = new TreapNode(17, rootLeft, null, null, 96); rootLeft.left = rootLeftLeft; rootLeft.right = rootLeftRight; treap.root = root; Node delete = treap.delete(20); Assert.assertEquals(delete.value, (Integer) 15); }