数据结构之Treap详解(2)

时间:2014-08-30 02:29来源:网络整理作者:网络点击: 次

分享到：

4. Treap应用 Treap可以解决splay tree可以解决的所有问题，具体参见另一篇文章：《数据结构之伸展树详解》可以这样定义结构体： struct Treap_Node { Treap_No

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