# 伸展树

## 优点

• 可靠的性能——它的平均效率不输于其他平衡树[2]
• 存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
• 支持可持久化——可以将其改造成可持久化伸展树可持久化数据结构允许查询修改之前数据结构的信息，对于一般的数据结构，每次操作都有可能移除一些信息，而可持久化的数据结构允许在任何时间查询到之前某个版本的信息。可持久化这一特性在函数式编程当中非常有用。另外，可持久化伸展树每次一般操作的均摊复杂度是O(log n)

## 实现

```#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 ) 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
```

## 参考来源

1. ^ Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees, Journal of the ACM, 1985, 32 (3): 652–686, doi:10.1145/3828.3835 （英文）
2. ^ Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. : 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."