Skip to main content

二叉搜索树 & 平衡树

参考资料​

简介​

二叉搜索树（Binary Search Tree，BST）满足左子树所有值小于根、右子树所有值大于根，中序遍历即为有序序列，支持 O(h)O(h) 的插入、删除、查询，其中 hh 为树高。但在有序数据下树高可能退化为 O(n)O(n)。平衡树 通过旋转等操作维持 h=O(log⁡n)h=O(\log n)，常用于维护有序集合并支持排名、前驱后继等操作。

Treap​

Treap（Tree + Heap）给每个节点附一个随机优先级，使其按键值满足二叉搜索树性质、按优先级满足堆性质。随机优先级让期望树高为 O(log⁡n)O(\log n)，从而支持 O(log⁡n)O(\log n) 的插入、删除、排名、前驱后继等操作。

竞赛中常用 无旋 Treap（FHQ Treap）：只用 split（按键或按大小分裂）与 merge（合并两棵相对有序的树）两个操作即可实现全部功能，代码简短，且天然支持可持久化与区间翻转。

__gnu_pbds::tree​

__gnu_pbds::tree 是基于红黑树的有序集合，配合 tree_order_statistics_node_update 可 O(log⁡n)O(\log n) 查询元素排名与第 kk 小，省去手写平衡树。

152 Bcpp
#include <bits/extc++.h>
using namespace __gnu_pbds;

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;

笛卡尔树​

笛卡尔树（Cartesian Tree）的节点同时满足两个性质：下标构成 BST（中序遍历即原下标序），权值构成堆。用单调栈维护右链即可 O(n)O(n) 建树。

137 Bcpp
int top=0;
s[++top]=0;
for(int i=1;i<=n;i++)
{
	while(top&&a[s[top]]>a[i])son[i][0]=s[top--];
	if(s[top])son[s[top]][1]=i;
	s[++top]=i;
}

例题​

洛谷 P3369 【模板】普通平衡树

你需要写一种数据结构，来维护一些数，并且提供以下操作：

  1. 插入一个数 xx。
  2. 删除一个数 xx（若有多个相同的数，应只删除一个）。
  3. 定义排名为比当前数小的数的个数 +1+1。查询 xx 的排名。
  4. 查询数据结构中排名为 xx 的数。
  5. 求 xx 的前驱（前驱定义为小于 xx，且最大的数）。
  6. 求 xx 的后继（后继定义为大于 xx，且最小的数）。
洛谷 P6136 【模板】普通平衡树（数据加强版）

您需要动态地维护一个可重集合 MM，并且提供以下操作：

  1. 向 MM 中插入一个数 xx。
  2. 从 MM 中删除一个数 xx（若有多个相同的数，应只删除一个）。
  3. 查询 MM 中有多少个数比 xx 小，并且将得到的答案加一。
  4. 查询如果将 MM 从小到大排列后，排名位于第 xx 位的数。
  5. 查询 MM 中 xx 的前驱（前驱定义为小于 xx，且最大的数）。
  6. 查询 MM 中 xx 的后继（后继定义为大于 xx，且最小的数）。

本题 强制在线，保证所有操作合法（操作 22 保证存在至少一个 xx，操作 4,5,64,5,6 保证存在答案）。

洛谷 P5854 【模板】笛卡尔树

给定一个 1∼n1\sim n 的排列 pp，构建其笛卡尔树。

即构建一棵二叉树，满足：

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 ii 的权值为 pip_i，每个节点的权值满足小根堆的性质。