费这么大力气搞平衡二叉树，目的是提高查找效率。这里提出一个简单的定性衡量效率的方法——整树节点查找比较次数和。下图是3节点平衡与非平衡二叉树的比较次数和。

　　功夫没白费，三个节点的平衡二叉树就显示出查找效率提高了，何况很多节点的情况呢！但平衡二叉树的插入和删除节点实在太麻烦啊，如果这种树频繁添加和删除节点，则要把电脑烧坏不可。

　　为了不烧坏电脑，在查找效率做些让步——最多的比较次数不超过最少的比较次数的两倍。于是红黑树(RB-Tree)的方案就提出来了。

　　红黑树是一种类似于完全二叉树（注：平衡二叉树的子集，参考资料中是平衡二叉树，忽悠了。）的二叉树结构，除了必须符合二叉查找树的规则外，它还要符合以下规则：

　　(1)节点是红色或者黑色。

　　(2)根节点是黑色。

　　(3)所有节点要么是叶节点，要么满配（注：参考资料中没有。）；每个叶子节点都是黑色的空节点(数值是None)。

　　(4)每个红色节点的两个子节点都是黑色的（红黑树不会出现相邻的红色节点）。

　　(5)从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

　　红黑树结构如下图所示。

　　红黑树能实现“最多的比较次数不超过最少的比较次数的两倍”是基于这个简单的数学事实：红球不能相邻，全部由黑球构成的线路球数最少，由黑红球相隔构成的线路球数最多，最多球数是最少球数的两倍。因此，第(4)和第(5)的规则就显而易见了。但为何还要有第(2)和第(3)的规则呢？

　　第(2)的规定主要是考虑到2红1黑3个非空节点的情况。如果根节点是红色，必然1条线路有2个红节点相连。如下图所示。

　　第(3)的规则比较复杂。首先考虑1红1黑2个非空叶节点的情况。由第(4)和第(5)规则，还要满配，所以在红色节点下加2个黑色空节点。如下图所示。

其次，根据第(4)和(5)的规则，如果是单红叶节点的父母节点就要配上“红空节点”；如果是单黑叶节点父母节点就要配上“黑空节点”。可见，由于叶节点的原因需要配置空节点的3情况中，2种情况是配置“黑空节点”，1种情况配置“红空节点”。能否只用1种空节点呢？当然可以的，很自然想到用“黑空节点”。因为单红叶节点父母节点配上“黑空节点”，就成了1红1黑满配状态，只要在红节点后又增加2个黑空节点，就符合第(4)和(5)的规则。但为何还要在黑非空节点后加2个空黑节点呢？

　　其实，这时迫不得已的措施，红节点满配2个黑节点的情况，如下图：

增加红节点也好，黑节点也好，都要破坏规则，都需要进行调整，这不符合红黑树的设计目的。为了解决这个问题，在黑非空节点下也添加2个黑空节点。这样，起码添加红节点时没破坏规则。如下图所示。

　　红黑树的规则，解析完了。基于红黑树的规则，新加入黑节点必然破坏规则；但在黑非空节点后加入红节点没有破坏规则，红色节点后加红节点才破坏规则。两害相权，取其轻，于是产生了红黑树的附加规则：新加入到红黑树中的节点为红色节点。

　　思考题：红黑树的规则，一条也不能少。但根据满二叉树的特点，可知叶节点的数量是所有祖先的和加1。从而得到，红黑树可能要增加1倍多1个指针和1个节点。也许有可能用另外一套规则代替这一套规则，无需增加空节点指针但又能达到红黑树的目的——最多的比较次数不超过最少的比较次数的两倍。注：这是个未解之谜。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html