文章目录 Treap是什么基本结构基本操作初始化修改某个节点的siz左旋右旋插入数x删除数x查找数x的排名查找排名为x的数查找数x的前趋查找数x的后继完整模板 Treap是什么 树堆,在数据结构中也称 T r e a p Treap Treap,是指有一个随机附加域满足堆的性质的…
Treap树堆
Treap是一种平衡化二叉搜索树,在键值key满足二叉搜索树的前提下,增加了priority是满足堆序的条件。可以证明,如果priority的随机的,那么Treap的期望深度是 O ( l o g N ) O(logN) O(logN),也就是说大部分操…
先给出我自己的一份Treap的代码——传送门
一、什么是 Treap T r e a p T r e e H e a p TreapTreeHeap TreapTreeHeap T r e a p Treap Treap是一种平衡树 T r e a p Treap Treap发音为[tri:p] 这个单词的构造选取了 T r e e Tree Tree(树)的前两个字符和 H e a p Heap He…