红黑树

# 1. 平衡树简介

之前我们学习过二叉查找树，发现它的查询效率比单纯的链表和数组的查询效率要高很多，大部分情况下，确实是这样的，但在最坏情况下，二叉查找树可能会退化为链表：

我们会发现，如果我们要查找1这个元素，查找的效率依旧会很低。效率低的原因在于这个树不平衡，全部是向左边分支。如果我们有一种方法，能够不受插入数据的影响，让生成的树都像完全二叉树那样，那么即使在最坏情况下，查找的效率依旧会很好。

# 1.1 平衡树定义

平衡二叉树 (opens new window)（BalancedBinaryTree）具有以下性质：

它是一棵空树或它的左右两个子树的高度差的绝对值 (opens new window)不超过1，并且左右两个子树都是一棵平衡二叉树(AVL)

# 1.2 平衡树分类

AVL树：自平衡二叉查找树 (opens new window)，最坏复杂度都是O(log n)
红黑树 (opens new window)
2-3树

# 1.3 红黑树和AVL树简介

# 平衡二叉树（AVL树）

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

【应用】

搜索操作较多的情况下，二叉查找树实现
由于要保持严格平衡，插入、删除操作较为耗时

# 红黑树

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个==节点着色==的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少。

【应用】

搜索，插入，删除操作较多的情况下

# 小结

红黑树和AVL树类似，都是在进行插入和删除时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能
红黑树和AVL树的区别在于它使用颜色来标识结点的高度，是局部平衡而不是AVL树中的非常严格的平衡
红黑树对于任何不平衡都会在==三次== 旋转之内解决
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高

# 1.4 AVL树 vs 红黑树

**平衡性：**左右子树高度之差的绝对值不超过1

平衡二叉树类型	平衡度	调整频率	适用场景
AVL树	高	高	查询多，增/删少。Windows NT内核
红黑树	低	低	增/删频繁。C++的STL

AVL树是严格的平衡二叉搜索树，平衡条件必须满足所有节点的左右子树高度差不超过1
红黑树是一种弱平衡二叉搜索树（红黑树确保没有一条路径比其它路径长出两倍，平衡因子为<=2），在相同的节点情况下，AVL树的高度低于红黑树

# 2. 2-3查找树

# 2-3查找树的定义

2-3查找树是一种绝对平衡的树，任意叶子节点到根节点路径一定相同

2-结点：含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点

3-结点：含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点

# 查找

要判断一个键是否在树中：

先将它和其根结点中的键比较。如果它和其中任意一个相等，查找命中；
否则就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找
如果这个是空链接，查找未命中

# 插入

# 向2-结点中插入新键

往2-3树中插入元素【关键步骤是节点融合】：

首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。
如果查找后未找到的节点是一个2-结点，那么很容易，我们只需要将新的元素放到这个2-结点里面使其变成一个3-结点即可。

# 向一棵只含有一个3-结点的树中插入新键

假设2-3树只包含一个3-结点，这个结点有两个键，没有空间来插入第三个键了，最自然的方式是我们假设这个结点能存放三个元素，暂时使其变成一个4-结点，同时他包含四条链接。
然后，我们将这个4-结点的中间元素提升，左边的键作为其左子结点，右边的键作为其右子结点。
插入完成，变为平衡2-3查找树，树的高度从0变为1。