数据结构——平衡树

GJX_Algorithm · 2025-03-01 19:08:28 · 算法·理论

平衡树

二叉搜索树＆平衡树

二叉搜索树（Binary Search Tree）基础

定义：二叉搜索树是一种二叉树结构，满足如下性质：
- 每个节点的左子树所有节点的值小于当前节点的值。
- 每个节点的右子树所有节点的值大于当前节点的值。
- 左右子树也分别为二叉搜索树。
时间复杂度分析：
- 理想情况（高度最小）：二叉搜索树为完全平衡树时，若总节点数为 n，则树的高度为 \lfloor \log_2n \rfloor。其插入、删除、查询操作的时间复杂度皆为 O(\log n)。
- 最坏情况（高度最大）：二叉搜索树退化成链表时，若总节点数为 n，则树的高度为 n。其插入、删除、查询操作的时间复杂度皆为 O(n)。

平衡树（Balance Tree）基础

广泛定义：是指一棵树形结构，对任意节点 x，其左右子树的高度差不超过 1。
二叉搜索平衡树（后文提到的平衡树皆指二叉搜索平衡树）：上文提到 BST 的退化问题，为了解决，利用平衡树特定的平衡性质，使二叉搜索树的高度始终保持理想情况。以下给出普通 BST（退化的 BST）与经平衡后的 BST 的区别：

算法竞赛中常见的平衡树实现，本文重点介绍 FHQ-Treap：

平衡树类型平衡策略

Treap 随机优先级，左旋与右旋

Splay 贪心

FHQ-Treap（无旋 Treap）无旋，分裂+合并

平衡树类型	平衡策略
Treap	随机优先级，左旋与右旋
Splay	贪心
FHQ-Treap（无旋 Treap）	无旋，分裂+合并

FHQ-Treap 的实现

为什么要选择 FHQ-Treap？
- 无旋操作：目前笔者只学过 FHQ-Treap，似乎分裂与合并比左旋右旋更容易理解？
- 天然支持区间操作：结合延迟标记（如区间翻转），之后文艺平衡树会讲到。
- 高效稳定：所有操作严格 O(\log n)。

数据结构的定义与初始化：

struct node
{
  int val, rnk, lc, rc, size; // 值、优先级、左右子节点、子树的大小
}tree[N];
int tot, root; // 总节点数与根节点

功能：储存树的信息。

结点的管理

void update(int k)
{
  tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1;
  return ;
}
int add_node(int val) 
{
  tree[++tot].size = 1;
  tree[tot].val = val;
  tree[tot].lc = tree[tot].rc = 0;
  tree[tot].rnk = rand(); //Treap 的基本策略，随机优先级
  return tot; //返还对应的结点编号
}

功能：
update：统计子树大小，左儿子子树大小+右儿子子树大小+自己。
add_node：新建节点并初始化结点信息。

分裂
- 主要思路如图：

  void split(int k, int &a, int &b, int val) 
  {
      if(k == 0) // 结点不存在
    {
          a = b = 0;
          return ;
      }
      if(tree[k].val <= val) // 按值分裂，以 k 为根的子树
    {
          a = k;
          split(tree[k].rc, tree[k].rc, b, val); // 继续分裂以 k 的右儿子为根的子树，分成 k 的右儿子本身与 b 树
      } 
    else 
    {
          b = k;
          split(tree[k].lc, a, tree[k].lc, val);
      }
      update(k);
      return ;
  }

功能：给定一棵平衡树 k，按照某个权值 val，分裂成平衡树 a 和 b，且 a 树所有点的权值不超过 val，b 树的所有点权大于 val。

合并
- 主要思路如图：

  void merge(int &k, int a, int b)
  {
      if(a == 0 || b == 0) 
    {
          k = a + b;
          return ;
      }
      if(tree[a].rnk < tree[b].rnk) // a 的优先级更高，a 做根结点，且 a 的右孩子与 b 竞争成为 a 的右孩子
    {
          k = a;
          merge(tree[a].rc, tree[a].rc, b);
      } 
    else 
    {
          k = b;
          merge(tree[b].lc, a, tree[b].lc);
      }
      update(k);
      return ;
  }

功能：将两棵平衡树 a 和 b 合并成一棵平衡树 k，且保证 a 树的点权都小于 b 树的点权。

插入

void insert(int &k, int val) 
{
  int a = 0, b = 0, cur = add_node(val); 
  split(k, a, b, val);
  merge(a, a, cur);
  merge(k, a, b);
  return ;
}
void del(int &k, int val) 
{
  int a = 0, b = 0, z = 0;
  split(k, a, b, val); // 先把比 val 大的子树划出去
  split(a, a, z, val - 1); // 把值为 val 的节点分裂出来，成为 z 树
  merge(z, tree[z].lc, tree[z].rc); // 将待删除的 z 节点的左右子树合并，取代 z 的位置
  merge(a, a, z);
  merge(k, a, b);
  return ;
}

