平衡树

本章介绍平衡树的概念，详细讲解 AVL

树的平衡因子、四种平衡旋转操作及代码实现，并简介红黑树、Treap、SBT、B

树和 B +

树等其他平衡树。特别介绍了一种特殊的平衡树——伸展树的基本结构、核心操作、基本操作、序列操作、时间复杂度等内容。

平衡树概念与AVL

回顾二叉排序（查找）树

若其左子树非空，则左子树上所有结点的值均小于根结点的值

若其右子树非空，则右子树上所有结点的值均大于等于根结点的值

其左右子树本身又各是一棵二叉排序树

中序遍历二叉排序树后的结果有什么规律？

AVL树是最先发明的自平衡二叉查找树

二叉排序树的操作－删除

如果所删结点 \(now\)

左右子树有空树：用非空子树树根 \(nex\)

顶替被删结点

否则用左子树中序最末结点 \(nex\)

顶替被删节点 \(now\)，并对 \(nex\) 再次执行删除操作

平衡树

二叉排序树在退化情况下查找与插入性能降低，接近线性而不再是 \(logn\)

\(ASL\)(Average Search

Length)：平均搜索长度

在插入删除的过程中动态调整二叉树的姿态，尽可能保持任意子树的左右子树高度一致，即平衡树。

AVL

AVL树是最先发明的自平衡二叉查找树，基于平衡因子实现

平衡因子：该结点左子树与右子树的高度差

AVL树任一结点的平衡因子只能取：-1、0 或 1

对于一棵有n个结点的AVL树，其高度和ASL都保持在\(O(log2n)\)

判断下面两个树是否是 AVL

重要操作

平衡旋转：

在插入新节点时，需要调整树的结构以保持平衡。主要有以下四种情况：

LL：在左子树的左子树插入节点

平衡因子由 \(1\) 变为 \(2\)

需要进行顺时针旋转

RR：在右子树的右子树插入节点

平衡因子由 \(-1\) 变为 \(-2\)

需要进行逆时针旋转

LR：在左子树的右子树插入节点

平衡因子由 \(1\) 变为 \(2\)

需要先对左子树逆时针旋转，再对根顺时针旋转

RL：在右子树的左子树插入节点

平衡因子由 \(-1\) 变为 \(-2\)

需要先对右子树顺时针旋转，再对根逆时针旋转

