1回答

liuyubobobo

2018-09-26

已采纳

红黑树的添加删除比AVL快，就是因为这一小节所讲的：红黑树可以做到任意的添加操作都在三次旋转内解决，而当数据量很大的时候，对于AVL树来说，添加节点所需要的旋转操作更多。

对于查询，红黑树会略输AVL树的主要原因是：红黑树不是严格意义上的“平衡二叉树”，而是保持绝对的黑平衡而已；而AVL树保持着平衡二叉树的性质。所以，红黑树的高度是2logn级别的，而AVL树的高度是logn级别的。具体可以参考这里的分析：https://coding.imooc.com/learn/questiondetail/79608.html

这使得对于同样一组数据，建立起的红黑树，其树的高度高概率的高于AVL树，查找自然会慢一些。

当然，在这里，我们说的快一些，慢一些，其实都是在同一个复杂度下的比较。红黑树和AVL树的添加删除查询操作，从复杂度理论的角度讲，都是O(logn)级别的：）

加油！：）

0

1

李爽爽爽爽

谢谢老师~

2018-09-26

共1条回复