功能：
insert：插入新值 val，通过分裂找到位置后合并。
del：删除值为 val 的节点，处理重复值情况。

查询

int find_num(int k, int x) 
{
  while(tree[tree[k].lc].size + 1 != x) 
{
      if(tree[tree[k].lc].size >= x)
          k = tree[k].lc;
      else 
    {
          x -= tree[tree[k].lc].size + 1;
          k = tree[k].rc;
      }
  }
  return tree[k].val;
}
int find_rank(int &k, int val) 
{
  int a = 0, b = 0;
  split(k, a, b, val - 1); // 分裂出 <val 的节点
  int tmp = tree[a].size + 1;
  merge(k, a, b);
  return tmp;
}
int prev(int &k, int val) 
{
  int a = 0, b = 0;
  split(k, a, b, val - 1);
  int tmp = find_num(a, tree[a].size); // a树的最大值即前驱
  merge(k, a, b);
  return tmp;
}
int suf(int &k, int val)
{
  int a = 0, b = 0;
  split(k, a, b, val);
  int tmp = find_num(b, 1); // b树的最小值即后继
  merge(k, a, b);
  return tmp;
}

功能：
find_num：通过遍历树结构找到第 k 小的元素。
find_rank：查询值 val 的排名（比 val 小的元素数量 + 1）。
prev 和 suf：分别通过分裂树找到前驱（比 val 小的最大元素）和后继（比 val 大的最小元素）。

文艺平衡树

什么是文艺平衡树？

定义：文艺平衡树泛指支持区间操作的平衡树，例如：
- 区间翻转：将指定区间内的元素逆序。
- 区间求和/最值：快速查询区间内的统计值。
- 区间赋值：批量修改区间内的元素。
核心需求：在维持平衡树性质的同时，高效处理区间操作，时间复杂度需保持在 O(\log n)。

FHQ-Treap 的文艺平衡树实现

懒惰标记：说起区间操作，相比读者会想起经典的线段树，那线段树在某些方面的核心操作就是懒惰标记（Lazy Tag）。
- 原理：将区间操作的修改暂时记录在结点标记中，仅在必要时（如查询或进一步分裂）下传给子结点。
- 示例：区间翻转。
```
void pushdown(int k) 
{
if (tree[k].rev) 
{
    swap(tree[k].lc, tree[k].rc); // 交换左右子节点
    tree[tree[k].lc].rev ^= 1; // 下传标记到左子树
    tree[tree[k].rc].rev ^= 1; // 下传标记到右子树
    tree[k].rev = 0; // 清除当前节点的标记
}
return ;
}
```

区间操作

分裂提取区间：通过两次split分离出目标区间。
应用标记：在区间根节点上设置标记（如 rev ^= 1）。
合并还原树：将处理后的子树合并回原树。

示例：区间翻转。

void reverse(int l, int r) 
{
int a, b, c;
// 分割出前 l - 1 个节点 a 和剩余部分 b + c
split(root, a, b, l - 1);
// 从剩余部分分割出 r - l + 1 个节点 b 和剩余部分 c
split(b, b, c, r - l + 1);
tree[b].rev ^= 1; // 标记翻转
merge(a, a, b); // 合并 a 和翻转后的 b
merge(root, a, c); // 合并得到最终树
return ;
}

完整代码示例

