众所周知，插入和删除都需要O(log n)。 AVL树需要O(log n)，因为它需要O(log n)来插入和O(log n)来平衡旋转。
RB 树需要 O(log n)，因为它需要 O(log n) 来插入，在算法简介第三版中，RB-INSERT-FIXUP 需要 O(log n) 用于情况 1(颜色翻转)，最多旋转 2 次。 所以看起来AVL需要2O(log n)，但是RB树需要2O(log n)+C。
为什么我们认为RB树在插入上比AVL快？仅仅因为旋转比颜色翻转需要更多时间？旋转和颜色翻转都需要O(1)，为什么旋转比颜色翻转更耗时？ 谢谢!:)
最佳答案
如果我正确理解您的问题，是的，RB-Trees 和 AVL-Trees 都在 O(logn) 时间内提供查找、插入和删除。
AVL 树比 RB 树更严格地平衡。为此，需要进行大量旋转，这非常耗时。 RB 树略微不平衡，因为它们的平衡规则较弱，因此它们需要较少的插入和删除操作。因此，AVL-Trees 中的查找速度比 RB-Trees 快，但插入和删除速度在 RB-Trees 中更快。
编辑
请阅读this blog post .关键是 RB 树在插入后比 AVL 树平衡得更快。是的，在AVL树中一次旋转确实需要O(1)的时间，最多需要进行两次旋转，但是仍然需要找到旋转的点，旋转的时间变为O(登录)。而在 RB 树中，插入后的重新平衡以摊销的常数时间运行。因此，O(1) 颜色翻转的摊销时间，而不是 O(logn)。
关于algorithm - AVL树旋转和红黑树颜色翻转，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19224190/