首页 > 其他 > 详细

二叉树系列之Treap树

时间:2021-07-29 11:02:04      阅读:21      评论:0      收藏:0      [点我收藏+]

技术分享图片

          Treap是一棵拥有键值、优先级两种权值的树 

 

 

1.唯一性

2.期望的插入、删除、查找的时间复杂度都是O(log n)

3.插入

         技术分享图片

 

 

  技术分享图片

 

                                              (灰色为先前位置)

 

 

  旋转代码

void rotate(node* &o,int d){      //d=0,左旋;d=1,右旋
    node *k=o->son[d^1];          //d^1与1-d等价,但是更快
    o->son[d^1]=k->son[d];        //图中的x
    k->son[d]=o;    
    o=k;                          //返回新的根
}

 4.删除

  调整至叶子结点后直接删除

5.分裂与合并问题

6.Treap与名次树问题

  例题:hdu4585 "Shaolin"

  题解地址:https://www.cnblogs.com/ynzhang2020/p/15071130.html

二叉树系列之Treap树

原文:https://www.cnblogs.com/ynzhang2020/p/15070994.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!