红黑树与AVL树相比，为什么它的插入和删除速度更快？

Question

红黑树与AVL树相比，为什么它的插入和删除速度更快？

algorithmtreeavl-treered-black-tree

5

我希望更好地理解它们之间的区别，但我还没有找到能够把它们分解到我的水平的来源。

我知道这两种树都需要最多2次旋转才能插入。那么为什么红黑树中插入速度更快呢？

而在avl树中，插入需要O(log n)次旋转，而在红黑树中只需要O(1)次旋转？

- user2626445

2

我不知道是谁蠢到给这个问题点了踩！ - Kaidul

2个回答

2

插入和删除在红黑树中并不更快。这是一个常见的假设，这个假设基于红黑树平均每次插入时执行的旋转操作比AVL少（.6 vs .7）。您可以使用Java自行比较TreeMap（红黑树）和TreeMapAVL实现，您可以得到确切的数字，而不是常见但不正确的假设。 https://github.com/dmcmanam/bbst-showdown

- David McManamon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christian · Accepted Answer

嗯，我不确定你的水平如何，但简单来说，红黑树比AVL树更不平衡。对于红黑树，从根到最远叶子节点的路径长度最多是从根到最近叶子节点路径长度的两倍，而对于AVL树，则相邻子树之间最多只有一层差别。这使得AVL树中插入和删除略微更加昂贵，但查找速度更快。然而，这两种数据结构的渐进和最坏情况行为是相同的（在这两种情况下插入的运行时间（而不是旋转次数）都是O(log n)，而你提到的O(1)是所谓的摊销运行时间）。

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