把普通搜索二叉树转化为红黑树的方法就是把旧树拆了，用节点数据构建新的红黑树。本文采用逐层拆树法。

　　程序代码：

　　运行结果：

　　转化之后，实际数据层较少了一层，数据分布均匀性提高了。

　　红黑树（RB-Tree）与二叉查找树（BST）和二叉平衡树（AVL）比较

　　红黑树不要求像平衡树那样的严格平衡条件，因此插入和删除性能比平衡树高一些，当然要比查找树低（毕竟查找树无平衡条件）；搜索性能比平衡树低一些，当然比查找树高。

　　红黑树能够以O(1og2N)的时间复杂度进行搜索、插入和删除操作。此外，得益于它的独特设计，任何不平衡都会在三次旋转之内解决。当然，还有其它数据结构能够二次旋转之内解决，但实现起来比红黑树复杂，因此红黑树还是个“性价比”较好的解决方案。

　　相比于BST，因为红黑树可以确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证2O(1ogN)。这是要好于BST的，因为BST最坏情况下可以让查找的时间复杂度达到O(N)。

　　红黑树的算法时间复杂度和AVL树相同，然而统计性能比AVL树更高，致使它的后期维护（插入和删除）比AVL树少，但它们的查找效率没有太大的差别，都是O(logN)。实际应用中，红黑树是高于AVL树。

　　实际上插人AVL树和红黑树的速度取决于所插入的数据。如果待运算的数据分布较好，则比较宜于采用AVL树（例如随机产生系列数），但是如果需要处理的数据比较杂乱，则用红黑树是比较快。

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

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

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

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

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

参考资料：

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