根据红黑树的规则，插入的都是红节点，因此插入前后线路中的黑节点数是不变的，那插入就可以分开两种情况：

　　(1)在黑色节点下插入，也符合第(4)个规则，因此树还是处于平衡状态，无需调整，如下图所示。

　　(2)如果在红色节点下插入，就违反了第(4)个规则，因此需要调整。因为红色节点的父节点一定是黑节点，所以只有两种情况。

　　第一种、叔节点也是红节点，那么把父节点和叔节点都变为黑色，这样以爷节点为根的子树就平衡了。但这个爷子数黑节点多了1个，因此需要把爷节点变为红色。问题就回到了原来的情况。如下图所示。

　　第二种、叔节点是黑色节点，父节点由红节点转为黑节点后，以爷节点为根的左右子数的黑色节点数量失衡了，而且无法通过变色修正，只有采用旋转。由于红黑树只能插入红节点，因此叔节点必为黑空节点。这样就可以分开两种情况来描述。
　　1、叔节点是右节点，在父节点由红变黑后，以爷节点为根的左子树就比右子数的黑节点多1（相当于平衡因子等于1），明显需要以爷节点为旋转根进行右旋。右旋后变黑后的父节点升到爷节点的位置，相当与线路上的黑色节点减少1，爷节点下降到叔节点的位置，同时带上2两个空黑节点。这样叔子树线路就多了1个黑节点，把叔节点（旋转前的爷节点）变为红色即可。如下图所示。

　　2、叔节点是左节点与叔节点是右节点是对称的操作，右旋变左旋，左变右，右变左就行。

　　３、预旋：当爷节点、父节点和当前节点不在一条直线上（当前节点与父节点的关系与父节点与爷节点的关系不一致时需要预旋。左旋要预右旋；右旋要预左旋。如下图所示。

　　程序代码：

　　运行结果：

　　练习１：改变数据列表，测试上例。

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

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

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

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

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社