旋转Treap的简单实现

我就是我 2022-05-25 10:15 144阅读 0赞

Treap=Tree+Heap

Treap是一棵 [二叉搜索树][Link 1] ，它的左子树和右子树分别是一个Treap，和一般的二叉搜索树不同的是，Treap结构中每个节点x有两个域，一个是其关键字值key，一个是优先级数priority（他是一个独立选取的随机数），对于Treap结构，其关键字遵循二叉搜索树性质，其优先级遵循堆性质。但是这里要注意的是Treap和二叉堆有一点不同，就是 [二叉堆][Link 2] 必须是完全二叉树，而Treap可以并不一定是。

在这里用的链表实现的旋转的Treap，简单实现是思路比较简单，但代码稍微有点繁琐。有点懒，不想整理了。

TreapNode结构如下：

template<class T>
    struct treapNode
    {
    	int key;//用于二叉搜索树的关键字 
    	int pri;//用于堆性质的优先级数字 
    	T element;//其中的元素 
        treapNode<T> *leftChild,   //左子树 
                     *rightChild,
    				 *father;  //右子树 
       treapNode() {leftChild = rightChild = father=NULL;}//构造函数 
       treapNode(const T& theElement):element(theElement)
       {
          leftChild = rightChild = father=NULL;
       }
       treapNode(const T& theElement,
                      treapNode *theLeftChild,
                      treapNode *theRightChild,
    				  treapNode *theFather)
                      :element(theElement)
       {
          leftChild = theLeftChild;
          rightChild = theRightChild;
          father=theFather;
       }
    	treapNode(int theKey,int thePri,T theElement)
    	{
    		key=theKey;
    		pri=thePri;
    		element=theElement;
    		 leftChild = rightChild = father=NULL;
    	}
    	treapNode(int theKey,T theElement)
    	{
    		key=theKey;
    		pri=rand();
    		element = theElement;
    		leftChild=rightChild=father=NULL;
    	} 
    };

在节点中加入了父节点的指针，为了后面的旋转操作能够更简单一点，不加也是可以的，不过就要稍微复杂一点了。

插入操作：

先找到要插入的位置，然后判断优先级是否满足堆的性质，如果满足就不用旋转了。

不满足：当插入的节点为其父节点的左孩子时，应该右旋，否则左旋。

插入方法：

