出现背景
平衡二叉树解决了搜索二叉树可能过长导致查找次数过多的问题，但是随着不断的插入和删除，平衡二叉树算法需要不断的旋转以达到最佳结构，这个旋转操作浪费了不少时间，平衡二叉树的条件过于严格导致在调整过程中浪费了不少操作时间，入不敷出。红黑树旨在根据一种较为宽松的平衡原则，达到查找树和调整树的操作之和总体最小。
正由于红黑树的这种特点，使得它能够在最坏情况下，也能在O(logn)的时间复杂度，并且从根到叶子的最长路径不会超过最短路径的2倍
算法
染色和树构建规则：
@节点是红色或黑色
@根节点是黑色的
@每个叶子结点都是黑色的空节点
@任何相邻（线连起来的，横着的不算）的节点不能同时为红色，红色节点被黑色隔开
@每个节点，从该节点到其可达的叶子节点的所有路径，都包含相同数目的黑色节点
这个规则有两个作用：
1、构建了一个较为宽松的规则，主要是根据每个路径黑色节点数量相同这一性质约束，它一定程度上约束平衡因子，约束了没有完全约束，要比平衡二叉树宽松一点
2、染色规则会涉及变换操作和判别操作，算是一种操作的简化吧
调整方法：
1、变色
2、左旋转
3、右旋转
插入规则：
插入的节点是红色的，因为如果是黑色的那么一个路径上的黑色节点数量不同，影响和调整花销较大，红色的话调整较小。
插入的横向位置按照二叉搜索树的位置层层比较下来
假设插入节点N，N的父节点为P，祖父节点为G，叔叔节点为U
if（插入节点==根节点）：
将N的节点由红色染成黑色
if（N的父节点P是黑色）：
性质4（每个红色节点必须有两个黑色子节点）和性质5（路径黑色节点数量相同）没有收到影响，不需要调整
if（插入节点的父节点是红色，叔叔节点U也是红色）：
先将P和U的颜色染成黑色，再将G的颜色染成红色，此时G的路径上黑色节点数量不变。但需要注意的是G被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归线上调整。
这时候AC是连续的红色节点，所以对C变为黑色
变形完毕
if（N的父节点为红色，叔叔节点为黑色或没有，节点N是P的右孩子，且节点P是G的左孩子）：
先对节点P进行左旋，调整N与P的位置。接下来按照下一种进行处理，以恢复红色不相邻性质。
if（N的父节点为红色，叔叔节点为黑色。N是P的左孩子，且节点P是G的左孩子）：
此时对G进行右旋，调整P和G的位置，并互换颜色。经过这样的调整后，红色不相邻性质被恢复，同时未破坏路径性质。
删除规则：
if（待删除的节点没有子节点）：
直接删除即可
if（待删除的节点有一个孩子）：
让这个孩子上位即可
if（待删除的节点有两个孩子）：
选择与待删除节点最接近的节点来取代它
比如上图是节点3和节点6是合适的选择，习惯上我们选择仅大于的那个，也就是节点6
标签：黑色,路径,效率,插入,搜索,二叉树,红色,红黑树,节点 From： https://www.cnblogs.com/EeiKo/p/16586028.html