112. 红黑树

[goldEli]

什么是红黑树

[goldEli]

红黑树是一种数据结构，是平衡的二叉查找树

先来看看什么事二叉树查找：

如上图所示

1. 每个节点都有两个子节点
2. 节点的值大于等于左边的子节点，小于等于右边的子节点。

带来的好处就是查找值很方便，比如要查找10这个节点，由于有大小关系，从根节点开始 9 =》13 =》11 =》 10，只要需要4步就找到了。

但是缺点也很明显，入下图：

在插入节点的时候很容易造成左右不平衡，导致查找效率低，所以红黑树就是来解决这个问题的。

红黑树入下图：

红黑树特点：

1. 根节点为黑色，叶子节点为红色
2. 相邻节点不能同色
3. 任意子节点到叶子节点都经历相同的黑色节点
4. 插入节点时，通过变色和旋转（左旋，右旋）来让树的结构达到平衡

插入 21：

Reference

红黑树的变色与旋转 漫画：什么是红黑树？

[zlx362211854]

红黑树是一种自平衡的二叉查找树，它具有下面的特点：

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

它通过变色与旋转，解决了上面所说的二叉树不平衡的问题，红黑树使用红黑二色进行“着色”，目的是利用颜色值作为二叉树的平衡对称性的检查，只要插入的节点“着色”满足红黑二色的规定，最短路径与最长路径不会相差的太远，红黑树的节点分布就能大体上达至均衡