数据结构基础14———非线性数据结构之自平衡二叉查找树之伸展树
伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊O(log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。
在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
场景：
继AVL树之后，我们给出了2-3树和红黑树。虽然红黑树将2-3树的实现变成了二叉查找树结构，但对于红黑树本身其实还是是引入新的信息表明红还是黑色，并不够纯粹。红红黑黑花里胡哨的，强迫症又犯了怎么办？我们希望要一个纯粹的二叉树
实现而不需要去管这些红黑颜色，不需要去保存额外的信息，有没有其他的方案呢？
伸展树的出发点是这样的：考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问，也就是我们通常所说的"二八"法则），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。
为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）（平摊复杂度，摊返分析见后面章节）
优点
1.伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。
2.可靠的性能——它的平均效率不输于其他平衡树
3.存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
缺点：
伸展树最显著的缺点是它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——O(log n)。
即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。
伸展(splay)
当一个节点x被访问过后，伸展操作会将x移动到根节点。为了进行伸展操作，我们会进行一系列的旋转，每次旋转会使x离根节点更近。通过每次访问节点后的伸展操作，最近访问的节点都会离根节点更近，且伸展树也会大致平衡，这样我们就可以得到期望均摊时间复杂度的下界——均摊O(log n)。每次旋转操作由三个因素决定：
x是其父节点p的左儿子还是右儿子；
p是否为根；
p是其父节点g（x的祖父节点）的左儿子还是右儿子。
在每次旋转操作后，设置g的儿子为x是很重要的。如果g为空，那么x显然就是根节点了。
共有三种旋转操作，每种都有左旋（Zig）和右旋（Zag）两种情况。为了简单起见，对每种旋转操作只展示一种情况(因为是对称的，程序上是6种但是逻辑上是3种)。这些旋转操作是：
Zig：当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。
(单旋转)
Zig-zig和Zag-zag：当p不为根节点且x和p都为左儿子或都为右儿子时进行。下图为x和p都为左儿子时的情况（即Zig-zig），需先将p右旋到g的位置，再将x右旋到p的位置。
(一字型旋转)
Zig-zag和Zag-zig：当p不为根节点且x为左儿子而p为右儿子时进行，反之亦然。下图为前述情况（即Zig-zag），需先将x左旋到p到的位置，再将x右旋到g的位置。
（之字形旋转）
连接(join)
给出两棵树S和T，且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树：伸展S中最大的节点。现在这个节点变为S的根节点，且没有右儿子。
令T的根节点变为其右儿子。
分割(split)
给出一棵树和一个元素x，返回两棵树：一棵中所有的元素均小于等于x，另一棵中所有的元素大于x。下面的步骤可以完成这个操作：伸展x。这样的话x成为了这棵树的根所以它的左子树包含了所有比x小的元素，右子树包含了所有比x大的元素。
把x的右子树从树中分割出来。
插入(insert)
插入操作是一个比较复杂的过程，具体步骤如下: 我们假定要插入的值为k。如果当前树为空，则直接插入根。
如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行splay操作。
否则按照二叉查找树的性质
public class SplayTree<T extends Comparable<T>> {
private SplayTreeNode<T> mRoot; // 根结点
public class SplayTreeNode<T extends Comparable<T>> {
T key; // 关键字(键值)
SplayTreeNode<T> left; // 左孩子
SplayTreeNode<T> right; // 右孩子
public SplayTreeNode() {
this.left = null;
this.right = null;
}
public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
}
}
public SplayTree() {
mRoot = null;
}
/*
* 前序遍历"伸展树"
*/
private void preOrder(SplayTreeNode<T> tree) {
if (tree != null) {
System.out.print(tree.key + " ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍历"伸展树"
*/
private void inOrder(SplayTreeNode<T> tree) {
if (tree != null) {
inOrder(tree.left);
System.out.print(tree.key + " ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 后序遍历"伸展树"
*/
private void postOrder(SplayTreeNode<T> tree) {
if (tree != null) {
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key + " ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (递归实现)查找"伸展树x"中键值为key的节点
*/
private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) {
if (x == null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public SplayTreeNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非递归实现)查找"伸展树x"中键值为key的节点
*/
private SplayTreeNode<T> iterativeSearch(SplayTreeNode<T> x, T key) {
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public SplayTreeNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小结点：返回tree为根结点的伸展树的最小结点。
*/
private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) {
if (tree == null)
return null;
while (tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
SplayTreeNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 查找最大结点：返回tree为根结点的伸展树的最大结点。
*/
private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) {
if (tree == null)
return null;
while (tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
SplayTreeNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 旋转key对应的节点为根节点，并返回根节点。
*
* 注意： (a)：伸展树中存在"键值为key的节点"。 将"键值为key的节点"旋转为根节点。 (b)：伸展树中不存在"键值为key的节点"，并且key <
* tree.key。 b-1 "键值为key的节点"的前驱节点存在的话，将"键值为key的节点"的前驱节点旋转为根节点。 b-2
* "键值为key的节点"的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。
* (c)：伸展树中不存在"键值为key的节点"，并且key > tree.key。 c-1
* "键值为key的节点"的后继节点存在的话，将"键值为key的节点"的后继节点旋转为根节点。 c-2
* "键值为key的节点"的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。
*/
private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {
if (tree == null) {
return tree;
}
SplayTreeNode<T> N = new SplayTreeNode<T>();
SplayTreeNode<T> l = N;
SplayTreeNode<T> r = N;
SplayTreeNode<T> c;
while(true) {
int cmp = key.compareTo(tree.key);
if (cmp < 0) {
if (tree.left == null) {
break;
}
if (key.compareTo(tree.left.key) < 0) {
c = tree.left; /* rotate right */
tree.left = c.right;
c.right = tree;
tree = c;
if (tree.left == null)
break;
}
r.left = tree; /* link right */
r = tree;
tree = tree.left;
} else if (cmp > 0) {
if (tree.right == null)
break;
if (key.compareTo(tree.right.key) > 0) {
c = tree.right; /* rotate left */
tree.right = c.left;
c.left = tree;
tree = c;
if (tree.right == null)
break;
}
l.right = tree; /* link left */
l = tree;
tree = tree.right;
} else {
break;
}
}
l.right = tree.left; /* assemble */
r.left = tree.right;
tree.left = N.right;
tree.right = N.left;
return tree;
}
public void splay(T key) {
mRoot = splay(mRoot, key);
}
/*
* 将结点插入到伸展树中，并返回根节点
*
* 参数说明： tree 伸展树的 z 插入的结点
*/
private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {
int cmp;
SplayTreeNode<T> y = null;
SplayTreeNode<T> x = tree;
// 查找z的插入位置
while (x != null) {
y = x;
cmp = z.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else {
System.out.printf("不允许插入相同节点(%d)!\n", z.key);
z = null;
return tree;
}
}
if (y == null)
tree = z;
else {
cmp = z.key.compareTo(y.key);
if (cmp < 0)
y.left = z;
else
y.right = z;
}
return tree;
}
public void insert(T key) {
SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);
// 如果新建结点失败，则返回。
if ((z = new SplayTreeNode<T>(key, null, null)) == null)
return;
// 插入节点
mRoot = insert(mRoot, z);
// 将节点(key)旋转为根节点
mRoot = splay(mRoot, key);
}
/*
* 删除结点(z)，并返回被删除的结点
*
* 参数说明： bst 伸展树 z 删除的结点
*/
private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {
SplayTreeNode<T> x;
if (tree == null)
return null;
// 查找键值为key的节点，找不到的话直接返回。
if (search(tree, key) == null)
return tree;
// 将key对应的节点旋转为根节点。
tree = splay(tree, key);
if (tree.left != null) {
// 将"tree的前驱节点"旋转为根节点
x = splay(tree.left, key);
// 移除tree节点
x.right = tree.right;
} else
x = tree.right;
tree = null;
return x;
}
public void remove(T key) {
mRoot = remove(mRoot, key);
}
/*
* 销毁伸展树
*/
private void destroy(SplayTreeNode<T> tree) {
if (tree == null)
return;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree = null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
* 打印"伸展树"
*
* key -- 节点的键值 direction -- 0，表示该节点是根节点; -1，表示该节点是它的父结点的左孩子; 1，表示该节点是它的父结点的右孩子。
*/
private void print(SplayTreeNode<T> tree, T key, int direction) {
if (tree != null) {
if (direction == 0) // tree是根节点
System.out.printf("%2d is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
print(tree.left, tree.key, -1);
print(tree.right, tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
更新时间：2020-02-13 15:36:39
本文由 寻非 创作，如果您觉得本文不错，请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
原文链接：https://www.zhouning.group/archives/数据结构基础14非线性数据结构之自平衡二叉查找树之伸展树
最后更新：2020-02-13 15:36:39
