在《构建儿童数据的二叉树》中，本号曾经写过平衡二叉树在存储大量数据的应用。但是，平衡二叉树虽然美观，其插入删除修改需要涉及的旋转过程很耗费时间，例如删除结点时需要对结点到根结点的整个路径进行向上递归的旋转，此时需要消耗log2(n)的时间。因此对于数据量大于1000的情况，平衡二叉树的时间劣势会非常明显。

当统计的数据的数目越来越大且需要大量更替时，平衡二叉树旋转的时间浪费会越来越显著，图一来自新禾融媒体工作室

因此，人们根据平衡二叉树旋转消耗时间长等缺点，把它改进为红黑树。并对红黑树进行以下定义：

1、每个结点只能是红色和黑色的。

2、根结点为黑色。

3、NIL结点为黑色。

4、红色结点的孩子都为黑色。

5、从任一结点到NIL叶子结点的所有简单路径都经过相同数量的黑色结点。

与平衡二叉树相比，红黑树的插入和删除后的调整更加复杂，情况也更加多。并且需要定义NIL结点为黑色的，且双亲、左右孩子都是自己的结点作为辅助，同时，规定根结点的双亲和叶子结点的左右孩子都是NIL结点。

想象一下初夏数之不尽的莲雾果实，红与黑被定义为浅色或深色的果实

对于红黑树的插入，根据定义5，新插入的结点必然是红色的。在寻找到插入的位置之后，需要对插入之后的情况进行以下调整：

当插入的结点的双亲为黑色时，无需调整，直接插入。

当插入的结点的双亲为红色时，由于违反了定义4、5，需要通过下列6种情况以保持其性质。这6种情况可以分为插入结点在左子树和插入结点在右子树的各3种情况。

以下只讨论插入结点在左子树的3种情况，另外3种情况为这3种情况的左右对换。

为讨论方便，以下定义插入结点为N结点，双亲结点为P结点，双亲的双亲（祖亲）为G结点，祖亲在双亲之外的孩子结点（旁亲）为U结点。

情况1：结点的旁亲为红色。此时只需要把双亲和旁亲变黑色，祖亲变红色，并迭代调整插入结点的祖亲结点直到根结点。

情况2：结点的旁亲为黑色，且插入结点为双亲的右孩子。此时需要对双亲进行左旋（关于左旋、右旋详见《构建儿童数据的二叉树》，不再赘述），至此进入情况3。

情况3：结点的旁亲为黑色，且插入结点为双亲的左孩子。此时需要把双亲结点变为黑色，祖亲结点变为红色，并对祖亲结点进行右旋。

对于红黑树的删除，和平衡二叉树的删除基本一样。当删除的是叶子结点时，叶子结点用NIL结点顶替，当删除的是只有一个孩子的结点时，用其孩子顶替，当删除的结点有两个孩子时，用右子树的最左边结点（或左子树的最右边结点）顶替。删除根结点时，用NIL结点顶替根结点自身。

不同在于，删除的过程中需对被删除的结点进行判断并调整。

当被删除的结点为红色时，无需调整，直接删除。

当被删除的结点为黑色时，由于违反了定义5，需要通过下列8种情况以保持其性质。这8种情况可以分为被删除的是左孩子还是右孩子的各4种情况。

和插入一样，以下只讨论被删除的是左孩子的4种情况，另外4种情况为这4种情况的左右对换。

为讨论方便，以下定义被删除结点为D结点，被删除结点的同胞结点为S结点，同胞结点的左孩子（左侄亲）为L结点，同胞结点的右孩子（右侄亲）为R结点。

另外，下列图中结点如果为黑圈套红圈（或红圈套黑圈）的，说明结点可为红色或黑色，其内圈和外圈的颜色变化为结点颜色不同基础下颜色的变化。

情况1：结点的同胞为红色。此时需要把同胞结点变黑色，双亲结点变红色，并对双亲结点左旋。

情况2：结点的同胞为黑色，且两个侄亲结点均为黑色。此时把同胞结点变红色，然后迭代向双亲方向调整。

情况3：结点的同胞为黑色，右侄亲为黑色且左侄亲为红色。此时把同胞变红色，左侄亲变黑色并对同胞结点右旋。至此进入情况4。

情况4：结点的同胞为黑色，右侄亲为红色。此时先把双亲的颜色作为同胞的颜色，之后把双亲变黑色，右侄亲变黑色，之后对双亲结点进行左旋，最后把结点返回到根结点。

当被删除的对应结点不是根结点且结点为黑色时，循环上述操作在删除的最后，需要设置根结点总为黑色。

由于平衡二叉树最大高度为

，小于红黑树的最大高度

，所以在最坏的情况下，平衡二叉树在遍历或搜索的时间会略小于红黑树。但两者的差别不大，当数据足够多时，平衡二叉树和红黑树的树高都会趋向于理想状态，即

。

平衡二叉树的美观性，体现在层次的均匀上，但这种均匀是要付出旋转的代价的

而由于红黑树在删除时最多只需要3次旋转即可保持其性质，但平衡二叉树最多需要log2(n)次，因此在大量插入删除，体现在需要大量更替数据的情况下，红黑树的优势将更加显现出来，并抵消不完美平衡的不足。

红黑树在结构上像梅树、橘子树和榕树，不完全平衡，但插入删除修改的时间更少

在现实当中，红黑树在计算机科学领域的应用很广。例如Java中的TreeSet，TreeMap就是红黑树的应用，并且红黑树log2(n)的时间复杂度使得它在数据量很大时，可以充当链表的作用。

对于现实世界中像一个区域内所有的儿童的数据，一个网页的站内搜索功能等查找功能相对更多的情况，平衡二叉树可有利于提高运行的效率。而像一个景点内部的人的信息存储，大量用户争夺一个直播的贷款等需要大量数据插入删除的的情况，红黑树的效率会更高。

这两种应用类似图书馆的文献资料管理或旅游点的进出流量

但随着数据量的增长，红黑树的优势会渐渐显著，这也是红黑树比平衡二叉树应用更广的原因。

参考资料

https://blog.csdn.net/l_o_s/article/details/105703296

https://blog.csdn.net/v_JULY_v/article/details/6124989

https://blog.csdn.net/v_JULY_v/article/details/6109153

https://blog.csdn.net/v_JULY_v/article/details/6285620