伸展树C++类实现

概念：

区别于二叉搜索树BST和平衡二叉树AVL，伸展树本质在BST基础上还规定类每次访问之后将访问的节点变成根节点，这样使得被访问过的节点尽可能靠近根节点，这样下次再次访问时更快定位。因此不像AVL那样需要保存高度信息节省了存储空间。具有二叉查找树的所有性质。在性能上又比普通的二叉查找树有所改进：普通的二叉查找树在最坏情况下的查找操作的时间复杂度为O(n)（当二叉树退化成一条链的时候），而伸展树在任何情况下的平摊时间复杂度均为 O(log2n).

原理：

伸展树实现O(log2n)量级的平摊复杂度依靠每次对伸展树进行查询、修改、删除操作之后，都进行旋转操作 Splay(x, root)，该操作将节点x旋转到树的根部。 伸展树的旋转有六种类型，如果去掉镜像的重复，则为三种：/：zig(\：zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。

设计方法：

基于旋找展开原理可存在自低向上和自顶向下两种设计方法

1 自底向上的方式进行旋转

zig or zag旋转：

x是我们查找路径上需要旋找的一根非根节点，当x的父节点y是根节点下的情况：

y->lson==x--------zig

y->rson==x-------zag

对于这种情况直接参看AVL树里的单左旋（zag旋转）和单右旋（zig旋转）即可

zig-zig or zag-zag旋转：

x是我们查找路径上需要旋找的一根非根节点，当x的父节点是y，y的父节点是z的情况：

z->lson==y;y->lson==x--------zig-zig->先对y,z进行zig旋找再对x和y节点进行zig旋转

z->rson==y;y->rson==x--------zag-zag->先对y,z进行zag旋找再对x和y节点进行zag旋转

zig-zag or zag-zig旋转：

x是我们查找路径上需要旋找的一根非根节点，当x的父节点是y，y的父节点是z的情况：

z->lson==y;y->rson==x--------zig-zag->先对x,y进行zag旋找再对z和y节点进行zig旋转

z->rson==y;y->lson==x--------zag-zig->先对y,x进行zig旋找再对x和y节点进行zag旋转

C++类实现：

tree.h

#ifndef SPtree #define SPtree /********************Splay tree**********************/ class node{ public: eletype val; node *lson; node *rson; node *parent;//自低需要父节点 node():val(0),lson(NULL),rson(NULL),parent(NULL){} node(eletype k,node*l,node*r,node *p):val(k),lson(l),rson(r),parent(p){} }; typedef node *node_; class SPTree{ public: node*root; public: SPTree(); ~SPTree(); void postorder(); void inorder(); node*Find(eletype x); node* Find1(node *root1,eletype x); node *Findmax(); void splay_frombottom(eletype x); void Insert(eletype x); void Remove(eletype x); void Destroy(); private: void postorder(node_ root1)const; void inorder(node_ root1)const; node* Find(node *root1,eletype x); node *Findmax(node *root1); node* Splayfrombottom(node *y,node*&x); void singleRotaLeft(node*&k2); void singleRotaRight(node*&k2); void DoubleRotaLeft(node *&k2); void DoubleRotaRight(node *&k2); node*Insert(node*&root1,eletype x); node*Remove(node*&root1,eletype x); void Destroy(node*&root1); }; #endiftree.cpp

/*************Splay**********************/ //自低向上的设计 SPTree::SPTree():root(NULL){} SPTree::~SPTree(){ Destroy(root); } void SPTree::singleRotaRight(node*&y){ if(y==NULL)return ; //y节点，y节点父节点，y节点子节点x及x子节点 node *z=y->parent; node *x=y->lson; x->parent=z; if(x->rson)x->rson->parent=y; y->parent=x; y->lson=x->rson; x->rson=y; if(z){if(z->lson==y)z->lson=x;else z->rson=x;} y= x; } void SPTree::singleRotaLeft(node*&y){ if(y==NULL)return ; node *z=y->parent; node *x=y->rson; x->parent=z; if(x->lson)x->lson->parent=y; y->parent=x; y->rson=x->lson; x->lson=y; if(z){if(z->lson==y)z->lson=x;else z->rson=x;} y=x; } void SPTree::DoubleRotaLeft(node *&y){ singleRotaRight(y->rson); singleRotaLeft(y); } void SPTree::DoubleRotaRight(node *&y){ singleRotaLeft(y->lson); singleRotaRight(y); } node* SPTree::Splayfrombottom(node *y,node*&x)//待变成根节点的指针x和当前y {node *p=x->parent; node *g; while(p){ g=p->parent; if(p->lson==x)//x is left {if(g==NULL)singleRotaRight(p);//zig else if(g->lson==p) {singleRotaRight(g);singleRotaRight(p);}//zig-zig else {DoubleRotaLeft(g);}//zag-zig\/ } else if(p->rson==x)// x is right {if(g==NULL)singleRotaLeft(p);//zag else if(g->rson==p){singleRotaLeft(g);singleRotaLeft(p);}//zag-zag else DoubleRotaRight(g);//zag-zig } else ;// x is root p=x->parent; } return x; } void SPTree::splay_frombottom(eletype key){ node *X=Find(root,key); root=Splayfrombottom(root,X); } node*SPTree::Find(node *x,eletype key){ if(x==NULL)return x; else{ if(key<x->val) return Find(x->lson,key); else if(key>x->val)return Find(x->rson,key); else return x; } } node *SPTree::Find(eletype k){ node*p=Find(root,k); if(p==NULL){cout<<"empty tree!"<<endl;return p;} if(p!=root) {root=Splayfrombottom(root,p);return root;} else return p; } node *SPTree::Find1(node *root1,eletype x){ if(root1==NULL){return root1;} node *p=Find(root1,x); if(p==NULL){cout<<"empty tree!"<<endl;return p;} if(p!=root) {root=Splayfrombottom(root,p);return root;} else return p; } node *SPTree::Findmax(node *x){ if(x==NULL){cout<<"empty tree!"<<endl;return x;} node *p=x; while(p->rson)p=p->rson; return Splayfrombottom(x,p); } node *SPTree::Insert(node *&root1,eletype k) {if(root==NULL){root1=(node*)malloc(sizeof(node)); if(root1==NULL){cout<<"not enough memory!"<<endl;exit(1);} root1->val=k;root1->lson=root1->rson=root1->parent=NULL; return root1; } if(k==root1->val)return root1; //不是根节点时先寻找到合适x再进行插入 else{ node *tmp=root1; node *qre=root1; // 需要记住中间量故不采用递归 while(tmp){ if(k<tmp->val){qre=tmp;tmp=tmp->lson;} else if(k>tmp->val){qre=tmp;tmp=tmp=tmp->rson;} else break;//x==tmp->val } if(tmp==NULL)//no x insert it {node *X=new node();X->val=k; X->parent=qre; if(qre->val>k)qre->lson=X; else qre->rson=X; tmp=X;//这样x没有和有都是存在tmp中 } root1=Splayfrombottom(root1,tmp); } return root1; } void SPTree::Insert(eletype key){ root=Insert(root,key); //splay_frombottom(key);Insert已经完成旋转 } node *SPTree::Remove(node *&root2,eletype x){ if(root2==NULL){cout<<"empty Tree!"<<endl;exit(1);} node *root1=Find1(root2,x);//要寻找的点已经变成根节点 if(x==root1->val){ if(root1->lson&&root1->rson) {node *ltree=root1->lson;node *rtree=root1->rson; ltree->parent=rtree->parent=NULL; free(root1); ltree=Findmax(ltree); ltree->rson=rtree; rtree->parent=ltree; return ltree; } else if(root1->lson){node *ltree=root1->lson; ltree->parent=NULL; free(root1); return ltree; } else if(root1->rson){node *rtree=root1->rson; rtree->parent=NULL; free(root1); return rtree; } else {free(root1);root1=NULL;return root1; } } else {cout<<"not exist!"<<endl;return root1;} } void SPTree::Remove(eletype k){ root=Remove(root,k); } void SPTree::Destroy(node *&root1){ if(root1==NULL)return; if(root1->lson)Destroy(root1->lson); if(root1->rson)Destroy(root1->rson); free(root1); } void SPTree::Destroy(){ Destroy(root); } void SPTree::postorder(node *root1)const{ if(root1){ postorder(root1->lson); postorder(root1->rson); cout<<root1->val<<" "; } } void SPTree::postorder(){ postorder(root); cout<<endl; } void SPTree::inorder(node_ root1)const{ if(root1){ inorder(root1->lson); cout<<root1->val<<" "; inorder(root1->rson); } } void SPTree::inorder(){ inorder(root); cout<<endl; }测试程序

#include<iostream> #include<stdlib.h> #include<string.h> #include"Tree.h" static int arr[]={ 10,50,40,30,20,60}; using namespace std; int main(){ int i; //AVLtree<int>*tree=new AVLtree<int>(); SPTree *tree=new SPTree(); int len=sizeof(arr)/sizeof(int); for(i=0;i<len;i++){; tree->Insert(arr[i]); } tree->postorder(); tree->inorder(); i=30; cout<<"Rotate at"<<" "<<i<<endl; tree->Remove(i); tree->postorder(); tree->inorder(); tree->Destroy(); cout<<endl; }

2 自顶向下的方式进行旋转

见下篇