数据结构

---

AVL树

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

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

---

红黑树

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

红黑树满足以下特性：

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

---

并查集

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

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

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

路经压缩

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

// 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]); }

---