伸展树(英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊O(log n)的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬在1985年发明的。
在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行调整,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
场景:
继AVL树之后,我们给出了2-3树和红黑树。虽然红黑树将2-3树的实现变成了二叉查找树结构,但对于红黑树本身其实还是是引入新的信息表明红还是黑色,并不够纯粹。红红黑黑花里胡哨的,强迫症又犯了怎么办?我们希望要一个纯粹的二叉树
实现而不需要去管这些红黑颜色,不需要去保存额外的信息,有没有其他的方案呢?
伸展树的出发点是这样的:考虑到局部性原理(刚被访问的内容下次可能仍会被访问,查找次数多的内容可能下一次会被访问,也就是我们通常所说的"二八"法则),为了使整个查找时间更小,被查频率高的那些节点应当经常处于靠近树根的位置。这样,很容易得想到以下这个方案:每次查找节点之后对树进行重构,把被查找的节点搬移到树根,这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后,它均会通过旋转的方法把被访问节点旋转到树根的位置。
为了将当前被访问节点旋转到树根,我们通常将节点自底向上旋转,直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系(指中序遍历结果是全序的)情况下,所有基本操作的平摊复杂度仍为O(log n)(平摊复杂度,摊返分析见后面章节)
优点
1.伸展树的自我平衡使其拥有良好的性能,因为频繁访问的节点会被移动到更靠近根节点,进而获得更快的访问速度。
2.可靠的性能——它的平均效率不输于其他平衡树
3.存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小。
缺点:
伸展树最显著的缺点是它有可能会变成一条链。例如,在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率,操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——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的位置。
(之字形旋转)
伸展S中最大的节点。现在这个节点变为S的根节点,且没有右儿子。
令T的根节点变为其右儿子。
伸展x。这样的话x成为了这棵树的根所以它的左子树包含了所有比x小的元素,右子树包含了所有比x大的元素。
把x的右子树从树中分割出来。
如果当前树为空,则直接插入根。
如果当前节点的权值等于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);
}
}
本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础14非线性数据结构之自平衡二叉查找树之伸展树
最后更新:2020-02-13 15:36:39
Update your browser to view this website correctly. Update my browser now