AVL树

平衡树：一棵包含 N 个节点的平衡树，其树高 h 始终保持在 O(log N) 的量级。
AVL是平衡树的一种，平衡条件非常严格。它要求任何节点的左右子树高度差的绝对值不能超过1。

空二叉树是一个 AVL 树
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |ℎ(𝑙𝑠) −ℎ(𝑟𝑠)| ≤1，h 是其左右子树的高度
树高为 𝑂(log ⁡𝑛)

平衡因子：右子树高度 - 左子树高度

红黑树

首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK
通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）

红黑树满足以下特性：

节点是红色或黑色
根是黑色
叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），即null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
红色节点的子节点都是黑色，红色节点的父节点都是黑色
从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素

并查集支持以下两种操作：

合并（Unite）：合并两个元素所属集合（合并对应的树）。
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。

路经压缩

如果查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

1
2
3

// assignment expression 
// size_t a; size_t b = (a = 10);
size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

kd 树（k-d tree）

数据驱动 (Data-Driven) 的空间划分。k-d树的分割线（或分割面）的位置，是由数据点本身的位置决定的，目标是让分割后的两个子空间包含大致相同数量的点。
每个节点按一个维度（2D：x 或 y，3D：x/y/z）把空间分成两半
节点保存一个点/对象，左子树保存该维度值更小的点，右子树保存更大的点

构建方式

选维度: 从 X 轴开始。
找到中位数: 在所有数据点中，找到 X 坐标的中位数。
划分: 以这个中位数点的 X 坐标为界，画一条垂直于 X 轴的分割线（平面）。
- X 坐标小于该值的点，归入左子树。
- X 坐标大于等于该值的点，归入右子树。
递归与交替维度:（3维的话是 x -> y -> z -> x -> …）
- 对左子树和右子树，重复上述过程，但这次切换到 Y 轴。
- 下一层再切换回 X 轴，如此循环，交替使用不同的维度进行划分。
结束: 直到每个子区域只包含一个点，或达到预设的叶子节点容量。

结果是一个平衡树，构建复杂度 O(N log N)

更新方式

插入

直接沿树下降，到叶子插入新点
不做重平衡，平均 O(log N)，但随着插入会变得不平衡

删除

可把节点标记为“已删除”
或用后继/前驱点替换当前节点并递归删除

动态维护

简单方案：批量更新后重建整个 kd 树
常见做法：周期性重建，或者在插入/删除累计到一定阈值后重建

适用场景

点集较静态或更新较少
适合近邻搜索、点查询

四叉树

空间驱动 (Space-Driven) 的划分。四叉树的分割方式是固定的，它只关心空间本身，而不管空间里有什么数据。
每个节点对应一个轴对齐的矩形/正方形区域，如果区域内点数超过阈值，则分成 4 个子象限
分割线永远是区域的正中线。最终划分出的子空间是大小可能不同、但形状永远是正方形的网格。

构建方式

定义边界: 从一个包含所有数据点的巨大正方形（根节点区域）开始。
划分: 将这个正方形均匀地分割成四个等大的子正方形（象限）：西北、东北、西南、东南。这四个子正方形成为根节点的四个子节点。
递归:
- 对于每个子节点，检查其中包含的数据点数量。
- 如果数量大于某个阈值（比如1），或者区域的尺寸还很大，就再次将其均分成四个更小的正方形。
- 如果数量小于等于阈值，或者区域已经很小，则停止分裂，该节点成为叶子节点。
数据归属: 每个数据点根据其坐标，被存储在完全包含它的、尺寸最小的那个叶子节点中。

更新方式

插入

找到点所属的叶节点并加入
若点数超阈值，分裂该叶节点

删除

从对应叶节点删除点
如果节点和兄弟节点合并后点数低于阈值，可回收子节点，合并成父节点

移动对象

先从旧格子删除，再重新插入新位置
若对象移动量不大，可使用“松散四叉树”（loose quadtree）减少频繁重插入

适用场景

2D 空间、区域查询、碰撞检测、动态场景
对于分布不均匀、局部聚集的点特别有效

BVH (Bounding Volume Hierarchy) / 包围盒层级

对单位按区域构建层级包围盒（AABB），按包围盒层级组织，适合先过滤远物体再精细排序
适合移动对象少、查询多的场景
查询时先过滤掉远离的盒子：如果这个盒子比当前队列（大顶堆）中的最远距离还要远，那么不考虑这个盒子

构建方式

准备叶子对象：每个对象先计算自己的AABB和中心点（centroid）
建根节点：根节点包围所有对象的总 AABB
递归分裂：
- 终止条件为对象数 <= leaf_size（如 4/8）或树深度到上限。
- 否则继续分裂：选最长轴 + 中位数切分（快，质量一般），或者 SAH 选轴和切分位置（慢些，但查询更快）。
生成子节点：左右子集分别求 AABB，继续递归
叶子存索引：叶节点保存对象索引范围（而不是拷贝对象）。
- “保存索引范围” 通常建立在 “构建时把对象重排成连续段”这个前提上
- 如果不重排，那就需要存一个显式索引列表（vector/list），代价是内存和访问局部性通常更差。

乌啦呀哈呀哈乌啦！

数据结构

AVL树

红黑树

并查集

路经压缩

kd 树（k-d tree）

构建方式

最近邻查询

更新方式

四叉树

构建方式

最近邻查询

更新方式

BVH (Bounding Volume Hierarchy) / 包围盒层级

构建方式

最近邻查询