参考模板

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117/*注释内容由AI生成，仅供参考*/const int maxn = 1e5 + 10; // 定义最大节点数struct Node { // 定义AVL树节点结构 int key; // 键，用于二叉树排序 int data; // 数据域，不参与排序的数据 int left; // 左子树指针 int right; // 右子树指针 int height; // 节点高度 void Init(){data = key = left = right = height = -1;} // 初始化节点 void Init(int k_, int d_=0){Init(); key = k_; data = d_;} // 带参数初始化 Node(){Init();} // 默认构造函数 Node(int k_, int d_=0){Init(k_, d_);} // 带参数构造函数};Node tr[maxn]; // 节点数组int root, tp; // root为根节点，tp为内存分配指针inline int UpdateHeight(int now) { // 更新节点高度 int lh = tr[now].left == -1 ? 0 : tr[tr[now].left].height; // 获取左子树高度 int rh = tr[now].right == -1 ? 0 : tr[tr[now].right].height; // 获取右子树高度 return tr[now].height = (lh > rh ? lh : rh) + 1; // 更新当前节点高度}inline int HeightDiff(int now) { // 计算平衡因子 int lh = tr[now].left == -1 ? 0 : tr[tr[now].left].height; // 获取左子树高度 int rh = tr[now].right == -1 ? 0 : tr[tr[now].right].height; // 获取右子树高度 return lh - rh; // 返回平衡因子（左子树高度 - 右子树高度）}int LL(int an) { // LL型旋转（顺时针旋转） int bn = tr[an].left; // 保存左子节点 int dn = tr[bn].right; // 保存左子节点的右子树 tr[bn].right = an; // 调整指针关系 tr[an].left = dn; UpdateHeight(an); // 更新高度 UpdateHeight(bn); return bn; // 返回新的根节点}int RR(int an) { // RR型旋转（逆时针旋转） int bn = tr[an].right; // 保存右子节点 int dn = tr[bn].left; // 保存右子节点的左子树 tr[bn].left = an; // 调整指针关系 tr[an].right = dn; UpdateHeight(an); // 更新高度 UpdateHeight(bn); return bn; // 返回新的根节点}int LR(int an) { // LR型旋转（先逆时针后顺时针） tr[an].left = RR(tr[an].left); // 先对左子树进行逆时针旋转 return LL(an); // 再对根节点进行顺时针旋转}int RL(int an) { // RL型旋转（先顺时针后逆时针） tr[an].right = LL(tr[an].right); // 先对右子树进行顺时针旋转 return RR(an); // 再对根节点进行逆时针旋转}void Insert(int &now, int key, int data=0) { // 插入节点 if(now == -1) { // 如果当前节点为空 now = tp ++; // 分配新节点 tr[now].Init(key, data); // 初始化新节点 } else if(key < tr[now].key) { // 如果键值小于当前节点 Insert(tr[now].left, key, data); // 递归插入左子树 if(HeightDiff(now) == 2) // 如果平衡因子为2 now = key < tr[tr[now].left].key ? // 判断是LL还是LR型 LL(now) : LR(now); // 进行相应的旋转 } else if(key > tr[now].key) { // 如果键值大于当前节点 Insert(tr[now].right, key, data); // 递归插入右子树 if(HeightDiff(now) == -2) // 如果平衡因子为-2 now = key > tr[tr[now].right].key ? // 判断是RR还是RL型 RR(now) : RL(now); // 进行相应的旋转 } UpdateHeight(now); // 更新当前节点高度}void Delete(int &now, int key) { // 删除节点 if(now == -1) return; // 如果节点为空，直接返回 else if(key < tr[now].key) { // 如果键值小于当前节点 Delete(tr[now].left, key); // 递归删除左子树 } else if(key > tr[now].key) { // 如果键值大于当前节点 Delete(tr[now].right, key); // 递归删除右子树 } else { // 找到要删除的节点 if(tr[now].left == -1) { // 如果左子树为空 now = tr[now].right; // 用右子树替代 } else if(tr[now].right == -1) { // 如果右子树为空 now = tr[now].left; // 用左子树替代 } else { // 如果左右子树都不为空 int nd; // 找到左子树中的最大值 for(nd = tr[now].left; ; nd = tr[nd].right) if(tr[nd].right == -1) break; tr[now].key = tr[nd].key; // 用最大值替代当前节点 tr[now].data = tr[nd].data; Delete(tr[now].left, tr[nd].key); // 递归删除最大值节点 } } if(now == -1) return; // 如果节点为空，直接返回 UpdateHeight(now); // 更新当前节点高度 if(HeightDiff(now) == 2) { // 如果平衡因子为2 now = HeightDiff(tr[now].left) >= 0 ? // 判断是LL还是LR型 LL(now) : LR(now); // 进行相应的旋转 } else if(HeightDiff(now) == -2) { // 如果平衡因子为-2 now = HeightDiff(tr[now].right) <= 0 ? // 判断是RR还是RL型 RR(now) : RL(now); // 进行相应的旋转 }}

其它各种平衡树简介

红黑树

红黑树是一种广泛使用的平衡树,它通过节点的颜色来维持平衡:

每个节点要么是红色,要么是黑色

根节点是黑色

叶子节点(NIL)是黑色

如果一个节点是红色,则它的子节点必须是黑色

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

相比AVL树,红黑树: - 牺牲了部分平衡性来换取更少的旋转操作 -

插入删除的维护成本更低 - 被广泛应用于标准库实现中(如C++ STL)

Treap

Treap = Tree + Heap,是一种随机化的平衡二叉树:

每个节点除了键值外还随机分配一个优先级

按照键值组成二叉搜索树

按照优先级组成最大堆

通过旋转操作来维护堆的性质

期望的高度是O(log n)

SBT (Size Balanced Tree)

SBT是由ICPC选手陈启峰发明的一种平衡树:

通过维护子树大小(size)而不是高度来保持平衡

平衡条件比较简单:较小子树的大小不小于较大子树的子树大小

实现相对简单,只需要维护size信息

各种操作的时间复杂度都是O(log n)

在某些情况下比红黑树更容易实现和维护

B树和B+树

这两种树主要用于数据库和文件系统:

允许每个节点包含多个键值

所有叶子节点都在同一层

B+树的非叶节点只存储键值,数据都存在叶子节点

特别适合磁盘等外存储器的存储方式

广泛应用于数据库索引和文件系统中

用STL解决简单平衡树问题

一些只需要利用平衡树性质，但没有细化考查的问题，可以用STL的map或set完成。

std::map

由红黑树实现的数据有序，所有的“键”插入后都是有序的，比如可以用

