摘要：
1，Splay树的介绍
2，Splay树的旋转
3，Splay树的伸展
4，Splay树的分割
5，Splay树的合并
6，Splay树的插入
7，Splay树的删除
8，Splay树的查找
9，查找前驱和后继节点
10，查数值的排名
11，查排名对应的值
1，Splay树的介绍
伸展树(Splay Tree)是一种能够自平衡的《二叉搜索树》，它能在O(logn)的时间内完成插入、查找、修改和删除操作。它是由丹尼尔·斯莱托(Daniel Sleator)和罗伯特·塔扬(Robert Endre Tarjan)在1985年发明。
其中罗伯特·塔扬是1986年图灵奖得主，也是Tarjan算法的发明者，在我的另一个专栏《经典图论算法》中关于强连通分量，割点，割边等问题的求解都可以使用Tarjan算法。
假如要对一个二叉搜索树执行一系列的查找操作，为了使整个查找的时间复杂度尽可能小，那些被查频率比较高的节点应当处于靠近树根的位置。
于是在每次查找之后对树进行调整，把查找的节点移动到根节点，这就是伸展树。伸展树是一种自调整的二叉搜索树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点移到根节点。
我们先来看一下伸展树的节点类，这里我们假设树中允许有重复的节点，count就是记录重复节点的个数，size 是记录以当前节点为根的子树中节点的个数。parent记录的是父节点，对于伸展树的伸展有两种方式，一直是自下往上的 ，一直是自上往下的，如果是自上往下进行伸展，则不需要记录父节点。
Java 代码：
// 节点类
class SplayNode {
int val;// 节点值
int count = 1;// 该节点出现的次数，这里允许添加重复的值。
int size = 1;// 以当前节点为根的子树中节点个数。
// 父节点，左子树和右子树
SplayNode parent, left, right;
SplayNode(int val) {
this.val = val;
}
}
SplayNode root;// 根节点
// 获取以当前节点为根的子树中节点个数。
private int getTreeSize(SplayNode node) {
return node == null ? 0 : node.size;
}
// 更新节点个数
private void updateSize(SplayNode node) {
if (node == null) return;
// 以当前节点为根节点的子树中节点个数。
node.size = getTreeSize(node.left) + getTreeSize(node.right) + node.count;
}
C++ 代码：
struct SplayNode {
int val;// 节点值
int count = 1;// 该节点出现的次数，这里允许添加重复的值。
int size = 1;// 以当前节点为根的子树中节点个数。
// 父节点，左子树和右子树
SplayNode *parent = nullptr, *left = nullptr, *right = nullptr;
SplayNode(int val) : val(val) {}
};
SplayNode *root = nullptr;// 根节点
// 获取节点个数
int getTreeSize(SplayNode *node) {
return node == nullptr ? 0 : node->size;
}
// 更新节点个数
void updateSize(SplayNode *node) {
if (node == nullptr) return;
// 以当前节点为根节点的子树中节点个数。
node->size = getTreeSize(node->left) + getTreeSize(node->right) + node->count;
}
2，Splay树的旋转
旋转分为两种，分别是左旋和右旋，因为Splay树就是一颗二叉搜索树，所以它的旋转和我们前面讲的《AVL树》,《Treap树》的旋转都是一样的，旋转操作并不会改变二叉搜索树的特性，我们这里再来看一下。
这里要注意，如果伸展树是自下往上伸展的，每个节点都会有父节点（根节点除外），旋转的时候要注意父节点的改变。
Java 代码：
// 对节点node左旋
private void leftRotate(SplayNode node) {
SplayNode right = node.right;// 左旋操作肯定有右子树
node.right = right.left;
if (right.left != null)
right.left.parent = node;
// right即将成为该子树的根节点，这里更改right的父节点。
right.parent = node.parent;
if (node.parent != null) {
if (node == node.parent.left)
node.parent.left = right;
else
node.parent.right = right;
}
right.left = node;
node.parent = right;
updateSize(node);// 更新节点node的节点个数
updateSize(right);// 更新节点right的节点个数
}
// 对节点node右旋
private void rightRotate(SplayNode node) {
SplayNode left = node.left;// 右旋肯定有左子树
node.left = left.right;
if (left.right != null)
left.right.parent = node;
// left即将成为该子树的根节点，这里更改left的父节点。
left.parent = node.parent;
if (node.parent != null) {
if (node == node.parent.left)
node.parent.left = left;
else
node.parent.right = left;
}
left.right = node;
node.parent = left;
updateSize(node);// 更新节点node的节点个数
updateSize(left);// 更新节点left的节点个数
}
C++ 代码：
// 对节点node左旋
void leftRotate(SplayNode *node) {
SplayNode *right = node->right;// 左旋操作肯定有右子树
node->right = right->left;
if (right->left)
right->left->parent = node;
// right即将成为该子树的根节点，这里更改right的父节点。
right->parent = node->parent;
if (node->parent) {
if (node == node->parent->left)
node->parent->left = right;
else
node->parent->right = right;
}
right->left = node;
node->parent = right;
updateSize(node);// 更新节点node的节点个数
updateSize(right);// 更新节点right的节点个数
}
// 对节点node右旋
void rightRotate(SplayNode *node) {
SplayNode *left = node->left;// 右旋肯定有左子树
node->left = left->right;
if (left->right)
left->right->parent = node;
// left即将成为该子树的根节点，这里更改left的父节点。
left->parent = node->parent;
if (node->parent) {
if (node == node->parent->left)
node->parent->left = left;
else
node->parent->right = left;
}
left->right = node;
node->parent = left;
updateSize(node);// 更新节点node的节点个数
updateSize(left);// 更新节点left的节点个数
}
3，Splay树的伸展
Splay树的伸展就是把一个节点旋转到根节点，伸展有自下往上和自上往下两种方式，这里我们选择的是自下往上的方式，自上往下的伸展方式之后我们还会在介绍。
如果是单旋，也就是每次旋转一次，当树是极度不平衡的时候，旋转之后还是不平衡，如下图所示。
如果是双旋，也就是每次旋转两次，当树是极度不平衡的时候，旋转之后，不仅可以将该节点伸展至树根，而且同时可使树的高度接近于减半。
所以在Spaly树中我们选择的都是双旋，这里的双旋分为三种情况：
1，待旋转节点 x 的父节点是根节点
2，待旋转节点 x 的父节点以及父节点的父节点在一条线上。
3，待旋转节点 x 的父节点以及父节点的父节点不在一条线上。
