Treap

\(\text{Treap}\)是一种通过维护堆和二叉搜索树两重性质来限制树高的平衡树。

每一个节点都被赋予了两个值,称作\(val\)和\(key\),分别按照BST和堆的性质维护:

  • 小根堆:每一个节点的\(key\)都小于等于他的两个子节点的\(key\)
  • 二叉树:每一个节点的\(key\)都比他左子的\(val\)大,比右子的\(val\)小

每一个节点的\(key\)是随机指定的,这样可以保证期望树高为\(\log n\)

继续阅读“Treap”