Treap树各种操作

谁借莪１个温暖的怀抱￠ 2021-10-19 01:00 265阅读 0赞

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

1.插入元素

2.删除元素

3.查找元素

4.求第K小元素

5确定一个元素秩

6求最大值

7求最小值

8遍历

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/03/03/2378737.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/fc5db19a662b457ab39d730fbd86a072.png