What is Splay Tree?#

Useful Link:

Another blog about Balance tree

The most common two balance trees is Splay and Treap. I already have introduced treap before so this article let’s learn Splay.

Unlike Treap, the basic operation of Splay is rotate. By rotating, we can let the node we want move to root. The core idea of Splay is using Splay function to let the node we recently visited depth get shallower.

What is its function?#

It’s a Balanced BST (Binary Search Tree), which can search, insert, delete a node in $O(\log n)$ . And it can promise the tree balance.

Before explain the core operation Splay, You need know some basic sturcture and checking function.

Basic Structure#

The example code in this article will using array to simulate pointer, the version more save will publish later.

Variable Name	Meaning
`rt`	Id of root
`id`	the quantity of used node
`fa[i]`	father of node $i$
`ch[i][0/1]`	left/right children of node $i$
`val[i]`	Value of node $i$
`cnt[v]`	The times value $v$ appear
`sz[i]`	The size of sub tree which root is $i$

Set all value to $0$ when initial.

Checking Function#

1
bool dir(int x) {
2
    return x == ch[fa[x]][1]; // if x is left son return 0, or return 1.
3
}
4
void pushUp(int x) {
5
    sz[x] = cnt[x] + sz[ch[x][0]] + sz[ch[x][1]];
6
    // Update all information after changing position of node.
7
}

How to Rotate?#

First we should know how the basic operation, rotate work.

This image told us how to rotate node $x$ in a tree. It’s not difficlut to find that the inorder traversal of this tree have no changes. So rotate can not change the BST property of Splay tree. And it also a way to maintain the time complexity (or length) of Splay tree.

1
void rotate(int x) {
2
    int y = fa[x], z = fa[y];
3
    bool r = dir(x);
4
    ch[y][r] = ch[x][!r];
5
    ch[x][!r] = y;
6
    if (z) ch[z][dir(y)] = x;
7
    if (ch[y][r]) fa[ch[y][r]] = y;
8
    fa[y] = x;
9
    fa[x] = z;
10
    push_up(y);
11
    push_up(x);
12
}

Observe the picture I drawed can understand this function.

How to Splay?#

Then, many rotate operation become a splay operation. There are some basic model when doing splay : Zig, Zig-Zig, Zig-Zag.

We define function Splay(x, k) denotes let node $x$ move up until be son of node $k$ .

Without thinking, do nothing if $x = k$ .

Zig#

This situation when $x$ is son of $k$ . Just rotate $x$ is okay.

In splay tree, we only do left rotate operation when $x$ is right son, and only do right rotate operation when $x$ is left son. That can lead us using one function to realize Splay(x,k) in code.

Zig-Zig#

This situation when $x$ and $fa_x$ is son in same side of their father. We should first rotate $fa_x$ then rotate $x$ , we can do a little contrast.

Why not rotate $x$ twice? That because it will change the relative position of $fa_x$ and $x$ . Using correct Zig-Zig plan can let the final struction also Zig-Zig, and this plan also get best time complexity when potential method

Zig-Zag#

This situation when $x$ and $fa_x$ is son in different side of their father. We can rotate $x$ twice in this situation.

We can found the height of this tree decrease.

Code#

Then we know all the operator in each situation we can write the code:

1
void splay(int& z, int x) {
2
    int w = fa[z];
3
    for (int y; (y = fa[x]) != w; rotate(x)) { // whatever which situation, the last operation is rotate x
4
        if (fa[y] != w)  // if zigzig or zigzag
5
            rotate(dir(x) == dir(y) ? y : x); // check it's zigzig or zigzag
6
    }
7
    z = x;
8
}

How Splay Tree Do Basic Operation of Balance Tree?#

And below is how splay to realize some classic operation.

Find with Value#

Because Splay Tree also a BST, so the process find a node with value is same as BST, a only difference is we need splay node we found to root.

1
// find value v; if not found, end at last accessed node
2
void find(int& z, int v) {
3
    int x = z, y = 0; // x: current node, y: last visited node
4
    for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
5
    // traverse BST; stop when found or reach null
6
    splay(z, x ? x : y);
7
    // splay the found node, or the last accessed node to root
8
}

Find with Rank#

Same as treap too.

1
void loc(int& z, int k) {
2
    int x = z;
3
    for (;;) {
4
        if (sz[ch[x][0]] >= k) {
5
            x = ch[x][0];
6
        } else if (sz[ch[x][0]] + cnt[x] >= k) {
7
            break;
8
        } else {
9
            k -= sz[ch[x][0]] + cnt[x];
10
            x = ch[x][1];
11
        }
12
    }
13
    splay(z, x);
14
}

Insert a Value#

1
void insert(int v) { // insert value v
2
    int x = rt, y = 0;
3
    for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
4
    // find a node with value
5
    if (x) { // if already have this node (isn't empty node & value is wanted)
6
        ++cnt[x];
7
        ++sz[x];
8
    } else { // is a empty node
9
        x = ++id; // new node & initialize
10
        val[x] = v;
11
        cnt[x] = sz[x] = 1;
12
        fa[x] = y;
13
        if (y) ch[y][v > val[y]] = x; // insert it
14
    }
15
    splay(rt, x); // splay it to root
16
}

Merge Two Slay Trees#

This operation really like treap.

1
int merge(int x, int y) {
2
    if (!x || !y) return x | y;
3
    loc(y, 1); // find the minimum of tree y, it must have no left children
4
    ch[y][0] = x;
5
    fa[x] = y;
6
    push_up(y);
7
    return y; // return now root
8
}

Remove a Value#

