Splay trees – a reminder

I am very stupid where Computer Science is concerned, and my strength as a tutor is that I can emulate on any topic the stupidity my pupils will feel in the exam room, yet come up with strategies to cope with it. On that note, what follows is a personal reminder about splay trees.

The crucial point is that the result of a zig-zig move is different from what would be achieve with pointer rotations. If we start the move (splaying 5) with the tree on the left, then what we get is the tree on the right.

       /        |        /
      7         |       5
     / \        |      / \
    6   D       |     A   6
   / \          |        / \
  5   C         |       B   7
 / \            |          / \
A   B           |         C   D

On the other hand, two pointer rotations act like this:

       /        |        /      |       /
      7         |       7       |      5
     / \        |      / \      |     / \
    6   D       |     5   D     |    A   7
   / \          |    / \        |       / \
  5   C         |   A   6       |      6   D
 / \            |      / \      |     / \
A   B           |     B   C     |    B   C

Although at first sight the result of the pointer rotations looks less "linear", performing pointer rotations to raise 1 along a long spine results in a tree like the left one in an intermediate step:

            /     |            /
           7      |           7
          /       |          /
         6        |         6
        /         |        /
       1          |       1
        \         |        \
         5        |         4
        /         |        / \
       4          |       3   5
      /           |        \
     3            |         2
    /             |
   2              |

The pattern is going to continue, until 1 at the root has 7 as its right child, and everything else hanging in a long chain to its left. On the other hand, zig-zig steps result in the picture at the right, with little tufts created and the chain length halved.