正文
伸展树的旋转
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!!!)