红黑树和AVL树之间的差异 [英] Difference between red-black trees and AVL trees

问题描述

有人能解释一下这两个数据结构之间的主要区别是什么？我一直在试图找到一个源在线，突​​出的分歧/相似之处，但我还没有发现什么太丰富。在什么情况下会之一pferred比其他$ P $？什么实际情况做一个更好比其他使用？

Can someone please explain what the main differences between these two data structures are? I've been trying to find a source online that highlights the differences/similarities, but I haven't found anything too informative. In what cases would one be preferred over the other? What practical situations make one "better" to use than the other?

推荐答案

AVL树保持较为严格的资产负债比红黑树。从根本上最深的叶AVL树的路径最多为〜1.44 LG（N + 2），而在红黑色的树木它在大多数〜2 LG（N + 1）。

AVL trees maintain a more rigid balance than red-black trees. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).

其结果是，查找在AVL树通常更快，不过这是以慢插入和删除的成本由于多个旋转操作。因此，使用AVL树，如果你希望查找的数量更新的数量占主导地位的树。

As a result, lookup in an AVL tree is typically faster, but this comes at the cost of slower insertion and deletion due to more rotation operations. So use an AVL tree if you expect the number of lookups to dominate the number of updates to the tree.

这篇关于红黑树和AVL树之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！