template<class T>
    void treap<T>::insert(treapNode<T> *t)//插入方法，参数为一个treap节点。 
    {   t->leftChild=t->rightChild=t->father=NULL;
    	if(root==NULL)//当treap为空的时候情况 
    	  {
    	   root=t;
    	   treapSize++;
    	   return ;
          }
    	else//当treap不为空的时候，要找到要删除的位置 
    	{
    		treapNode<T> *pp=root;
    		treapNode<T> *p=NULL;
    		while(pp!=NULL)
    		{   p=pp;
    			if(t->key<pp->key)//小于关键字时 
    				pp=pp->leftChild;
    			else
    			{
    				if(t->key>pp->key)//大于关键字时 
    				pp=pp->rightChild;
    				else//要插入的节点已经重复时 
    				{
    				pp->element=t->element;
    				treapSize--;
    				return; 
    				}
    			}
    		}
    	  if(t->key>p->key)
    	  {
    	   p->rightChild=t;
    	   t->father=p;
          }
    	  else
    	  {
    	   p->leftChild=t;
    	   t->father=p;
          }
    	}
    	treapNode<T> *q=t->father;//获取插入节点的父节点 
    	//treapNode<T> *w=t->father;
    	int com;//判断是否循环继续的量 
    	do//采用do-while结构，保证循环至少进行一次 
      { com=0;
    	if(t->pri<q->pri&&t->key<q->key)//当优先级不满足堆的性质并且插入的节点在左孩子的位置时，此时应该右旋 
    	{   if(t->rightChild!=NULL)//当插入节点的右孩子不为空的时候 
    	    {
    		   q->leftChild=t->rightChild;//插入节点的右孩子变成其父节点的左孩子 
    		   t->rightChild->father=q;//插入节点的右孩子的父母指向插入节点的父母 
    		   t->rightChild=q;//父节点变为插入节点的右孩子 
    		   if(q->father!=NULL)//在这里分情况讨论，当其父节点的父节点不为空的时候 
    		   {
    		   	t->father=q->father;//插入节点的父节点为其父节点的父节点
    			if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子 
    		   	q->father->leftChild=t;//父节点的父节点左孩子变成插入节点 
    		   	else
    		   	q->father->rightChild=t;
    			q->father=t; //父节点的父母变成插入节点 
    		   }
    		   else//当其父节点的父节点为空时 
    		   {
    		   	t->father=NULL;//插入节点的父节点为空 
    		   	root=t;
    		   	q->father=t;//父节点的父母变为插入节点 
    		   }
    	    }
    	    else//当插入节点的右孩子为空的时候 
    	    {   t->rightChild=q;
    		    if(q->father!=NULL)//当其父节点的父节点不为空时 
    		    {
    			  t->father=q->father;
    			  if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
    			  q->father->leftChild=t;
    			  else
    			  q->father->rightChild=t;
    			  q->father=t; 
    			  q->leftChild=NULL;
    		    } 
    		    else//当其父节点的父节点为空时 
    			{
    				t->father=NULL;//父节点变为空 
    				root=t;//此时根节点为当前插入的节点 
    				t->rightChild=q;//插入节点的右孩子变为原来节点的父节点 
    				q->father=t; //插入节点的父节点改成当前节点 
    				q->leftChild=NULL;//插入节点的原来的父节点改为空值 
    			}
    		} com=1;
    	}
    	if(t->pri<q->pri&&t->key>q->key)//当优先级不满足堆的性质并且插入的节点在右孩子的位置时，此时应该左旋 
    	{   if(t->leftChild!=NULL)//当插入节点的左孩子不为空的时候 
    	    {
    		   q->rightChild=t->leftChild;//插入节点的左孩子变成其父节点的右孩子 
    		   t->leftChild->father=q;//插入节点的左孩子的父母指向插入节点的父母 
    		   t->leftChild=q;//父节点变为插入节点的左孩子 
    		   if(q->father!=NULL)//在这里分情况讨论，当其父节点的父节点不为空的时候 
    		   {
    		   	t->father=q->father;//插入节点的父节点为其父节点的父节点
    			if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子 
    		   	q->father->leftChild=t;//父节点的父节点左孩子变成插入节点 
    		   	else
    		   	q->father->rightChild=t;
    			q->father=t; //父节点的父母变成插入节点 
    			
    		   }
    		   else//当其父节点的父节点为空时 
    		   {
    		   	t->father=NULL;//插入节点的父节点为空 
    		   	root=t;
    		   	q->father=t;//父节点的父母变为插入节点 
    		   	q->leftChild=NULL;
    		   }
    	    }
    	    else//当插入节点的左孩子为空的时候 
    	    {   t->leftChild=q;
    		    if(q->father!=NULL)//当其父节点的父节点不为空时 
    		    {
    			  t->father=q->father;
    			  if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
    			  q->father->leftChild=t;
    			  else
    			  q->father->rightChild=t;
    			  q->father=t; 
    			  q->rightChild=NULL;
    		    } 
    		    else//当其父节点的父节点为空时 
    			{
    				t->father=NULL;
    				root=t;
    				t->leftChild=q;
    				q->father=t;
    				q->rightChild=NULL; 
    			}
    		} com=1;
    	}
    	q=t->father;//更新插入节点的父节点 
      } while(q!=NULL&&com==1);//
      treapSize++;
    }

删除操作:

先找到要删除的节点的位置，然后判断要删除的节点的有几个孩子，然后再根据情况具体实现。

