# 平衡二叉树
二叉搜索树在理想情况下，各个操作的时间复杂度都是 O(logn) ，但是在动态更新的过程中，二叉树可能会失去平衡，导致各个操作的效率下降，甚至退化成链表。要解决这个问题，则需要设计一种平衡二叉搜索树，具有在动态更新的过程中自我调整维持平衡状态的能力
平衡二叉树（AVL）：任意节点的左右子树高度相差不能大于 1
主要通过左旋和右旋来维持平衡，具体 (opens new window)
# 红黑树
红黑树没有严格符合上述定义，因此其实只是一种「近似平衡」二叉树，只保证：从根节点到叶子的最长路径，不多于最短路径的两倍
最大深度为 2*log(n+1)
对比 AVL 树
- AVL 树是严格符合定义的平衡二叉树，因此查找效率极高，但是为了维持这种高度的平衡，每次插入、删除操作 都需要做出调整，因此对于需要频繁插入删除的情况，代价十分高昂
- 红黑树只是做到了「近似平衡」，即极端情况下，性能不会退化太严重，因此维护平衡的成本低了很多，插入、删除、查找的各种操作性能比较稳定
红黑树的通常定义
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点
- 每个红色节点的两个子节点都是黑色
- 从任意节点到其每个叶子节点的所有路径都包含数目相同的黑色节点
红黑树的另一种定义
- 含有红黑链接的并满足下面条件的二叉搜索树
- 红链接均为左链接
- 没有任何一个节点同时和两个红链接相连
- 该树是完美黑色平衡，即任意 NULL 节点到根节点路径上的黑色节点数量相同
# 原理
想要理解红黑树的实现原理，可以先理解 2-3 树的原理，从 2-3 树的角度去理解红黑树的操作会更加容易
红节点其实指的是红链接，指向该节点的链接若为红色，则该节点为红节点
红色节点其实就是对应于 2-3 树中的 3-节点，若把红节点与其黑的父节点放平，就变为了一棵 2-3 树
为了简化红黑树，规定不允许存在红色右节点，即红链接只能向左
# 2-3 树的节点插入
- 对于空树，插入一个 2 节点：直接插入
- 插入节点到一个 2 节点的叶子节点：升级为 3 节点
- 插入节点到一个 3 节点：
a. 只有一个 3 节点：创建一个临时 4 节点，再分解为一个 2-3 树（3 个 2 节点）
b. 父节点为 2 节点的 3 节点：和上面一样，不过分解为 2-3 树后与父节点合并，父节点变 3 节点
c. 父节点为 3 节点的 3 节点：对比 b，此时向上合并后，父节点变临时 4 节点，继续向上合并
d. 父节点到根节点全部是 3 节点：不断向上合并，最后树的深度增加一层