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 \(M\) operations take at most \(O(M \log N)\) time.
Important
It does not guarantee that all operations are \(O(\log N)\).
With this data structure, we are talking about amortized running time.
When a sequence of \(M\) operations have a total worst-case running time of \(O(M f(N))\), then the amortized running time is \(O(f(N))\).
To simplify, splay tree operations have an average running time of \(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 \(k_1\).
We can see the access path (dashed lined). So we need to rotate \(k_1\) and \(k_2\).
Then we rotate \(k_1\) and \(k_3\).
We continue with \(k_4\).
Finally we need a last rotation with \(k_5\).
Activity
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 \(M\) operations requiring \(\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 \(X\) be a non-root node on the access path.
If the parent of \(X\) is the root -> rotate \(X\) and the root.
Otherwise has both a parent \(P\) and a grandparent \(G\).
If \(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:
The zig-zig is a single rotation.
The following figure illustrates the zig-zig:
The idea is in the end very simple.
Activity
Take the previous example and apply the algorithm.
Draw the final graph
Is it balanced?
Important
A splay tree is not balanced and it is not the point!
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.
1 private:
2 struct SplayNode
3 {
4 Comparable element;
5 SplayNode *left;
6 SplayNode *right;
7 SplayNode *parent;
8
9 SplayNode( const Comparable & ele, SplayNode *lt, SplayNode *rt, SplayNode *p)
10 : element{ ele }, left{ lt }, right{ rt }, parent{ p } { }
11
12 };
I am giving you the header file.
Header file
1#ifndef SPLAY_TREE_H
2#define SPLAY_TREE_H
3
4#include <algorithm>
5#include <iostream>
6using namespace std;
7
8// SplayTree class
9
10template <typename Comparable>
11class SplayTree
12{
13 public:
14 SplayTree( );
15
16 ~SplayTree( );
17
18 const Comparable & findMin( ) const;
19
20 const Comparable & findMax( ) const;
21
22 bool contains( const Comparable & x ) const;
23
24 bool isEmpty( ) const;
25
26 void printTree( ) const;
27
28 void makeEmpty( );
29
30 void insert( const Comparable & x );
31
32 void remove( const Comparable & x );
33
34 private:
35 struct SplayNode
36 {
37 Comparable element;
38 SplayNode *left;
39 SplayNode *right;
40 SplayNode *parent;
41
42 SplayNode( const Comparable & ele, SplayNode *lt, SplayNode *rt, SplayNode *p)
43 : element{ ele }, left{ lt }, right{ rt }, parent{ p } { }
44
45 };
46
47 SplayNode *root;
48
49 void insert( const Comparable & x, SplayNode * & t, SplayNode * & p);
50
51 void remove( const Comparable & x, SplayNode * & t );
52
53 void splay( SplayNode * t );
54
55 SplayNode * findMin( SplayNode *t ) const;
56
57 SplayNode * findMax( SplayNode *t ) const;
58
59 bool contains( const Comparable & x, SplayNode *t ) const;
60
61 void makeEmpty( SplayNode * & t );
62
63 void printTree( SplayNode *t ) const;
64
65 void rotateWithLeftChild( SplayNode * k2 );
66
67 void rotateWithRightChild( SplayNode * k1 );
68
69 void doubleWithLeftChild( SplayNode * k3 );
70
71 void doubleWithRightChild( SplayNode * k1 );
72};
73
74#endif
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.
Activity
Implement the insertion function
void insert( const Comparable & x );.Consider the splay function already implemented:
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.
Activity
Implement the function
void splay( SplayNode * t ).