红黑树中插入和删除如何比 AVL 树更快？

Question

我想更好地理解差异，但还没有找到可以将其分解到我的水平的来源。

我知道两棵树每次插入最多需要 2 次旋转。那么如何在红黑树中更快地插入呢？

以及插入如何在 avl 树中需要 O(log n) 次旋转而在红黑中需要 O(1) 次？

Answer 1

好吧，我不知道你的水平到底是多少，但简单地说，红黑树不如 AVL 树平衡。对于红黑树，从根到最远叶子的路径不超过从根到最近叶子的路径的两倍，而对于AVL树，两个相邻子树之间的级别差异永远不会超过一级。这使得 AVL 树中的插入和删除成本稍高，但查找速度更快。两种数据结构的渐近和最坏情况行为是相同的（两种情况下插入的运行时间（不是旋转次数）都是 O(log n) ，您提到的 O(1) 是所谓的摊销运行时间）。

请参阅本段，了解两种数据结构的简短比较。