伸展树 类型 树 发明时间 1985年 发明者 丹尼爾·斯萊托 和羅伯特·塔揚 用大O符号 表示的时间复杂度 算法
平均
最差 空间
O
(
n
)
{\displaystyle O(n)}
O
(
n
)
{\displaystyle O(n)}
搜索
O
(
log
-->
n
)
{\displaystyle O(\log n)}
均摊
O
(
log
-->
n
)
{\displaystyle O(\log n)}
插入
O
(
log
-->
n
)
{\displaystyle O(\log n)}
均摊
O
(
log
-->
n
)
{\displaystyle O(\log n)}
删除
O
(
log
-->
n
)
{\displaystyle O(\log n)}
均摊
O
(
log
-->
n
)
{\displaystyle O(\log n)}
伸展树 (英語:Splay Tree )是一种能够自我平衡的二叉查找树 ,它能在均摊
O
(
log
-->
n
)
{\displaystyle O(\log n)}
的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼爾·斯萊托 和羅伯特·塔揚 在1985年发明的[1] 。
在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行調整,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。
优点
伸展树的自我平衡使其拥有良好的性能,因为频繁访问的节点会被移动到更靠近根节点,进而获得更快的访问速度。
可靠的性能——它的平均效率不输于其他平衡树 [2] 。
存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小。
缺点
伸展树最显著的缺点是它有可能会变成一条链 。例如,在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率,操作的实际时间效率可能很低。然而均摊 的最坏情况是对数级的——
O
(
log
-->
n
)
{\displaystyle O(\log n)}
。
即使以“只读”方式(例如通过查找操作)访问伸展树,其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言,如果允许多个线程同时执行查找操作,则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用,尽管用于实现优先级队列的方式不多。
操作
伸展(splay)
当一个节点x 被访问过后,伸展操作会将x 移动到根节点。为了进行伸展操作,我们会进行一系列的旋转,每次旋转会使x 离根节点更近。通过每次访问节点后的伸展操作,最近访问的节点都会离根节点更近,且伸展树也会大致平衡,这样我们就可以得到期望均摊时间复杂度的下界——均摊
O
(
log
-->
n
)
{\displaystyle O(\log n)}
。
每次旋转操作由三个因素决定:
x 是其父节点p 的左儿子还是右儿子;
p 是否为根;
p 是其父节点g (x 的祖父节点)的左儿子还是右儿子。
在每次旋转操作后,设置p 的儿子为x 是很重要的。如果p 为空,那么x 显然就是根节点了。
共有三种旋转操作,每种都有右旋(Zig)和左旋(Zag)两种情况。为了简单起见,对每种旋转操作只展示一种情况。这些旋转操作是:
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 大的元素。
插入(insert)
插入操作是一个比较复杂的过程,具体步骤如下:
我们假定要插入的值为k。
如果当前树为空,则直接插入根。
如果当前节点的权值等于k则增加当前节点的大小并更新节点和父亲的信息,将当前节点进行splay操作。
否则按照二叉查找树的性质向下找,找到空节点就插入即可,当然在最后还要进行一次splay操作。
[3]
删除(delete)
令要删除的节点为x,对x进行一次splay操作将其移动到根节点的位置。
若x的大小大于1,则将x的大小减一然后结束删除操作。
否则将x删除然后执行join操作合并x的左右子树并重新指定根。
查找(find)
如同一般的查找树的查找方式。
实现
以下是伸展树的C++实现(用指针 实现)
#include <functional>
#ifndef SPLAY_TREE
#define SPLAY_TREE
template < typename T , typename Comp = std :: less < T > >
class splay_tree {
private :
Comp comp ;
unsigned long p_size ;
struct node {
node * left , * right ;
node * parent ;
T key ;
node ( const T & init = T ( ) ) : left ( 0 ), right ( 0 ), parent ( 0 ), key ( init ) { }
} * root ;
void left_rotate ( node * x ) {
node * y = x -> right ;
x -> right = y -> left ;
if ( y -> left ) y -> left -> parent = x ;
y -> parent = x -> parent ;
if ( x -> parent ) {
if ( x == x -> parent -> left ) x -> parent -> left = y ;
else x -> parent -> right = y ;
}
y -> left = x ;
x -> parent = y ;
}
void right_rotate ( node * x ) {
node * y = x -> left ;
x -> left = y -> right ;
if ( y -> right ) y -> right -> parent = x ;
y -> parent = x -> parent ;
if ( x -> parent ) {
if ( x == x -> parent -> left ) x -> parent -> left = y ;
else x -> parent -> right = y ;
}
y -> right = x ;
x -> parent = y ;
}
void splay ( node * x ) {
while ( x -> parent ) {
if ( ! x -> parent -> parent ) {
if ( x -> parent -> left == x ) right_rotate ( x -> parent );
else left_rotate ( x -> parent );
} else if ( x -> parent -> left == x && x -> parent -> parent -> left == x -> parent ) {
right_rotate ( x -> parent -> parent );
right_rotate ( x -> parent );
} else if ( x -> parent -> right == x && x -> parent -> parent -> right == x -> parent ) {
left_rotate ( x -> parent -> parent );
left_rotate ( x -> parent );
} else if ( x -> parent -> left == x && x -> parent -> parent -> right == x -> parent ) {
right_rotate ( x -> parent );
left_rotate ( x -> parent );
} else {
left_rotate ( x -> parent );
right_rotate ( x -> parent );
}
}
}
void replace ( node * u , node * v ) {
if ( ! u -> parent ) root = v ;
else if ( u == u -> parent -> left ) u -> parent -> left = v ;
else u -> parent -> right = v ;
if ( v ) v -> parent = u -> parent ;
}
node * subtree_minimum ( node * u ) {
while ( u -> left ) u = u -> left ;
return u ;
}
node * subtree_maximum ( node * u ) {
while ( u -> right ) u = u -> right ;
return u ;
}
public :
splay_tree ( ) : root ( 0 ), p_size ( 0 ) { }
void insert ( const T & key ) {
node * z = root ;
node * p = 0 ;
while ( z ) {
p = z ;
if ( comp ( z -> key , key ) ) z = z -> right ;
else z = z -> left ;
}
z = new node ( key );
z -> parent = p ;
if ( ! p ) root = z ;
else if ( comp ( p -> key , z -> key ) ) p -> right = z ;
else p -> left = z ;
splay ( z );
p_size ++ ;
}
node * find ( const T & key ) {
node * z = root ;
while ( z ) {
if ( comp ( z -> key , key ) ) z = z -> right ;
else if ( comp ( key , z -> key ) ) z = z -> left ;
else return z ;
}
return 0 ;
}
void erase ( const T & key ) {
node * z = find ( key );
if ( ! z ) return ;
splay ( z );
if ( ! z -> left ) replace ( z , z -> right );
else if ( ! z -> right ) replace ( z , z -> left );
else {
node * y = subtree_minimum ( z -> right );
if ( y -> parent != z ) {
replace ( y , y -> right );
y -> right = z -> right ;
y -> right -> parent = y ;
}
replace ( z , y );
y -> left = z -> left ;
y -> left -> parent = y ;
}
p_size -- ;
}
const T & minimum ( ) { return subtree_minimum ( root ) -> key ; }
const T & maximum ( ) { return subtree_maximum ( root ) -> key ; }
bool empty ( ) const { return root == 0 ; }
unsigned long size ( ) const { return p_size ; }
};
#endif // SPLAY_TREE
时间效率分析
m次伸展操作的均摊时间效率
T
a
m
o
r
t
i
z
e
d
(
m
)
=
O
(
m
log
-->
n
)
{\displaystyle T_{\mathrm {amortized} }(m)=O(m\log n)}
实际时间效率
T
a
c
t
u
a
l
(
m
)
=
O
(
m
log
-->
n
+
n
log
-->
n
)
{\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}
[4]
参考来源
^ Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF) , Journal of the ACM, 1985, 32 (3): 652–686 [2015-03-05 ] , doi:10.1145/3828.3835 , (原始内容存档 (PDF) 于2015-03-05) (英语)
^ Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. 2014: 506 . ISBN 978-1-118-77133-4 (英语) . The surprising thing about splaying is that it allows us to guarantee a logarithmic amortized running time, for insertions, deletions, and searches.
^ Splay tree - OIwiki . [2019-07-14 ] . (原始内容存档 于2019-07-14).
^ Splay tree - Wikipedia . [2018-06-23 ] . (原始内容存档 于2018-05-05).