红黑树的几点疑问

Question

一、老师在课程里好像也没有写删除部分的代码，算法书上写的删除操作有点看不懂，作者也没有写，然而删除操作是比添加更复杂的，是否是因为对于红黑树来说这部分操作意义不大呢？
二、还有就是红黑树结构和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的情况更多，也就是不用旋转只需要改变颜色就可以了。这是否说明右偏树就更快一点呢？这是为什么？

Answer 1

liuyubobobo 2020-06-20 14:26:28

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

统计意义都是一样的。因为是对称的。一组数据不能说明问题。要大规模做很多组，做统计分析，才能说明问题。

继续加油！：）

• 提问者 qq_萌新_4 #1

  对于二个问题，2logn应该只是统计的黑节点吧？红黑节点一起统计其实还是logn。我想知道的是没有这样的应用是只统计黑节点的吧？红黑树对AVL的优势主要还是减少了不必要的旋转操作
  
  由于准备面试，我就先不看删除了。
  
  老师的文章写的很好，这篇幽默感很强，笑死我了

• liuyubobobo 回复 提问者 qq_萌新_4 #2

  不是。2logn 是红黑都统计；这个意思是，一棵树如果绝对平衡，高度应该是 logn 的。但因为红黑树是黑平衡，最差情况那个最高的高度上每个黑节点下面都跟一个红节点，就是 2logn 这个级别了。

• 提问者 qq_萌新_4 回复 liuyubobobo #3

  但是就算是最差的情况，相同数据下，红黑树和AVL的高度应该是一样的，高度都是logn，那为什么跟一个红节点就变成2logn呢，不是都按照二叉搜索树进行搜索么

点开查看后面6条评论