Avl树与红黑树的比较

Question

我明天要考试，我的笔记上有3道题我听不懂。

1- #搜索>> #插入和#deletions=0，这是哪一棵树？(Avl或红黑树)(答案是Avl)

2- #insertions>0和#searches=#deletions=0，那是哪棵树？(Avl或红黑树)(答案是红黑)

3- #insertions=#deletions和#searches=0，那是哪棵树？(Avl或红黑树)(答案是红黑)

你能解释一下吗？谢谢你的帮助

Answer 1

与红/黑树相比，AVL树的高度通常较小，因为AVL不变量给出的不平衡空间较小。然而，与AVL树相比，红色/黑色树具有更快的插入和删除速度(维护红色/黑色不变量的修复成本低于维护AVL不变量的固定成本)。

对于案例(1)，AVL树可能更好，因为查找的成本将更低，如果查找的次数确实比插入的数目大得多，则AVL树将具有相对优势。

对于案例(2)，红色/黑色树可能会更快，因为它支持更快的插入。

对于案例(3)，由于与第(2)部分相同的原因，红色/黑色的树可能会更快。

希望这能有所帮助！