lower_bound 找特定键的前驱

123456789std::map myMap;// 假设 myMap 已经填充了一些数据auto predecessorIt = myMap.lower_bound(targetKey);if (predecessorIt != myMap.begin()) { // 回退一步得到前驱 --predecessorIt;} else { // 没有前驱}

std::set

是集合的概念，相对map来说它只有“键”没有“值”，在不需要数据映射的时候用

set 更简洁，比如找一个键的前驱

1234567891011121314#include #include int main() { std::set mySet = {1, 3, 5, 7, 9}; int target = 5; auto successorIt = mySet.upper_bound(target); if (successorIt != mySet.end()) { std::cout << "Successor: " << *successorIt << std::endl; } else { std::cout << "No successor found." << std::endl; }}

map和set

都是平衡树实现，在简单场景中可以不用繁琐地自己去实现平衡树，在比赛中节约大量时间。

伸展树（Splay）

伸展树通过"伸展"操作将最近访问的节点移动到根节点，从而保证树的高度在均摊意义下为\(O(log n)\)。

传统平衡树的操作，伸展树基本都可以完成，但可能复杂度高一些，非特异需求不建议用伸展树。

除传统平衡树支持的操作外，伸展树更擅长执行以下操作:

区间操作：通过将区间两端点伸展到根节点附近，可以方便地进行区间修改和查询

最近访问优化：由于最近访问的节点会被移动到根部，对于有局部性的访问模式效率更高

动态统计：可以方便地维护子树信息，适合需要频繁修改和查询统计信息的场景

序列操作：通过中序遍历性质，可以方便地进行序列的分割、合并等操作

所以掌握一种传统平衡树（比如AVL或SBT）外，还应当掌握伸展树的使用。

基本结构

伸展树的基本结构包含以下信息：

