伸展树

优点

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

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

缺点

伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(log n )

实现

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

#include#ifndef SPLAY_TREE#define SPLAY_TREEtemplate<typenameT,typenameComp=std::less>classsplay_tree{private:Compcomp;unsignedlongp_size;structnode{node*left,*right;node*parent;Tkey;node(constT&init=T()):left(0),right(0),parent(0),key(init){}}*root;voidleft_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;elseif(x==x->parent->left)x->parent->left=y;elsex->parent->right=y;y->left=x;x->parent=y;}voidright_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;elseif(x==x->parent->left)x->parent->left=y;elsex->parent->right=y;y->right=x;x->parent=y;}voidsplay(node*x){while(x->parent){if(!x->parent->parent){if(x->parent->left==x)right_rotate(x->parent);elseleft_rotate(x->parent);}elseif(x->parent->left==x&&x->parent->parent->left==x->parent){right_rotate(x->parent->parent);right_rotate(x->parent);}elseif(x->parent->right==x&&x->parent->parent->right==x->parent){left_rotate(x->parent->parent);left_rotate(x->parent);}elseif(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);}}}voidreplace(node*u,node*v){if(!u->parent)root=v;elseif(u==u->parent->left)u->parent->left=v;elseu->parent->right=v;if(v)v->parent=u->parent;}node*subtree_minimum(node*u){while(u->left)u=u->left;returnu;}node*subtree_maximum(node*u){while(u->right)u=u->right;returnu;}public:splay_tree():root(0),p_size(0){}voidinsert(constT&key){node*z=root;node*p=0;while(z){p=z;if(comp(z->key,key))z=z->right;elsez=z->left;}z=newnode(key);z->parent=p;if(!p)root=z;elseif(comp(p->key,z->key))p->right=z;elsep->left=z;splay(z);p_size++;}node*find(constT&key){node*z=root;while(z){if(comp(z->key,key))z=z->right;elseif(comp(key,z->key))z=z->left;elsereturnz;}return0;}voiderase(constT&key){node*z=find(key);if(!z)return;splay(z);if(!z->left)replace(z,z->right);elseif(!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--;}constT&minimum(){returnsubtree_minimum(root)->key;}constT&maximum(){returnsubtree_maximum(root)->key;}boolempty()const{returnroot==0;}unsignedlongsize()const{returnp_size;}};#endif // SPLAY_TREE

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。