数据结构之Treap详解
1. 概述
同splay tree一样,treap也是一个平衡二叉树,不过Treap会记录一个额外的数据,即优先级。Treap在以关键码构成二叉搜索树的同时,还按优先级来满足堆的性质。因而,Treap=tree+heap。这里需要注意的是,Treap并不是二叉堆,二叉堆必须是完全二叉树,而Treap可以并不一定是。
2. Treap基本操作
为了使Treap 中的节点同时满足BST性质和最小堆性质,不可避免地要对其结构进行调整,调整方式被称为旋转。在维护Treap 的过程中,只有两种旋转,分别是左旋转(简称左旋)和右旋转(简称右旋)。
左旋一个子树,会把它的根节点旋转到根的左子树位置,同时根节点的右子节点成为子树的根;右旋一个子树,会把它的根节点旋转到根的右子树位置,同时根节点的左子节点成为子树的根。
struct Treap_Node { Treap_Node *left,*right; //节点的左右子树的指针 int value,fix; //节点的值和优先级 }; void Treap_Left_Rotate(Treap_Node *&a) //左旋 节点指针一定要传递引用 { Treap_Node *b=a->right; a->right=b->left; b->left=a; a=b; } void Treap_Right_Rotate(Treap_Node *&a) //右旋 节点指针一定要传递引用 { Treap_Node *b=a->left; a->left=b->right; b->right=a; a=b; }
3. Treap的操作
同其他树形结构一样,treap的基本操作有:查找,插入,删除等。
3.1 查找
同其他二叉树一样,treap的查找过程就是二分查找的过程,复杂度为O(lg n)。
3.2 插入
在Treap 中插入元素,与在BST 中插入方法相似。首先找到合适的插入位置,然后建立新的节点,存储元素。但是要注意新的节点会有一个优先级属性,该值可能会破坏堆序,因此我们要根据需要进行恰当的旋转。具体方法如下:
1. 从根节点开始插入;
2. 如果要插入的值小于等于当前节点的值,在当前节点的左子树中插入,插入后如果左子节点的优先级小于当前节点的优先级,对当前节点进行右旋;
3. 如果要插入的值大于当前节点的值,在当前节点的右子树中插入,插入后如果右子节点的优先级小于当前节点的优先级,对当前节点进行左旋;
4. 如果当前节点为空节点,在此建立新的节点,该节点的值为要插入的值,左右子树为空,插入成功。
Treap_Node *root; void Treap_Insert(Treap_Node *&P,int value) //节点指针一定要传递引用 { if (!P) //找到位置,建立节点 { P=new Treap_Node; P->value=value; P->fix=rand();//生成随机的修正值 } else if (value <= P->value) { Treap_Insert(P->left,r); if (P->left->fix < P->fix) Treap_Right_Rotate(P);//左子节点修正值小于当前节点修正值,右旋当前节点 } else { Treap_Insert(P->right,r); if (P->right->fix < P->fix) Treap_Left_Rotate(P);//右子节点修正值小于当前节点修正值,左旋当前节点 } }
3.3 删除
与BST 一样,在Treap 中删除元素要考虑多种情况。我们可以按照在BST 中删除元素同样的方法来删除Treap 中的元素,即用它的后继(或前驱)节点的值代替它,然后删除它的后继(或前驱)节点。
上述方法期望时间复杂度为O(logN),但是这种方法并没有充分利用Treap 已有的随机性质,而是重新得随机选取代替节点。我们给出一种更为通用的删除方法,这种方法是基于旋转调整的。首先要在Treap 树中找到待删除节点的位置,然后分情况讨论:
情况一,该节点为叶节点或链节点,则该节点是可以直接删除的节点。若该节点有非空子节点,用非空子节点代替该节点的,否则用空节点代替该节点,然后删除该节点。
情况二,该节点有两个非空子节点。我们的策略是通过旋转,使该节点变为可以直接删除的节点。如果该节点的左子节点的优先级小于右子节点的优先级,右旋该节点,使该节点降为右子树的根节点,然后访问右子树的根节点,继续讨论;反之,左旋该节点,使该节点降为左子树的根节点,然后访问左子树的根节点,这样继续下去,直到变成可以直接删除的节点。
BST_Node *root; void Treap_Delete(Treap_Node *&P,int *value) //节点指针要传递引用 { if (value==P->value) //找到要删除的节点 对其删除 { if (!P->right || !P->left) //情况一,该节点可以直接被删除 { Treap_Node *t=P; if (!P->right) P=P->left; //用左子节点代替它 else P=P->right; //用右子节点代替它 delete t; //删除该节点 } else //情况二 { if (P->left->fix < P->right->fix) //左子节点修正值较小,右旋 { Treap_Right_Rotate(P); Treap_Delete(P->right,r); } else //左子节点修正值较小,左旋 { Treap_Left_Rotate(P); Treap_Delete(P->left,r); } } } else if (value < P->value) Treap_Delete(P->left,r); //在左子树查找要删除的节点 else Treap_Delete(P->right,r); //在右子树查找要删除的节点 }
4. Treap应用
Treap可以解决splay tree可以解决的所有问题,具体参见另一篇文章:《数据结构之伸展树详解》
可以这样定义结构体:
struct Treap_Node { Treap_Node *left,*right; //节点的左右子树的指针 int value,fix,weight,size; //节点的值,优先级,重复计数(记录相同节点个数,节省空间),子树大小 inline int lsize(){ return left ?left->size ?0; } //返回左子树的节点个数 inline int rsize(){ return right?right->size?0; } //返回右子树的节点个数 };
5. 总结
Treap 作为一种简洁高效的有序数据结构,在计算机科学和技术应用中有着重要的地位。它可以用来实现集合、多重集合、字典等容器型数据结构,也可以用来设计动态统计数据结构。
6. 参考资料
(1)Treap:http://www.nocow.cn/index.php/Treap
(2)随机平衡二叉查找树Treap 的分析与应用:http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf
相关文章
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 本文主要和大家分享几种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。...2021-01-15
- 这篇文章主要为大家详细的介绍了Redis高效的原因以及分析了Redis高效的数据结构,有需要的朋友可以借鉴参考下,希望能够有所帮助...2021-09-27
- 上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构——线性结构...2020-06-25
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++数据结构与算法之哈夫曼树的实现方法,简单说明了哈夫曼树的原理,并结合具体实例形式分析了C++实现哈夫曼树的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了基于JavaScript的数据结构队列动画实现示例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-06
- 这篇文章主要介绍了数据结构 双向链表的创建和读取详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之动态分配实现串的相关资料,希望通过本文能帮助到大家,让大家实现数据结构中动态分配实现串的实例,需要的朋友可以参考下...2020-04-25
- <? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){...2016-11-25
- 我们在进行编程时,往往会开发诸多的算法,那么我们怎么在那么多算法中找到最好的那个呢?本文主要介绍时间和空间复杂度概念及时间复杂度的求解,预祝读者学习愉快...2021-10-23
- 这篇文章主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构树的双亲表示法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中数据结构之链式基数排序的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之使用链表模拟栈的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了数据结构之树的概念详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-09-10
- 这篇文章主要介绍了C语言 数据结构中栈的实现代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之栈简单操作的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C语言数据结构之迷宫问题,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25