众所周知，插入和删除都需要O(log n)。AVL 树需要 O(log n)，因为它需要 O(log n) 来插入和 O(log n) 来旋转以达到平衡。
RB 树需要 O(log n)，因为它需要 O(log n) 才能插入，在第三版算法简介中，对于案例 1（颜色翻转），RB-INSERT-FIXUP 需要 O(log n)，最多2次旋转。所以看起来 AVL 需要 2O(log n)，但 RB 树需要 2O(log n)+C。
为什么我们认为 RB 树在插入方面比 AVL 更快？仅仅因为旋转比颜色翻转需要更多时间？旋转和颜色翻转都需要 O(1)，为什么旋转比颜色翻转更耗时？谢谢！：）
如果我正确理解您的问题，是的，RB-Trees 和 AVL-Trees 都提供O(logn)及时的查找、插入、删除。
AVL-Trees 比 RB-Trees 更严格地平衡。为了达到这个目的，需要大量的旋转，这很耗时。RB-Trees 稍微不平衡，因为它们的平衡规则较弱，因此它们需要较少的插入和删除操作。因此，AVL-Trees 中的查找比 RB-Trees 更快，但 RB-Trees 中的插入和删除更快。
编辑
请阅读这篇博文。关键是RB树在插入后比AVL树平衡得更快。是的，在 AVL 树中，一个轮换确实需要O(1)时间，最多需要进行两次轮换，但仍然需要找到轮换点，轮换的时间变为O(logn)。而在 RB 树中，插入后的重新平衡以摊销的常数时间运行。因此，O(1)颜色翻转的摊销时间，而不是O(logn).