12345678910111213struct SplayNode { int ch[2]; // 左右儿子 int fa; // 父亲节点 int val; // 节点值 int cnt; // 值出现次数 int sz; // 子树大小 int lz; // 懒标记(用于区间操作) void Init() { ch[0] = ch[1] = fa = val = cnt = sz = lz = 0; } SplayNode() { Init(); }};

每个节点需要维护以下信息：

ch[2]：存储左右子节点的编号

fa：存储父节点的编号

val：节点的值

cnt：该值出现的次数

sz：以该节点为根的子树大小

lz：用于区间操作的懒标记

核心操作

1. 旋转操作

旋转是Splay树的基础操作，用于将一个节点上移一层。旋转操作需要保证：

不破坏二叉查找树的性质

正确维护父子关系

更新节点信息

旋转分为两种情况：

当节点是其父节点的左儿子时，进行右旋

当节点是其父节点的右儿子时，进行左旋

12345678910111213141516171819202122void Rotate(int x) { int y = sn[x].fa, z = sn[y].fa; int chk = Ws(x); // 判断x是y的左儿子还是右儿子 // 更新y的子节点 sn[y].ch[chk] = sn[x].ch[chk ^ 1]; if(sn[y].ch[chk]) sn[sn[y].ch[chk]].fa = y; // 更新x和y的关系 sn[x].ch[chk ^ 1] = y; sn[y].fa = x; // 更新x和z的关系 sn[x].fa = z; if(z) sn[z].ch[y == sn[z].ch[1]] = x; // 维护节点信息 Maintain(y); Maintain(x);}

2. 伸展操作

伸展操作是Splay树的核心，它将一个节点通过一系列旋转移动到根节点。伸展操作分为三种情况：

zig：当父节点是根节点时，直接旋转

zig-zig：当节点和父节点都是左儿子或都是右儿子时，先旋转父节点，再旋转当前节点

zig-zag：当节点和父节点一个是左儿子一个是右儿子时，连续旋转两次当前节点

123456void Splay(int x, int target=0) { for(int y = sn[x].fa; (y = sn[x].fa) != target; Rotate(x)) if(sn[y].fa != target) Rotate(Ws(x) == Ws(y) ? y : x); if(!target) rt = x;}

基本操作

插入操作

插入操作的基本步骤：

如果树为空，直接创建新节点作为根节点

否则，按照二叉查找树的性质找到插入位置

如果找到相同值的节点，增加计数

否则创建新节点

最后进行伸展操作，将新节点移到根节点

1234567891011121314151617181920212223void Insert(int k) { if(!rt) { rt = Add(k); return; } int cur = rt, f = 0; while(true) { if(sn[cur].val == k) { sn[cur].cnt++; Maintain(cur); Maintain(f); Splay(cur); break; } f = cur; cur = sn[cur].ch[sn[cur].val < k]; if(!cur) { int nn = Add(k, f); Splay(nn); break; } }}

删除操作

删除操作的基本步骤：

首先找到要删除的节点并伸展到根

如果节点计数大于1，直接减少计数

如果节点没有子节点，直接删除

如果节点只有一个子节点，用子节点替代

如果节点有两个子节点，找到前驱节点替代，然后删除前驱节点

12345678910111213141516171819202122232425262728void Del(int k) { Rank(k); if(sn[rt].cnt > 1) { sn[rt].cnt--; Maintain(rt); return; } if(!sn[rt].ch[0] && !sn[rt].ch[1]) { Clear(rt); rt = 0; return; } // 处理只有一个子节点的情况 for(int i = 0; i <= 1; i++) { if(sn[rt].ch[i]) continue; int cur = rt; rt = sn[rt].ch[i ^ 1]; sn[rt].fa = 0; Clear(cur); return; } // 处理有两个子节点的情况 int cur = rt, x = RtPre(); sn[sn[cur].ch[1]].fa = x; sn[x].ch[1] = sn[cur].ch[1]; Clear(cur); Maintain(rt);}

前驱后继查询

前驱后继查询的基本步骤：

前驱：找到左子树中的最大值

后继：找到右子树中的最小值

查询后将节点伸展到根

1234567891011121314151617int RtPre(int cur=0) { if(!cur) cur = sn[rt].ch[0]; else cur = sn[cur].ch[0]; if(!cur) return cur; while(sn[cur].ch[1]) cur = sn[cur].ch[1]; Splay(cur); return cur;}int RtNxt(int cur=0) { if(!cur) cur = sn[rt].ch[1]; else cur = sn[cur].ch[1]; if(!cur) return cur; while(sn[cur].ch[0]) cur = sn[cur].ch[0]; Splay(cur); return cur;}

序列操作

Splay树也可以用于维护序列信息。与线段树相比，Splay树虽然常数较大，但支持更复杂的序列操作，如区间翻转等。

将序列建成的Splay树具有以下性质：

中序遍历相当于原序列从左到右的遍历

每个节点代表序列中的一个元素

一棵子树代表序列中的一段区间

区间操作

以区间翻转为例，操作步骤如下：

将区间左端点前一个节点伸展到根

将区间右端点后一个节点伸展到根的右儿子

此时根的右儿子的左子树就是目标区间

对该子树进行翻转操作并打上懒标记

12345678910void DFS(int cur, int k) { if(!cur) return; PushDown(cur); DFS(sn[cur].ch[0], k); DFS(sn[cur].ch[1], k); sn[sn[cur].fa].ch[Ws(cur)] = 0; Maintain(sn[cur].fa); tbi.push_back(sn[cur].val); cct.push_back(sn[cur].cnt);}

懒标记管理

对于区间操作，需要维护懒标记：

123456789101112void PushDown(int x) { if(!x || !sn[x].lz) return; UpdateLz(sn[x].ch[0], sn[x].lz); UpdateLz(sn[x].ch[1], sn[x].lz); sn[x].lz = 0;}void UpdateLz(int x, LL lz) { if(!x) return; sn[x].lz += lz; sn[x].val -= lz;}

在访问节点时需要下传标记：

12345678void Splay(int x, int target=0) { std::vector path; for(int f = x; f; f = sn[f].fa) path.push_back(f); for(int i = path.size() - 1; i >= 0; i--) PushDown(path[i]); for(int y; (y = sn[x].fa) != target; Rotate(x)) if(sn[y].fa != target) Rotate(Ws(x) == Ws(y) ? y : x); if(!target) rt = x;}

应用示例

以K小值查询为例，展示了Splay树处理区间操作的能力：

123456789101112131415161718void UpperBound(int k) { int lastLager = 0, cur = rt; while(cur) { PushDown(cur); if(k < sn[cur].val) { lastLager = cur; if(!sn[cur].ch[0]) break; cur = sn[cur].ch[0]; } else { if(!sn[cur].ch[1]) break; cur = sn[cur].ch[1]; } } if(sn[cur].val <= k) cur = lastLager; if(cur) Splay(cur); return cur;}

这个例子展示了如何：

维护区间信息

处理懒标记

进行区间查询和修改

通过这些操作，Splay树可以高效地处理各种序列操作问题。

时间复杂度

单次操作均摊复杂度：\(O(log

n)\)

空间复杂度：\(O(n)\)