java splay tree program

Splay trees balance trees in a different way from AVL trees. An AVL tree always has height O(log n) meaning that every operation will require O(log n) time which is as good as you can possibly expect fro a BST. Splay trees allow some operations to take much longer, but the slow operations are balanced out by a sufficient number of faster ones. This is referred to as amortized complexity where over a total of n operations on a splay tree the average amount of time spent on each operation is O(log n). You will see an example of this later.

Pretty much everything you need to know about splay trees is here. You only need to read the first 3 sections. Some important points you will read are: (1) It is possible to have a splay tree with height O(n) but on average the height will be O(log n). (2) Splay trees require no extra storage so they are space efficient. AVL trees require a balance factor in each node, so this less true for AVL trees. (3) Somewhat surprisingly, an element after insertion is moved (splayed) to the root of the tree. His may sound inefficient but it is during this splaying process that the tree is balanced. (4) The main operations performed while balancing a splay tree are zig-zig and zig-zag. It’s also possible for there to be a single zig when the element moves to the root of the tree.

Looking at section 3 on operations, the simple zig step should look familiar to you. It is a simple right or left rotation. So, looking at the zig step diagram you can see that moving x to the root is just a right rotation.

When splaying up from further down the tree we always go two steps at once. If the node being splayed up is either left–left or right–right of its grandparent then a zig-zig splay is performed. Looking at the zig-zig diagram you can see to accomplish this you must first rotate g to the right, then rotate p to the right, bringing x two levels higher in the tree. If you do it in the other order you will not end up with the same tree. I suggest you try it to confirm what I say.

If when splaying up a node it is either left–right or right–left of the grandparent then a zig-zag is performed. Looking at the zig-zag diagram we this this is done by rotating p left, then g right. Even though both of these were two separate single rotations, to help remember the algorithm I suggest you think of them both as different but easy to remember double rotations – just as you should have done with AVL trees.

Here is an example with some explanations.

Start with an empty tree.

Now insert 10. This is a 1-node tree, 10 is already at the root so no splaying necessary.

10

Insert 20. First insert as you would with any BST, giving

10

20

Now splay 20 to the root. It is just one step away, so a zig brings it to the root.

20

10

Now insert 30.

20 10 30

Again, it is one step from the root, so zig it up.

30

20

10

Now insert 40, 50, 60, 70, 80 and it is easy to see that the resulting splay tree will be

80

70

60

50

40

30

20

10

This takes us to one of the fundamental facts of splay trees. Notice this is a worst case tree. If we continued this process for n insertions we would have a tree of height n. But the good news is that is was very fast to build this tree. Each insertion only took 1 step instead of O(log n). This means we’re way ahead of the game. We’ve been averaging constant time instead of O(log n). Now let’s insert something under 10. This is a worst case insertion so it will hurt our average, but something else good happens, too. Inserting 15 will give us this tree before we do any splaying.

80

70

60

50

40

30

20

10

15

Now we must splay 15 to the root. We will do this step by step. Look at the grandparent of 15, 20. 15 is left–right under 20, so we perform a zig-zag.

80

70

60

50

40

30

15

10 20

Now look at the grandparent of 15 to figure out the next splay step. It is 40, 15 is left–left so we perform a zig-zig.

80

70

60

50

15

10 30

20 40

Similarly, the grandparent is 60, so another zig-zig step.

80

70

15

10 50

30 60

20 40

And now one more ziz-zig step to the root, gives us this.

15

10 70

50 80

30 60

20 40

This demonstrates the other fundamental fact of splay trees, i.e., bad splay trees do not stay bad for long. Even though the tree we started with was bad and insertion took a long time, the new tree is half the height of the original one. So even in the worst case the next insertion will only take half as long as the previous one. The mathematical details are a bit complicated, but this example should help convince you that splay trees really do behave as I promised.

One more example. Let’s insert 35 into the previous tree and watch how it splays to the root. Insert 35.

15

10 70

50 80

30 60

20 40

35

Zig-zag to where 30 is.

15

10 70

50 80

35 60

30 40

20

Zig-zig to where 70 is.

15

10 35

30 50

20 40 70

60 80

No grandparent. Just zig to the root.

35

15 50

10 30 40 70

20 60 80

Try some on your own to be sure you understand. You can check your work by using the following helpful animation: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html