1
bool remove(int v) {
2
    find(rt, v);
3
    if (!rt || val[rt] != v) return false;
4
    --cnt[rt];
5
    --sz[rt];
6
    if (!cnt[rt]) {
7
        int x = ch[rt][0];
8
        int y = ch[rt][1];
9
        fa[x] = fa[y] = 0;
10
        rt = merge(x, y);
11
    }
12
    return true;
13
}

Query Rank#

1
int find_rank(int v) {
2
    find(rt, v); // we cannot sure result find returned must greater or less than v when v is not exist
3
    return sz[ch[rt][0]] + (val[rt] < v ? cnt[rt] : 0) + 1;
4
}

Query Prevent and Next#

1
int find_prev(int v) {
2
    find(rt, v); // rt exist and val[rt] less than v
3
    if (rt && val[rt] < v) return val[rt];
4
    int x = ch[rt][0]; // this situation when v exist or have a node which greater than v
5
    if (!x) return -1; // so check now node's left subtree
6
    for (; ch[x][1]; x = ch[x][1]); // the maximum of left subtree is rightest node
7
    splay(rt, x);
8
    return val[rt];
9
}
10

11
// same with find_prev
12
int find_next(int v) {
13
    find(rt, v);
14
    if (rt && val[rt] > v) return val[rt];
15
    int x = ch[rt][1];
16
    if (!x) return -1;
17
    for (; ch[x][0]; x = ch[x][0]);
18
    splay(rt, x);
19
    return val[rt];
20
}

All Code#

From OI wiki.

1
#include <iostream>
2

3
constexpr int N = 2e6;
4
int id, rt;
5
int fa[N], val[N], cnt[N], sz[N], ch[N][2];
6

7
bool dir(int x) { return x == ch[fa[x]][1]; }
8

9
void push_up(int x) { sz[x] = cnt[x] + sz[ch[x][0]] + sz[ch[x][1]]; }
10

11
void rotate(int x) {
12
  int y = fa[x], z = fa[y];
13
  bool r = dir(x);
14
  ch[y][r] = ch[x][!r];
15
  ch[x][!r] = y;
16
  if (z) ch[z][dir(y)] = x;
17
  if (ch[y][r]) fa[ch[y][r]] = y;
18
  fa[y] = x;
19
  fa[x] = z;
20
  push_up(y);
21
  push_up(x);
22
}
23

24
void splay(int& z, int x) {
25
  int w = fa[z];
26
  for (int y; (y = fa[x]) != w; rotate(x)) {
27
    if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
28
  }
29
  z = x;
30
}
31

32
void find(int& z, int v) {
33
  int x = z, y = fa[x];
34
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
35
  splay(z, x ? x : y);
36
}
37

38
void loc(int& z, int k) {
39
  int x = z;
40
  for (;;) {
41
    if (sz[ch[x][0]] >= k) {
42
      x = ch[x][0];
43
    } else if (sz[ch[x][0]] + cnt[x] >= k) {
44
      break;
45
    } else {
46
      k -= sz[ch[x][0]] + cnt[x];
47
      x = ch[x][1];
48
    }
49
  }
50
  splay(z, x);
51
}
52

53
int merge(int x, int y) {
54
  if (!x || !y) return x | y;
55
  loc(y, 1);
56
  ch[y][0] = x;
57
  fa[x] = y;
58
  push_up(y);
59
  return y;
60
}
61

62
void insert(int v) {
63
  int x = rt, y = 0;
64
  for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
65
  if (x) {
66
    ++cnt[x];
67
    ++sz[x];
68
  } else {
69
    x = ++id;
70
    val[x] = v;
71
    cnt[x] = sz[x] = 1;
72
    fa[x] = y;
73
    if (y) ch[y][v > val[y]] = x;
74
  }
75
  splay(rt, x);
76
}
77

78
bool remove(int v) {
79
  find(rt, v);
80
  if (!rt || val[rt] != v) return false;
81
  --cnt[rt];
82
  --sz[rt];
83
  if (!cnt[rt]) {
84
    int x = ch[rt][0];
85
    int y = ch[rt][1];
86
    fa[x] = fa[y] = 0;
87
    rt = merge(x, y);
88
  }
89
  return true;
90
}
91

92
int find_rank(int v) {
93
  find(rt, v);
94
  return sz[ch[rt][0]] + (val[rt] < v ? cnt[rt] : 0) + 1;
95
}
96

97
int find_kth(int k) {
98
  if (k > sz[rt]) return -1;
99
  loc(rt, k);
100
  return val[rt];
101
}
102

103
int find_prev(int v) {
104
  find(rt, v);
105
  if (rt && val[rt] < v) return val[rt];
106
  int x = ch[rt][0];
107
  if (!x) return -1;
108
  for (; ch[x][1]; x = ch[x][1]);
109
  splay(rt, x);
110
  return val[rt];
111
}
112

113
int find_next(int v) {
114
  find(rt, v);
115
  if (rt && val[rt] > v) return val[rt];
116
  int x = ch[rt][1];
117
  if (!x) return -1;
118
  for (; ch[x][0]; x = ch[x][0]);
119
  splay(rt, x);
120
  return val[rt];
121
}
122

123
int main() {
124
  int n;
125
  std::cin >> n;
126
  for (; n; --n) {
127
    int op, x;
128
    std::cin >> op >> x;
129
    switch (op) {
130
      case 1:
131
        insert(x);
132
        break;
133
      case 2:
134
        remove(x);
135
        break;
136
      case 3:
137
        std::cout << find_rank(x) << '\n';
138
        break;
139
      case 4:
140
        std::cout << find_kth(x) << '\n';
141
        break;
142
      case 5:
143
        std::cout << find_prev(x) << '\n';
144
        break;
145
      case 6:
146
        std::cout << find_next(x) << '\n';
147
        break;
148
    }
149
  }
150
  return 0;
151
}