伸展树

伸展树的自我平衡使其拥有良好的性能，因为频繁访问的节点会被移动到更靠近根节点，进而获得更快的访问速度。

可靠的性能——它的平均效率不输于其他平衡树。

存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。

伸展树最显著的缺点是它有可能会变成一条链。例如，在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率，操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——O(log n)。

即使以“只读”方式（例如通过查找操作）访问伸展树，其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言，如果允许多个线程同时执行查找操作，则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用，尽管用于实现优先级队列的方式不多。

当一个节点x被访问过后，伸展操作会将x移动到根节点。为了进行伸展操作，我们会进行一系列的旋转，每次旋转会使x离根节点更近。通过每次访问节点后的伸展操作，最近访问的节点都会离根节点更近，且伸展树也会大致平衡，这样我们就可以得到期望均摊时间复杂度的下界——均摊O(logn)。

每次旋转操作由三个因素决定：

x是其父节点p的左儿子还是右儿子

p是否为根，如果不是

p是其父节点g（x的祖父节点）的左儿子还是右儿子

在每次旋转操作后，设置g的儿子为x是很重要的。如果g为空，那么x显然就是根节点了。

共有三种旋转操作，每种都有左旋和右旋两种情况。为了简单起见，对每种旋转操作只展示一种情况。这些旋转操作是：

Zig：当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。

Zig-zig：当p不为根节点且x和p都为左儿子或都为右儿子时进行。下面这幅图为x和p都为左儿子时的情况。在这种情况下，先右旋p到g的位置，再右旋x到p的位置。

Zig-zag；当p不为根节点且x为左儿子而p为右儿子时进行，反之亦然。在这种情况下，先旋转p到x的位置，再旋转p到g的位置。

给出两棵树S和T，且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树：

伸展S中最大的节点。现在这个节点变为S的根节点，且没有右儿子。

令T的根节点变为其右儿子。

以下是伸展树的C++实现（用指针实现）

#include #ifndef SPLAY_TREE#define SPLAY_TREEtemplate< 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 ) root = y; else 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 ) root = y; else 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次伸展操作的均摊时间效率

实际时间效率