P3369 【模板】普通平衡树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
struct node 
{
    int val, rnk, lc, rc, size;
}tree[N];
int n, tot, root;
void update(int k)
{
    tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1;
    return ;
}
int add_node(int val) 
{
    tree[++tot].size = 1;
    tree[tot].val = val;
    tree[tot].lc = tree[tot].rc = 0;
    tree[tot].rnk = rand();
    return tot;
}
void split(int k, int &a, int &b, int val) 
{
    if (k == 0) 
    {
        a = b = 0; 
        return ;
    }
    if (tree[k].val <= val)
    {
        a = k;
        split(tree[k].rc, tree[k].rc, b, val);
    } 
    else 
    {
        b = k;
        split(tree[k].lc, a, tree[k].lc, val);
    }
    update(k);
    return ;
}
void merge(int &k, int a, int b) 
{
    if (a == 0 || b == 0) 
    {
        k = a + b;
        return ;
    }
    if (tree[a].rnk < tree[b].rnk) 
    {
        k = a;
        merge(tree[a].rc, tree[a].rc, b);
    } 
    else 
    {
        k = b;
        merge(tree[b].lc, a, tree[b].lc);
    }
    update(k);
    return ;
}
void insert(int &k, int val) 
{
    int a = 0, b = 0, cur = add_node(val); 
    split(k, a, b, val);
    merge(a, a, cur); 
    merge(k, a, b);
    return ;
}
void del(int &k, int val) 
{
    int a = 0, b = 0, z = 0;
    split(k, a, b, val);
    split(a, a, z, val - 1); 
    merge(z, tree[z].lc, tree[z].rc);
    merge(a, a, z);
    merge(k, a, b);
    return ;
}
int find_num(int k, int x) 
{
    while (tree[tree[k].lc].size + 1 != x) 
    {
        if (tree[tree[k].lc].size >= x)
            k = tree[k].lc;
        else 
        {
            x -= tree[tree[k].lc].size + 1;
            k = tree[k].rc;
        }
    }
    return tree[k].val;
}
int find_rank(int &k, int val) 
{
    int a = 0, b = 0;
    split(k, a, b, val - 1);
    int tmp = tree[a].size + 1;
    merge(k, a, b);
    return tmp;
}
int prev(int &k, int val) 
{
    int a = 0, b = 0;
    split(k, a, b, val - 1);
    int tmp = find_num(a, tree[a].size);
    merge(k, a, b);
    return tmp;
}
int suf(int &k, int val)
{
    int a = 0, b = 0;
    split(k, a, b, val);
    int tmp = find_num(b, 1);
    merge(k, a, b);
    return tmp;
}
int main() 
{
    cin >> n;
    root = 0;
    srand(time(0));
    for (int i = 1; i <= n; i++) 
    {
        int op, val;
        cin >> op >> val;
        if (op == 1) 
            insert(root, val);
        else if (op == 2) 
            del(root, val);
        else if (op == 3) 
            cout << find_rank(root, val) << "\n";
        else if (op == 4) 
            cout << find_num(root, val) << "\n";
        else if (op == 5) 
            cout << prev(root, val) << "\n";
        else 
            cout << suf(root, val) << "\n";
    }
    return 0;
}

P3391 【模板】文艺平衡树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node 
{
    int val, rnk, lc, rc, size;
    bool rev;
}tree[N];
int n, m, root, tot;
void update(int k) 
{
    tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1;
    return ;
}
void pushdown(int k) 
{
    if (tree[k].rev) 
    {
        swap(tree[k].lc, tree[k].rc);
        tree[tree[k].lc].rev ^= 1;
        tree[tree[k].rc].rev ^= 1;
        tree[k].rev = 0;
    }
    return ;
}
int add_node(int val) 
{
    tree[++tot].size = 1;
    tree[tot].val = val;
    tree[tot].lc = tree[tot].rc = 0;
    tree[tot].rnk = rand();
    tree[tot].rev = 0;
    return tot;
}

void split(int k, int &a, int &b, int sz) 
{
    if (k == 0) 
    {
        a = b = 0;
        return;
    }
    pushdown(k);
    if (tree[tree[k].lc].size + 1 <= sz) 
    {
        a = k;
        split(tree[k].rc, tree[k].rc, b, sz - tree[tree[k].lc].size - 1);
    } 
    else 
    {
        b = k;
        split(tree[k].lc, a, tree[k].lc, sz);
    }
    update(k);
    return ;
}
void merge(int &k, int a, int b) 
{
    if (a == 0 || b == 0) 
    {
        k = a + b;
        return;
    }
    if (tree[a].rnk < tree[b].rnk) 
    {
        pushdown(a);
        k = a;
        merge(tree[a].rc, tree[a].rc, b);
    } 
    else 
    {
        pushdown(b);
        k = b;
        merge(tree[b].lc, a, tree[b].lc);
    }
    update(k);
    return ;
}
void insert(int &k, int val) 
{
    int a = 0, b = 0, cur = add_node(val); 
    split(k, a, b, val);
    merge(a, a, cur); 
    merge(k, a, b);
    return ;
}
void reverse(int l, int r) 
{
    int a = 0, b = 0, c = 0;
    split(root, a, b, l - 1);
    split(b, b, c, r - l + 1);
    tree[b].rev ^= 1;
    merge(a, a, b);
    merge(root, a, c);
    return ;
}
void print(int k) 
{
    if (k == 0) return;
    pushdown(k);
    print(tree[k].lc);
    cout << tree[k].val << " ";
    print(tree[k].rc);
    return ;
}
int main() 
{
    cin >> n >> m;
    root = 0;
    srand(time(0));
    for (int i = 1; i <= n; i++)
        insert(root, i);
    for (int i = 1; i <= m; i++) 
    {
        int l, r;
        cin >> l >> r;
        reverse(l, r);
    }
    print(root);
    return 0;
}

练习

P1486 [NOI2004] 郁闷的出纳员
P2234 [HNOI2002] 营业额统计
P3224 [HNOI2012] 永无乡
P3850 [TJOI2007] 书架
P3765 总统选举
P5217 贫穷

数据结构——平衡树

平衡树

二叉搜索树 ＆ 平衡树

二叉搜索树（Binary Search Tree）基础

平衡树（Balance Tree）基础

FHQ-Treap 的实现

文艺平衡树

什么是文艺平衡树？

FHQ-Treap 的文艺平衡树实现

完整代码示例

练习

二叉搜索树＆平衡树