红黑树和AVL树之间的区别

Question

有人可以解释一下这两种数据结构之间的主要区别是什么吗？我一直试图在网上找到一个突出差异/相似之处的来源,但我没有找到任何太丰富的信息.在哪种情况下,一个人比另一个人更受欢迎？什么实际情况使一个"更好"使用比另一个？

Answer 1

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

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

Answer 2

对于小数据:

insert:RB tree&avl tree具有恒定的最大旋转次数,但RB树会更快,因为平均RB树使用较少的旋转.

查找:AVL树更快,因为AVL树的深度较小.

删除:RB树具有恒定的最大旋转次数,但AVL树可以将O(log N)次旋转视为最差.并且平均而言,RB树也具有较少的旋转次数,因此RB树更快.

对于大数据:

insert:AVL树更快.因为您需要在插入之前查找特定节点.当您有更多数据时,查找特定节点的时间差异与O(log N)成比例增长.但在最坏的情况下,AVL树和RB树仍然只需要恒定的旋转次数.因此,瓶颈将成为您查找该特定节点的时间.

查找:AVL树更快.(与小数据情况相同)

删除:AVL树平均速度更快,但在最坏的情况下,RB树更快.因为您还需要在删除之前查找非常深的节点以进行交换(类似于插入的原因).平均而言,两棵树都有恒定的旋转次数.但RB树有一个恒定的旋转上限.

Answer 3

引用此:AVL和红黑树之间的差异

RB-Trees和AVL树一样,是自平衡的.它们都提供O(log n)查找和插入性能.不同之处在于RB-Trees保证每次插入操作的O(1)旋转.这实际上是实际成本中的性能成本.简化后,RB-Trees从概念上成为2-3个树,而不会带来动态节点结构的开销.物理RB树实现为二叉树,红/黑标志模拟2-3行为.

根据定义,每个AVL因此是Red-Black的子集.一个人应该能够为任何AVL树着色,而无需重组或旋转,将其转换为红黑树.