template<class T>
    void treap<T>::erase(int key)
    {
    	treapNode<T> *t=root;
    	while(t!=NULL)//首先找到要删除的节点 
    	{
    		if(t->key<key)
    		t=t->rightChild;
    		else
    		{
    		    if(t->key>key)
    			t=t->leftChild;
    			else//当相等时即找到要删除的节点了，跳出循环 
    			break;
    		} 
    	}
    	if(t==NULL)//treap中没有要删除的关键字的元素 
    	{
    		cout<<"please put in correct data"<<key<<" ";
    		return ;
    	}
    	else//找到要删除的节点后 
    	{
    	    treapNode<T> *q=t->father;//找到要删除的节点的父节点 
    	   if(t->leftChild==NULL&&t->rightChild==NULL)//最简单的情况：当要删除的节点为叶节点时 ，并且此种情况下优先级的顺序不会改变 
    	  {
    		if(t==root)//其中的特殊情况：只有一个节点，即根节点 
    		root=NULL;
    		else//不为根节点 
    		{
    			if(key<q->key)//判断是左孩子还是右孩子 
    			q->leftChild=NULL;
    			else
    			q->rightChild=NULL;
    			t->father=NULL;//让此节点的父节点为空 
    			//t=NULL;//释放此节点 
    		}
    	  }
    	  if((t->leftChild==NULL&&t->rightChild!=NULL)||(t->leftChild!=NULL&&t->rightChild==NULL))//当要删除的节点为有一个孩子时 
    	  {  
    	   if(q==NULL)//当要删除的节点为根节点时 
    	   {
    	   	 if(t->leftChild!=NULL)//如果左孩子不为空 
    	   	 { t->leftChild->father=NULL;
    		   root=t->leftChild;
    		   t->leftChild=NULL;
    	     }
    	     else//右孩子不为空 
    	     {
    	     	t->rightChild->father=NULL;
    	     	root=t->rightChild;
    	     	t->rightChild=NULL;
    		 }
    	   }
    	   else//删除的节点不为根节点时 
    	   {
    	  	 if(t->key<q->key)//当为其左孩子时 
    		 {
    		    if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时 
    			{
    				q->leftChild=t->leftChild;//删除节点的父节点的左孩子指向删除节点的左孩子 
    				t->leftChild->father=q;//删除节点的左孩子的父亲指向删除节点的父亲 
    				t->leftChild=NULL;//删除节点的左孩子指针指向空 
    				t->father=NULL;//其父节点的指针指向空 
    			} 
    			else//当要删除的右孩子不为空时 
    			{
    		       q->leftChild=t->rightChild;
    			   t->rightChild->father=q;
    			   t->rightChild=NULL;
    			   t->father=NULL;		
    		    }	 
    		 } 
    		 else//当为其右孩子时 
    		 {
    		 	if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时 
    			{
    				q->rightChild=t->leftChild;
    				t->leftChild->father=q;
    				t->leftChild=NULL;
    				t->father=NULL;
    				//t=NULL;
    			} 
    			else//当删除的节点的右孩子不为空时 
    			{
    		       q->rightChild=t->rightChild;
    			   t->rightChild->father=q;
    			   t->rightChild=NULL;
    			   t->father=NULL;
    			   //t=NULL;		
    		    }	 
    		 }
    	   }
         }
    	  if(t->leftChild!=NULL&&t->rightChild!=NULL)//左右孩子均不为空的情况 
    	  { 
    	  	if(t->leftChild->pri<t->rightChild->pri)//找出左右孩子中优先级较小的那个 
    		  {treapNode<T> *p=t->leftChild;//记录下当前节点的左孩子 
    		  	if(p->rightChild==NULL)//当左孩子的右孩子为空时 
    			  {
    			  	if(q==NULL)//如果待删节点为根节点 
    				  {
    				  	p->rightChild=t->rightChild;
    					p->father=NULL;
    					t->rightChild->father=p;
    					t->leftChild=t->rightChild=NULL;
    					//t=NULL;
    					root=p;   
    				  }
    				else//待删节点不为根节点 
    				{
    					p->rightChild=t->rightChild;
    					t->rightChild->father=p;
    					 p->father=q;
    					 if(q->leftChild==t)
    					 q->leftChild=p;
    					 else
    					 q->rightChild=p;
    					 t->father=t->leftChild=t->rightChild=NULL;
    					 //t=NULL;
    				}
    			  	
    			  }
    			else//当左孩子的右孩子不为空时 
    			 {
    			   	t->father=p;
    			   	t->leftChild=p->rightChild;
    			   	p->rightChild->father=t;
    			   	p->rightChild=t;
    			   	if(q==NULL)
    				 {
    				   	p->father=NULL;
    				   	root=p;
    				 }
    				else
    				 {
    				     p->father=q;
    				     if(q->leftChild==t)
    				     q->leftChild=p;
    				     else
    				     q->rightChild=p;
    				 }
    				 erase(key);
    			 }
    		  }
    		  else//找出左右孩子中优先级较小的那个 
    		  {treapNode<T> *p=t->rightChild;//记录下当前节点的右孩子 
    		  	if(t->rightChild->leftChild==NULL)//当右孩子的左孩子为空时 
    			  {
    			  	if(q==NULL)//如果待删节点为根节点 
    				  {
    				  	p->leftChild=t->leftChild;
    					p->father=NULL;
    					t->leftChild->father=p;
    					t->leftChild=t->rightChild=NULL;
    					//t=NULL;
    					root=p;   
    				  }
    				else//待删节点不为根节点 
    				{
    					p->leftChild=t->leftChild;
    					t->leftChild->father=p;
    					 p->father=q;
    					 if(q->leftChild==t)
    					 q->leftChild=p;
    					 else
    					 q->rightChild=p;
    					 t->father=t->leftChild=t->rightChild=NULL;
    					 //t=NULL;
    				}
    			  	
    			  }
    			else//当右孩子的左孩子不为空时 
    			 {
    			   	t->father=p;
    			   	t->rightChild=p->leftChild;
    			   	p->leftChild->father=t;
    			   	p->leftChild=t;
    			   	if(q==NULL)
    				 {
    				   	p->father=NULL;
    				   	root=p;
    				 }
    				else
    				 {
    				     p->father=q;
    				     if(q->leftChild==t)
    				     q->leftChild=p;
    				     else
    				     q->rightChild=p;
    				 }
    				 erase(key);
    			 }
    		  }
    	  } 
    	  treapSize--;
       }
    }

大概就是这样。

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E5%A0%86