文章首发于：clawhub.club

BST存在的问题：

数在插入的时候会导致树的倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。
理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
如图：
BST对比.png

所以出现了平衡树，其在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。

定义：

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。
这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
它的统计性能要好于平衡二叉树（AVL树）
红黑树例子.png

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树性质.png

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

参考文档：

https://cloud.tencent.com/developer/article/1058189
https://segmentfault.com/a/1190000016867155
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md