【笔记】数据结构-Treap

平衡树,是一种非常高效,可以对值或序列进行一些操作的数据结构,它支持的操作包括但不限于以下几种:

  • 插入一个数。
  • 删除一个数。
  • 求某个数的前驱(即所有小于这个数的数中最大的数)。
  • 求某个数的后继(即所有大于这个数的数中最小的数)。
  • 求某个数的排名(即小于这个数的数的数量再加一)。
  • 求第 K 大的数。
  • 翻转某段区间。

看起来很多操作也可以用权值线段树或线段树来做,而且时间复杂度也和平衡树一样是 O(logn)O(\log n),但不要忘了线段树的空间复杂度,假设要求维护的数值域为 [231,2311][-2^{31},2^{31}-1],权值线段树可就有点不行了,但平衡树的空间复杂度只和数的数量有关,和值域无关,所以即使是 [263,2631][-2^{63},2^{63}-1] 的值域,平衡树也能轻松搞定。

作者

AzuSemisa

发布于

2020-11-20

更新于

2020-11-25

许可协议

评论