伸展树(数据结构篇)

本文主要是介绍伸展树(数据结构篇)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构之伸展树

伸展树

概念：

伸展树是一颗对任意一个节点被访问后，就经过一系列的AVL树的旋转操作将该节点放到根上的特殊二叉查找树。
伸展树能保证对树操作M次的时间复杂度为O(MlogN)，而当一个查找树的一个节点刚好处于查找树最坏的情形，我们每次访问都需要按照最坏情形的时间计算，这将耗费O(M*N)的时间，伸展树就是要将访问的节点进行移动，使它不一直存在一个地方，避免了多次操作最坏情形的出现，而伸展树访问的节点比较深，经过移动，对该节点的原先子树节点访问也会避免往更深处进行操作
伸展树不要求保留高度或平衡信息，因此能够节省空间以及简化代码

查找操作：

关于访问节点，然后对其进行一系列旋转操作，将该节点放到根上，我们需要对访问该节点的路径上(从下到上)每一个节点都需要和它们的父节点实施单旋转，直到将该节点推到根
但是如果只进行单旋转情况，并直接从下到上的话，则会浪费大部分时间
因此我们需要使用展开操作，而展开操作其实就是根据路径树的结构分情况进行操作
具体步骤：
1. 判断路径的结构，分为“之字形”和“一字形”
2. 如果是“之字形”，就需要对要访问的节点进行双旋转操作，如果访问的节点不是根的孙节点，则进行双旋转操作后，会将路径结构转换为“一字形”，然后再进行“一字形”操作，将其放在根上
3. 如果是“一字形”，就需要路径从下到上逐一进行单旋转操作，直至要访问的节点成为根才结束

删除操作：

我们可以通过访问要被删除的节点然后访问后进行删除，这样的话，被删除节点就会被推到根上，将该节点删除，树就会分为两颗子树T_L和T_R(左子树和右子树)
要想将T_L和T_R重新合成为一个树，就需要找到T_L的最大值，并进行旋转操作，将其作为T_L的根节点，而此时T**_L将是一个没有右儿子的树**，然后将T_R的根节点作为现在T_L根节点的右儿子

代码：

struct splay{int data;splay* left;splay* right;
};splay* createNode(int data){auto p=new splay;p->data=data;p->left=NULL;p->right=NULL;return p;
}splay* SingleRotatewithLeft(splay* &k1){splay* k2;k2=k1->left;k1->left=k2->right;k2->right=k1;return k2;
}splay* SingleRotatewithRight(splay* &k1){splay* k2;k2=k1->right;k1->right=k2->left;k2->left=k1;return k2;
}splay* DoubleRotatewithLeft(splay* &k1){k1->left= SingleRotatewithRight(k1->left);return SingleRotatewithLeft(k1);
}splay* DoubleRotatewithRight(splay* &k1){k1->right= SingleRotatewithLeft(k1->right);return SingleRotatewithRight(k1);
}//插入
splay* insert(splay* &root,int data){if(NULL==root){splay* add= createNode(data);root=add;}else if(data<root->data){root->left= insert(root->left,data);}else if(data>root->data){root->right= insert(root->right,data);}return root;
}//查找
//因为查找data很有可能是相等的，所以要分开这种情况，如果root的下一个是要找的我们就往上返，令节点差为2个保证了判断路径结构的正确性
splay* search(splay* &root,int data){if(NULL==root||root->data==data){return root;}else if(data<root->data){root->left= search(root->left,data);if(data<root->left->data){root= SingleRotatewithLeft(root);}else if(data>root->left->data){root= DoubleRotatewithLeft(root);}}else if(data>root->data){root->right= search(root->right,data);if(data>root->right->data){root= SingleRotatewithRight(root);}else if(data<root->right->data){root= DoubleRotatewithRight(root);}}return root;
}//查找最小值
int findmin(splay* root){if(NULL==root){return root->data;}if (root->left!=NULL){return findmin(root->left);}else{return root->data;}
}//查找最大值
int findmax(splay* root){if(NULL==root){return root->data;}if(root->right!=NULL){return findmax(root->right);}else{return root->data;}
}//删除树节点
void del(splay* &root,int data){search(root,data);if(NULL==root){return;}else{splay* t1=root->left;splay* t2=root->right;root->left=NULL;root->right=NULL;delete root;int temp= findmax(t1);t1= search(t1,temp);t1->right=t2;root=t1;}
}void inorderprint(splay* root){if(NULL==root){return;}inorderprint(root->left);cout<<root->data<<" ";inorderprint(root->right);
}//清空树
void destroy(splay* &root){if(NULL==root){return;}destroy(root->left);destroy(root->right);delete root;
}