学步园

今天写了Treap树的各种操作。。

1.插入元素

2.删除元素

3.查找元素

4.求第K小元素

5确定一个元素秩

6求最大值

7求最小值

8遍历

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
typedef struct node
{
 node *lchild, *rchild, *pf;//左孩子，右孩子
 int v, pri, size;//值和优先值
}*Node;

void update( Node &q )
{
if( q->rchild && q->lchild )
    q->size = q->rchild->size + q->lchild->size + 1;
else if( q->rchild )
    q->size = q->rchild->size + 1;
else if( q->lchild )
    q->size = q->lchild->size + 1;
else
    q->size = 1;
}

//左旋转，返回新节点
Node Left_Rotate(Node &q)
{
  Node p =  q->rchild;
  q->rchild = p->lchild;
if( p->lchild )
    p->lchild->pf = q;
  p->lchild = q;
  p->pf = q->pf;
  q->pf = p;
  update( q );
  update( p );
return p;
}

//右旋转
Node Right_Rotate(Node &q)
{
  Node p = q->lchild; //新节点为q左孩子
  q->lchild = p->rchild; //p的右孩子给q的左孩子
  if( p->rchild )
    p->rchild->pf = q;
  p->rchild = q;// q成为p的右孩子
  p->pf = q->pf;
  q->pf = p;
  update(q);
  update(p);
return p;
}

Node NewNode(int t)
{
 Node q = new node;
 q->lchild = NULL;
 q->rchild = NULL;
 q->v = t;
 q->size = 1;
 q->pri = rand( ) % 10000;
 printf("%d %d\n", q->v, q->pri);
return q;
 }

Node insert( Node &p, Node &q, Node father)
{
if( p == NULL )
  {
     p = q;
     p->pf = father;
  }
else if( p->v > q->v )
  {
     p->lchild = insert(p->lchild, q, p);
if(p->lchild->pri < p->pri )
        p = Right_Rotate(p);
  }
else
  {
     p->rchild = insert(p->rchild, q, p);
if( p->rchild->pri < p->pri )
        p = Left_Rotate(p);
  }
  update(p);
return p;
}

Node find(Node p, int x)
{
if( p == NULL )
return NULL;
if( p->v == x )
return p;
else if( p->v > x )
return find(p->lchild, x);
else
return find(p->rchild, x);
}

//找出第k小的元素
Node OS_select(Node p, int k)
{ 
int num = 1;
if( p == NULL )
return NULL;
if( p->lchild )
   num = p->lchild->size + 1;
if( num  == k )
return p;
if( k > num )
return OS_select(p->rchild,k - num );
else
return OS_select(p->lchild, k); 
}

//确定一个元素(q->v)的秩
int OS_rank(Node p, Node q)
{
int num = 1;
  Node father = q;
if( q->lchild )
    num = q->lchild->size + 1;
while( father != p )
  {
     q = father;
     father = father->pf;
if(father->rchild == q )
     {
if( father->lchild == NULL )
            num += 1;
else
            num += father->lchild->size + 1 ;
     } 
  }
return num;
}

Node del(Node &p, int x, int &flag)
{  
if( p )
  {
if( p->v > x )
   {
      p->lchild = del(p->lchild, x, flag);
      update( p );
   }
else if( p->v < x )
   {
      p->rchild = del(p->rchild, x, flag);
      update( p );
   }
else
   {   
       flag = 1;
if( p->rchild == NULL && p->lchild == NULL )
       {
           delete p;
return NULL;
       }
else
       { 

if( p->lchild )//如果左孩子存在
         {   
if( p->rchild == NULL || (p->lchild->pri < p->rchild->pri ))//右孩子为空，或左孩子小于右孩子
           {
             p = Right_Rotate( p );
             p->rchild = del(p->rchild, x, flag);
             update( p );
           }
else  //左孩子大于右孩子
          { 
           p = Left_Rotate( p );
           p->lchild = del(p->lchild, x, flag);
           update( p );
          }
         }
else  //如果左孩子不存在
         {
           p = Left_Rotate( p );
           p->lchild = del(p->lchild, x, flag);
           update( p );
         }

       }  
   }
  }  
return p;
}

//求最小值
Node Get_Min( Node p)
{
  Node q = p;
while( p )
  {
   q = p;
   p = p->lchild;
  }
return q;
}

//求最大值
Node Get_Max( Node p )
{
  Node q = p;
while( p )
  {
    q = p;
    p = p->rchild;
  }
return q;
}

//求前驱    
Node Get_Prev(Node p)
{
  Node q = p->pf;
if( p->lchild )
return Get_Max(p->lchild);
while( q != NULL && p == q->lchild)
  {
    p = q;
    q = q->pf;
  }
return q;
}  


//求后继
Node Get_Next(Node p)
{
 Node q = p->pf;
if( p->rchild )
return Get_Min(p->rchild);
while( q != NULL && p == q->rchild )
 {
   p = q;
   q = q->pf;
 }
return q;
}

void preordertravel( Node p )
{
if( p )
 {
    preordertravel(p->lchild);
if( p->pf )
    printf("%d 节点个数%d 它得父亲节点为%d\n", p->v, p->size, p->pf->v);
else
     printf("%d 节点个数%d 它得父亲节点为空\n", p->v, p->size);
    preordertravel(p->rchild);
 }
}

int main( )
{
int N, t;
  srand(time(NULL));
while( scanf("%d",&N) != EOF )
  {
     Node root = NULL;
int flag = 0;
for( int i = 1; i <= N; i++)
     {
       scanf("%d",&t);
       Node q = NewNode(t);
       root = insert(root, q, NULL);
     }
     preordertravel( root );
while( 1 )
     {
      printf("请输入你要删除的数字:\n");
      scanf("%d",&t);
      flag = 0;
      root = del(root, t,flag);
if( flag == 1 )
        puts("成功删除");
else
        puts("未找到");
      preordertravel(root);
      puts("");
      printf("请输入你要查找的后继和前驱：\n");
      scanf("%d",&t);
      Node p = find(root, t);
if( p  )
      {
         Node p1 = Get_Next( p );
         Node q1 = Get_Prev(p);
if( p1 == NULL && q1 == NULL)
            printf("后继为空 前驱为空\n");
else if(p1 == NULL && q1 != NULL)
            printf("后继为空 前驱为%d\n",q1->v);
else if( q1 == NULL && p1 != NULL )
            printf("后继为%d 前驱为空\n",p1->v);
else
            printf("后继为%d 前驱为%d\n",p1->v, q1->v);
      }
else
      puts("你要查找的元素不存在!");
      printf("请输入你要查找的第多少小的元素:\n");
      scanf("%d",&t);
      Node p3 = OS_select(root, t);
if( p3 == NULL )
        puts("不存在");
else
        printf("%d\n", p3->v);
      printf("请输入你要查找的元素秩序:\n");
      scanf("%d",&t);
      Node p4 = find(root, t);
      printf("%d 的秩为%d\n",t, OS_rank(root,p4));
     }
  }
return 0;
}