ScapegoatTree extends AbstractSelfBalancingBinarySearchTree { @Override public Node insert(int element) { Node inserted = super.insert(element); int height = getNodeHeight(inserted); if (height > getHAlpha()) { Node scapegoat = findScapegoatNode(inserted); Node scapegoatParent = scapegoat.parent; boolean scapegoatOnParentsLeft = scapegoatParent != null && scapegoatParent.left == scapegoat; Node rebuiltSubtree = rebuildTree(getSubtreeSize(scapegoat), scapegoat); rebuiltSubtree.parent = scapegoatParent; if (scapegoatParent != null) { if (scapegoatOnParentsLeft) { scapegoatParent.left = rebuiltSubtree; } else { scapegoatParent.right = rebuiltSubtree; } } if (scapegoat == root) { root = rebuiltSubtree; } maxSize = getSize(); } return inserted; } ScapegoatTree();  ScapegoatTree(double alpha); @Override Node insert(int element); @Override Node delete(int element);  }
@Test public void testInsertSortedDesc() { ScapegoatTree tree = new ScapegoatTree(); tree.insert(18); tree.insert(17); tree.insert(16); tree.insert(15); tree.insert(14); tree.insert(13); tree.insert(12); tree.insert(11); tree.insert(10); tree.insert(9); tree.insert(8); tree.insert(7); tree.insert(6); tree.insert(5); tree.insert(4); tree.insert(3); tree.insert(2); tree.insert(1); tree.printTree(); Assert.assertEquals(18, tree.size); Assert.assertEquals((Integer)12, tree.root.value); testTreeBSTProperties(tree.root); }
@Test public void testInsertSorted() { ScapegoatTree tree = new ScapegoatTree(); tree.insert(1); tree.insert(2); tree.insert(3); tree.insert(4); tree.insert(5); tree.insert(6); tree.insert(7); tree.insert(8); tree.insert(9); tree.insert(10); tree.insert(11); tree.insert(12); tree.insert(13); tree.insert(14); tree.insert(15); tree.insert(16); tree.insert(17); tree.insert(18); Assert.assertEquals(18, tree.size); Assert.assertEquals((Integer)5, tree.root.value); testTreeBSTProperties(tree.root); }