1回答

liuyubobobo

2019-06-30

已采纳

只要是动红黑树的结构的操作（添加，删除，修改），都是红黑树更快。

直观的理解，原因是：AVL树是一种平衡树，但红黑树不完全是。AVL树是平衡的，即任何节点左右节点的高度差不超过1，但红黑树达不到这个条件。红黑树只保证了高度是logn级别，但其实最大高度是2logn。比如下面的树是一棵红黑树，但在根节点不满足左右节点的高度差不超过1。（R是红节点，B是黑节点）

    B
   /
  R
 /
B

正因为如此，由于AVL树要保持这个平衡性，通常需要更多的维护工作，在修改一个元素的值的时候，需要更多的旋转操作。而达成红黑树的条件，实际上更简单：）

实际上，对于红黑树，有一个极其“优秀”的性质，我写在了这一章最后的补充文字中，可以参考：https://coding.imooc.com/lesson/207.html#mid=15413

继续加油！：）

1

0