红黑树的几点疑问
来源：13-4 红黑树的基本性质和复杂度分析
qq_萌新_4
2020-06-20
一、老师在课程里好像也没有写删除部分的代码，算法书上写的删除操作有点看不懂，作者也没有写，然而删除操作是比添加更复杂的，是否是因为对于红黑树来说这部分操作意义不大呢？
二、还有就是红黑树结构和AVL是差不多的，左右子树高度都不会大于1，也就是说同样的数据，最大深度应该是一致的。
对于所有节点的查询操作，复杂度应该都是logN级别的。老师说的2logN是否只是针对黑节点来说的呢？因为我的测试中，单纯的查询操作AVL和红黑树相比，两者基本是差不多的；如果只针对黑节点，不对红节点进行操作，那么它的具体应用又是什么呢？
三、老师说的红黑树添加操作比AVL快（实际测试结果确实如此）
BST: 8.5948097 s.
AVLTree: 0.0319461 s.
RBTree: 0.0256456 s.
，快的地方应该是在递归的时候左旋和右旋的操作减少了吧？
四、按理说左偏和右偏只是相对的，add速度应该都是差不多，但是右偏的红黑树add操作好像更快一点，试了一组数据（满二叉）int[] arr = {4, 5, 3, 2, 1, 6, 8};，右偏树的flipColor的情况更多，也就是不用旋转只需要改变颜色就可以了。这是否说明右偏树就更快一点呢？这是为什么？
1回答
-
1
从计算机专业的学习或者更有针对性的说，准备算法面试的角度，意义不大。可以参考我的公众号的文章：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484057&idx=1&sn=c1df69aea5b6fc773e1dbb8cc25523af&chksm=fd8caddfcafb24c96d43df6b37f02b6e1fd20993a4dd5bda58dbad7088554641cd88d8a8eef0&token=1265877366&lang=zh_CN#rd
如果一定要研究删除操作，可以参考这里：http://coding.imooc.com/learn/questiondetail/136826.html
2
红黑树左右子树高度差可以大于 1。红黑树只是黑平衡。
我不知道你说的实际应用是指什么意思。红黑树统计性能更高，这就好比都是 nlogn 的算法，平均意义上，快排比归并和堆排序性能要好。
3
对。
4
统计意义都是一样的。因为是对称的。一组数据不能说明问题。要大规模做很多组，做统计分析，才能说明问题。
继续加油！：）
092020-06-20
相似问题