引出

上一节讲的是二叉搜索树，那红黑树是为什么出现的呢？它解决了二叉搜索树的什么问题？

二叉搜索树，在极端情况下，会退化成链表。平衡二叉搜索树，能解决二叉搜索树退化的问题，红黑树就是一个特殊的平衡二叉搜索树。

平衡二叉搜索树

平衡二叉树的严格定义是这样的

二叉树中任意一个节点的左右子树的高度相差不能大于1

完全二叉树、满二叉树都是平衡二叉树，但非完全二叉树也有可能是平衡二叉树

平衡二叉树.png

最经典的平衡二叉树，AVL树，这也是最先被发明的高度平衡的二叉搜索树。

但很多平衡二叉搜索树其实并没有严格符合上面的定义（任意一个节点的左右子树的高度相差不能大于1），比如红黑树。所以说红黑树，并不是严格意义的平衡二叉搜索树。

既然平衡二叉搜索树，是为了解决二叉搜索树退化成链表的问题而存在的。"平衡"的意思，其实就是为了让整棵树左右看起来比较"对称"，或者说比较"平衡"，不要出现左右子树一边很高一边很低的情况。

所以，如果我们设计一个新的平衡二叉搜索树，只要树高不比logn大很多，尽管他不是一个严格的平衡二叉搜索树，但我们仍可以说，这是一个合格的平衡二叉搜索树。这就是红黑树。

红黑树

顾名思义，红黑树的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

• 根节点是黑色的
• 每个叶子节点都是黑色的空节点(null)，也就是说，叶子节点不存储数据
• 任何相邻（父子关系）的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

红黑树.png

为什么要分红色和黑色

一句话：为了构建"棋谱"。
平衡的关键是，当遇到左右一边高一边低的情况，通过旋转（左旋、右旋），来把树左右转平衡。

大家都玩过魔方吧。其实魔方的复原解法是有固定算法的：遇到什么样的节点排布，我们就应对怎么去调整。只要按照这些固定的调整规则来操作，就能复原魔方。红黑树同理，只要按照固定的规则去操作，就能将一个非平衡的红黑树调整成平衡的。

来，下面我聚几个"棋谱"的例子。
红黑树规定，插入的节点必须是红色的，且，新插入的节点都是放在叶子节点上的。

case 1：如果关注节点是A，它的叔叔节点D是红色

• 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
• 将关注节点 a 的祖父节点 c 的颜色设置成红色；
• 关注节点变成 a 的祖父节点 c；
• 跳到 CASE 2 或者 CASE 3。

case 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

• 关注节点变成节点 a 的父节点 b；
• 围绕新的关注节点b 左旋；
• 跳到 CASE 3。

等等等等。不列举了，贴一个极客时间，王争老师的讲解
https://time.geekbang.org/column/article/68976

为什么大家都用红黑树

标准的平衡二叉搜索树已经有实现了，AVL树。为什么大家都喜欢使用非标准的平衡二叉搜索树，红黑树。

AVL树是一个高度平衡的二叉树，所以查询效率非常高，但是，有利就有弊，AVL树为了维持这种高度平衡，就要付出更多的代价。每次插入、删除都要做调整，实现非常复杂。所以，对于有频繁插入、删除操作的数据集合，使用AVL树的代价就有点高了。

红黑树，插入、删除的复杂度相对较低。

但是实现还是非常复杂，不建议自己实现。如果要自己手写代码来满足业务需求，建议手写跳表来替代它。