data-structures - 红黑树和AVL树的区别

Question

有人可以解释一下这两种数据结构之间的主要区别是什么吗？我一直试图在网上找到一个突出差异/相似之处的来源，但我没有找到任何信息太多的内容。在什么情况下，其中一种会优于另一种？哪些实际情况使其中一个比另一个“更好”使用？

Answer 1

AVL树比红黑树保持更严格的平衡。 AVL 树中从根到最深叶子的路径最多为 ~1.44 lg(n+2)，而在红黑树中最多为 ~2 lg(n+1)。

因此，AVL 树中的查找通常更快，但这是以由于更多旋转操作而导致插入和删除速度变慢为代价的。因此，如果您希望查找次数主导树的更新次数，请使用 AVL 树。