二叉堆与二叉查找树的结合应用——treap

Knuth学徒

我刚才发了篇介绍二叉堆的帖子，而且我把二叉堆的常用操作实现代码全部写了一遍，如果没看过那篇帖子的请点这个链接：https://www.chinapyg.com/viewthr ... &extra=page%3D1

       其实 二叉堆的思想远不止那些，它还可以应用到二叉查找树中。

/* **************************废话开始**************************************
                           
       众所周知，二叉查找树如果是平衡的话，那么查找一个元素所需要的时间为 O(logN)，但是维护平衡需要很繁琐的操作，比如 平衡二叉搜索树它需要维护节点的 BalanceFactor,即平衡因子，再通过非常多的情况进行旋转，常常会把人搞晕，尽管我算是搞明白了。。。。
       这里我推荐一种非常受人青睐的树，treap。    为什么它如此受欢迎，因为它的代码编写非常容易，情况非常少。而导致这种简单的原因就在于用到了 “二叉堆” 的思想。
       我们知道，一个最基本的二叉排序树对于插入序列如果是有序的，那么这些序列将会根据排序树的定义全部插入到节点的左边或者全部插入到节点的右边。    这样的话，二叉排序树就变成一条斜着的链条，查找和插入的速度退化成O(N),那就和线性表的顺序查找没有任何区别了——甚至更慢。

*******************************废话结束*************************************/

       treap用到了一个随机化的思想，使得它不仅是根据关键字的是否有序来插入树结构，它的每个节点还有一个随机生成的修正值fix,使得树中所有节点的修正值满足 二叉堆的性质，这样，数据几乎不会“有序的插入”。

      注：以下代码是在记事本中敲出的，也许有错误。。。。

      treap节点的结构：
      struct TreapNode{
                int val;
                int fix;
                struct TreapNode *lch,*rch;
     }Node,*Treap;

     插入函数的实现：

1. ////////////////////////////////////////////////////////////////////////////
   
2. //  函数名：insert()
   
3. //  参数：root根节点,data键值
   
4. //  前提：None
   
5. //  用法:  insert(root,18)
   
6. //  描述:  在根节点的子树中插入一个元素
   
7. /////////////////////////////////////////////////////////////////////////////
   
8. 
   
9. Treap insert(Treap root,int data)
   
10. 
    
11. {
    
12.         if(!root) //叶子节点的子节点
    
13.         {
    
14.                 Treap root = new Node;
    
15.                 root -> val = data;
    
16.                 root -> fix = rand()   //生成一个随机修正值;
    
17.                 root -> lch = root -> rch = NULL;
    
18.                 return root;    //返回指针
    
19.         }
    
20.         else if(data < root -> val)   //左子树插入
    
21.         {
    
22.                 root -> lch = insert(root->lch,data);
    
23.                 if(root -> lch -> fix < root -> fix)   //不满足堆性质
    
24.                          root =  R_rot (root);   //右旋
    
25.                 return root;
    
26.          }
    
27.          else  //右子树插入
    
28.          {
    
29.                 root -> rch = insert(root -> rch,data);
    
30.                 if(root -> rch -> fix < root -> fix)    //不满足堆性质
    
31.                           root = L_rot(root);   //左旋
    
32.                 return root;   
    
33.           }
    
34. }

复制代码

删除函数：

（1）删除函数和BST树类似，如果是叶子节点就直接释放内存，如果只有一个子节点，那么就让那个子节点代替。

（2）如果有两个非空子节点，那么就通过左旋或者右旋直到旋转到 （1）的情况，左旋或者右旋要根据堆的性质旋转。

1. ////////////////////////////////////////////////////////////////////////////
   
2. //  函数名：remove()
   
3. //  参数：root根节点,data键值
   
4. //  前提：None
   
5. //  用法:  remove(root,18)
   
6. //  描述:  在根节点的子树中删除一个元素
   
7. /////////////////////////////////////////////////////////////////////////////
   
8. 
   
9. Treap remove(Treap root,int data)
   
10. {
    
11.         if(data == root -> val)  //找到待删除节点指针 root
    
12.        {
    
13.                   if(!root->lch || !root->rch )  对应(1)，可以直接删除.
    
14.                   {
    
15.                              Treap temp =  root;
    
16.                              if(!root -> rch)   //如果右节点是空的
    
17.                                       root = root -> lch;  //用左节点代替
    
18.                              else
    
19.                                       root = root -> rch; //用右节点代替
    
20.                              delete  temp;   
    
21.                              return root;
    
22.                     }
    
23.                     else  //(2)，该节点有两个非空子节点
    
24.                     {
    
25.                              if(root -> lch -> fix < root -> fix)   //左子节点修正值小
    
26.                              {
    
27.                                         root = R_rot(root);   //右旋
    
28.                                         root ->lch = remove(root -> lch,data);
    
29.                                         return root;
    
30.                              }
    
31.                              else   //右子节点修正值小
    
32.                             {
    
33.                                         root = L_rot(root);
    
34.                                         root -> rch = remove(root -> rch,data);
    
35.                                         return root;
    
36.                              }
    
37.                      }
    
38.         }
    
39.         else if(data < root -> val)  
    
40.         {
    
41.                      root -> lch = remove(root -> lch, data) ; //在左子树删除
    
42.         }
    
43.         else
    
44.         {
    
45.                      root -> rch = remove(root -> rch,data); //在右子树删除
    
46.         }
    
47.         return root;  
    
48. }

复制代码

**************************************************
        这种树的写法和我以前说的 SBT 写法都非常简单，甚至比SBT更为简洁，当然SBT作为一种创新性的数据结构也是很牛的，关于SBT的详细代码见我写的这篇帖子：https://www.chinapyg.com/viewthr ... &extra=page%3D1

        它不能严格证明出 每次插入、删除、查找的效率都是O(logN),但是 由于随机的性质，可以知道，它退化成链表的概率微乎其微。。

**************************************************

Knuth学徒

Treap 树作为一个非常实用的数据结构我觉得掌握一下没坏处的。。。。

Knuth学徒

回复 3# wlm2421331


    寒，只是介绍一种实用的数据结构，里面的代码是经过我的优化的。