二叉搜索树 & 平衡树

Summary

二叉搜索树满足左子树所有值小于根、右子树所有值大于根，中序遍历即有序序列，插入、删除、查询均为 O(h)，但在有序数据下树高会退化到 O(n)。平衡树靠旋转等操作维持对数树高，用于维护有序集合并支持排名、前驱后继。重点讲 Treap：给每个节点附随机优先级，同时满足键的搜索树性质与优先级的堆性质，期望树高对数级；竞赛常用只靠 split 与 merge 两个操作的无旋 FHQ Treap，代码短且支持可持久化与区间翻转。另附 pbds 的红黑树容器，以及用单调栈 O(n) 建笛卡尔树。

参考资料

• 二叉搜索树 & 平衡树 - OI Wiki
• Treap - OI Wiki

简介

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

Treap

Treap（Tree + Heap）给每个节点附一个随机优先级，使其按键值满足二叉搜索树性质、按优先级满足堆性质。随机优先级让期望树高为 $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)$ 查询元素排名与第 $k$ 小，省去手写平衡树。

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)$ 建树。

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. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

洛谷 P6136 【模板】普通平衡树（数据加强版）

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

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

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

洛谷 P5854 【模板】笛卡尔树

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

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

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