SplayTree extends AbstractSelfBalancingBinarySearchTree { protected void splay(Node node) { while (node != root) { Node parent = node.parent; if (parent.equals(root)) { if (node.equals(parent.left)) { rotateRight(parent); } else if (node.equals(parent.right)) { rotateLeft(parent); } break; } else { Node grandParent = parent.parent; boolean nodeAndParentLeftChildren = node.equals(parent.left) && parent.equals(grandParent.left); boolean nodeAndParentRightChildren = node.equals(parent.right) && parent.equals(grandParent.right); boolean nodeRightChildParentLeftChild = node.equals(parent.right) && parent.equals(grandParent.left); boolean nodeLeftChildParentRightChild = node.equals(parent.left) && parent.equals(grandParent.right); if (nodeAndParentLeftChildren) { rotateRight(grandParent); rotateRight(parent); } else if (nodeAndParentRightChildren) { rotateLeft(grandParent); rotateLeft(parent); } else if (nodeRightChildParentLeftChild) { rotateLeft(parent); rotateRight(grandParent); } else if (nodeLeftChildParentRightChild) { rotateRight(parent); rotateLeft(grandParent); } } } }  @Override Node search(int element); @Override Node insert(int element); @Override Node delete(int element);  }
@Test public void testSplayZig() { SplayTree splayTree = new SplayTree(); Node root = new Node(15, null, null, null); splayTree.root = root; Node left = new Node(10, root, null, null); root.left = left; splayTree.splay(left); Assert.assertEquals(splayTree.root.value, (Integer) 10); Assert.assertEquals(splayTree.root.right.value, (Integer) 15); splayTree.splay(splayTree.root.right); Assert.assertEquals(splayTree.root.value, (Integer) 15); Assert.assertEquals(splayTree.root.left.value, (Integer) 10); }
@Test public void testSplayZigZig() { SplayTree splayTree = new SplayTree(); Node root = new Node(15, null, null, null); splayTree.root = root; Node left = new Node(10, root, null, null); Node leftleft = new Node(5, left, null, null); left.left = leftleft; root.left = left; splayTree.splay(leftleft); Assert.assertEquals(splayTree.root.value, (Integer) 5); Assert.assertEquals(splayTree.root.right.value, (Integer) 10); Assert.assertEquals(splayTree.root.right.right.value, (Integer) 15); splayTree.splay(splayTree.root.right.right); Assert.assertEquals(splayTree.root.value, (Integer) 15); Assert.assertEquals(splayTree.root.left.value, (Integer) 10); Assert.assertEquals(splayTree.root.left.left.value, (Integer) 5); }
@Test public void testSplayZigZag() { SplayTree splayTree = new SplayTree(); Node root = new Node(15, null, null, null); splayTree.root = root; Node left = new Node(10, root, null, null); Node leftright = new Node(12, left, null, null); left.right = leftright; root.left = left; splayTree.splay(leftright); Assert.assertEquals(splayTree.root.value, (Integer) 12); Assert.assertEquals(splayTree.root.right.value, (Integer) 15); Assert.assertEquals(splayTree.root.left.value, (Integer) 10); splayTree.root.right.left = new Node(13, splayTree.root.right, null, null); splayTree.splay(splayTree.root.right.left); Assert.assertEquals(splayTree.root.value, (Integer) 13); Assert.assertEquals(splayTree.root.left.value, (Integer) 12); Assert.assertEquals(splayTree.root.right.value, (Integer) 15); }