*********************
Topic 5 - Splay Trees
*********************

We will see another simple binary search tree, the **splay tree**.

Principle
=========

The objective of the splay trees is to guarantee that any sequences of :math:`M` operations take at most :math:`O(M \log N)` time.

.. important::

    It does not guarantee that all operations are :math:`O(\log N)`.

With this data structure, we are talking about **amortized** running time.

When a sequence of :math:`M` operations have a total worst-case running time of :math:`O(M f(N))`, then the amortized running time is :math:`O(f(N))`.

To simplify, splay tree operations have an average running time of :math:`O(\log N)`.

How does it work?
-----------------

The basic idea is very simple:

*  After a node is accessed, the node is pushed to the root using AVL tree rotations.
*  The AVL rotations will balance the tree, making future access faster.

.. note::

    In practice, when a node is accessed, it is likely it will be accessed again.

Ok, but AVL trees are doing the same thing!
-------------------------------------------

Yes, but...

Splay trees don't require to maintain the height or balance information!

It simplifies the code and save space in memory.

A first simple idea
===================

Now, we know that we need to apply rotations similarly to the AVL trees.

We could just apply simple rotation bottoms up!

Consider the following example. We want to find :math:`k_1`.

.. figure:: ../img/topic5/first_idea_01.*
    :align: center

We can see the access path (dashed lined). So we need to rotate :math:`k_1` and :math:`k_2`.

.. figure:: ../img/topic5/first_idea_02.*
    :align: center

Then we rotate :math:`k_1` and :math:`k_3`.

.. figure:: ../img/topic5/first_idea_03.*
    :align: center


We continue with :math:`k_4`.

.. figure:: ../img/topic5/first_idea_04.*
    :align: center

Finally we need a last rotation with :math:`k_5`.

.. figure:: ../img/topic5/first_idea_05.*
    :align: center


.. admonition:: Activity
    :class: warning

    *  Observe the tree after all the rotations.
    *  Does it do what we want?
    *  Is the tree balanced?

It is possible to prove that there is a sequence of :math:`M` operations requiring :math:`\Omega(M\times N)` time.


Splaying
========

Clearly, the previous strategy is not working as expected.

Splay trees are implementing the **splaying strategy**.

We are still rotating along the path to the root, but we are more selective hon the rotation type.

Let :math:`X` be a non-root node on the access path.

*  If the parent of :math:`X` is the root -> rotate :math:`X` and the root.
*  Otherwise has both a parent :math:`P` and a grandparent :math:`G`.

   *  If :math:`X` is an internal node -> this is the **zig-zag** case.
   *  Otherwise -> this is the **zig-zig** case.

The zig-zag is a double rotation like with the AVL trees.

The following figure illustrates the zig-zag:

.. figure:: ../img/topic5/FG_04_048.*
    :align: center

The zig-zig is a single rotation.

The following figure illustrates the zig-zig:

.. figure:: ../img/topic5/FG_04_049.*
    :align: center

The idea is in the end very simple.

.. admonition:: Activity
    :class: warning

    *  Take the previous example and apply the algorithm.

    .. figure:: ../img/topic5/first_idea_01.*
        :align: center

    *  Draw the final graph
    *  Is it balanced?


.. important::

    A splay tree is not balanced and it is not the point!

    .. figure:: ../img/topic5/splay_03.*
        :align: center

Implementation
==============

After seeing BST and AVL trees, the operation of the Splay trees should not be an issue.

.. important::

    It is recommended to implement iterative functions to splay trees.

Structure
---------

As we will have an iterative approach, a node needs to keep a pointer to its parent.

.. literalinclude:: ../code/topic5/SplayTree.hpp
    :language: cpp
    :linenos:
    :lines: 34-45

I am giving you the header file.

.. admonition:: Header file
    :class: dropdown

    .. literalinclude:: ../code/topic5/SplayTree.hpp
        :language: cpp
        :linenos:
        



Inserting
---------

The insertion is working as in AVL tree, but instead of balancing after inserting the node you splay.

You splay only once, just after inserting.

.. admonition:: Activity
    :class: warning

    *  Implement the insertion function :code:`void insert( const Comparable & x );`.
    *  Consider the splay function already implemented: :code:`void splay( SplayNode * t );`

Deletion
--------

The idea for deleting a node is the following:

*  Finding the node.
*  Splay the node to put it at the root.
*  Remove the node, so it gives you two subtrees left and right.
*  Find the maximum element in the left subtree.
*  Splay it, now link the right subtree to the right element of the node (that should be empty)

Splay
-----

We already discussed how the function is working.

.. admonition:: Activity
    :class: warning

    *  Implement the function :code:`void splay( SplayNode * t )`.