AVL树的旋转和红黑树的颜色翻转

众所周知，插入和删除都需要O（log n）。 AVL树需要O（log n），因为它需要O（log n）插入和O（log n）旋转才能达到平衡。因为它需要O（log n）来插入，所以RB-INSERT-FIXUP需要O（log n）用于情况1（彩色翻转），因为它需要O（log n）来插入，因此它需要O（log n），最多旋转2次。因此，似乎AVL需要2O（log n），但RB树需要2O（log n）+ C.AVL树的旋转和红黑树的颜色翻转

为什么我们认为RB树在插入时比AVL更快？仅仅因为旋转需要比颜色翻转更多的时间？旋转和颜色翻转都需要O（1），为什么旋转比颜色翻转更耗时？谢谢！:)

来源

2013-10-07 Aleeee

如果我正确理解你的问题，是的，这是真的，RB树和AVL树都提供查找，插入，删除O(logn)时间。

AVL树比RB树更加严格平衡。为了达到这个目的，需要大量的旋转，这是耗时的。 RB-Trees稍微不平衡，因为它们具有较弱的平衡规则，因此它们需要较少的插入和删除操作。因此，AVL-Tree中的查找比RB-Trees快，但在RB-Trees中插入和删除速度更快。

编辑

请阅读this blog post。重点是插入后RB树的平衡速度比AVL树快。是的，在AVL树中旋转确实需要O(1)时间，最多需要旋转两圈，但仍需要找到旋转点，旋转时间变为O(logn)。而在RB树中，插入后重新平衡以摊销后的恒定时间运行。所以，O(1)彩色翻转的分期时间，而不是O(logn)。

来源

2013-10-07 16:55:42 Max

这个问题已经更新，谢谢你！ – Aleeee

@Aleeee请检查最新的答案。 – Max

插入需要O（log n）。在RB-INSERT-FIXUP中，while循环仅在情况1发生时重复，然后指针z在树上向上移动两级。因此while循环可以执行的总次数是O（lg n）。这来自<算法第三版介绍>。所以整个RB树插入需要2O（log n）+ C。 AVL也需要2O（log n）。 – Aleeee

AVL树的旋转和红黑树的颜色翻转

回答

相关问题