对伸展树的伸展操作理解
伸展树的旋转
zig-zig旋转（一字型旋转）
zig-zag旋转（之字形旋转）
所有的旋转无外乎这两种，但是最大的区别就是Z比Y是大还是小，也就是书上会说的要查找的节点Z需要比较其父结点P(z)以及祖父结点G(z)，如果比同时比P(z)和G(z)大（小）的话就是zig-zig旋转，如果比P(z)和G(z)一个大一个小的话就是zig-zag旋转
挂到L树
- 挂到L树下的结点都是比要查找的Z结点小的，先挂上去的是最小的，后挂上去的比先挂上去的大
- 因为后挂到L上的结点比先挂上去的大，所以插入位置应该是在L最大结点的右结点上
- 第一次就挂到L的右孩子的位置上
- 第二次就挂到L最大结点的右孩子上，以此类推
挂到R树
- 挂到R树下的结点都是比要查找的Z结点大的，后挂上去的也是比先挂上去的小
- 第一次挂到R的左孩子位置上
- 第二次挂到R上的时候，新移动过去的2-3个结点组成的树的根结点一定是R的左孩子，需要一次zig-zig旋转
连接
- 需要访问结点的左子树挂到L的最大结点的右孩子位置上
- 需要访问结点的右子树挂到R的最小结点的左孩子位置上
代码实现(不全对)
private SplayNode<T> splay(SplayNode<T> tree, T key) {
if (tree == null)
return tree;
SplayNode<T> R = new SplayNode<>();
SplayNode<T> L = new SplayNode<>();
SplayNode<T> cur;
for (; ; ) {
int cmp = key.compareTo(tree.key);
if (cmp < 0) {
if (tree.left == null)
break;
cmp = key.compareTo(tree.left.key);
//在左孙子上
if (cmp < 0) {
cur = tree.left;
tree.left = cur.right;
cur.right = tree;
tree = cur.left;
cur.left = R.left;
R.left = cur;
} else {
SplayNode<T> temp = tree.left;
tree.left = R.left;
R.left = tree;
tree = temp;
}
} else if (cmp > 0) {
if (tree.right == null)
break;
cmp = key.compareTo(tree.right.key);
if (cmp > 0) {
cur = tree.right;
tree.right = cur.left;
cur.left = tree;
tree = cur.right;
//断开和tree的联系，挂到L上去
cur.right = null;
SplayNode<T> leftBiggest = L;
while (leftBiggest.right != null)
leftBiggest = leftBiggest.right;
leftBiggest.right = cur;
} else {
SplayNode<T> temp = tree.right;
tree.right = null;
SplayNode<T> leftBiggest = L;
while (leftBiggest.right != null)
leftBiggest = leftBiggest.right;
leftBiggest.right = tree;
tree = temp;
}
} else {
break;
}
}
SplayNode<T> A = tree.left;
SplayNode<T> B = tree.right;
SplayNode<T> tmp;
tmp = L;
while (tmp.right != null)
tmp = tmp.right;
tmp.right = A;
tmp = R;
while (tmp.left != null)
tmp = tmp.left;
tmp.left = B;
tree.right = R.left;
tree.left = L.right;
return tree;
}以上代码基本实现，对于结点不存在的查找可能会出现崩溃~写此仅用来理解
代码理解（网上标准）
private SplayNode<T> splay2(SplayNode<T> tree, T key) {
if (tree == null)
return null;
SplayNode<T> N = new SplayNode<>();
SplayNode<T> l = N;
SplayNode<T> r = N;
SplayNode<T> cur;
int cmp;
while (true) {
cmp = key.compareTo(tree.key);
if (cmp < 0) {
if (tree.left == null)
break;
if (key.compareTo(tree.left.key) < 0) {
cur = tree.left;
tree.left = cur.right;
cur.right = tree;
tree = cur;
if (tree.left == null)
break;
}
r.left = tree;
r = tree;
tree = tree.left;
} else if (cmp > 0) {
if (tree.right == null)
break;
if (key.compareTo(tree.right.key) > 0) {
cur = tree.right;
tree.right = cur.left;
cur.left = tree;
tree = cur;
if (tree.right == null)
break;
}
l.right = tree;
l = tree;
tree = tree.right;
} else
break;
}
l.right = tree.left;
r.left = tree.right;
tree.left = N.right;
tree.right = N.left;
return tree;
}总结：根据前面的理解
l.right = tree.left; r.left = tree.right; tree.left = N.right; tree.right = N.left;
这里就是连接的过程整个代码中最重要的是两个部分要理解
SplayNode<T> N = new SplayNode<>(); SplayNode<T> l = N; SplayNode<T> r = N;
这里是一个引用的指向（具体可以去查询Java中对象与引用的关系），l和r以及N都是指向同一个对象（至少初始的时候是的）直到
l.right = tree; l = tree; tree = tree.right;
r.left = tree; r = tree; tree = tree.left
以其中一个分析，l.right = tree，把旋转好的新树挂到l的右孩子上（与此同时，r N的右孩子也都有值了！！！），l = tree,l指向tree，而这时候（N r的右孩子也都成为了l！！！）