AVL树复杂度和红黑树复杂度
来源：2-11 不能白板编程红黑树就是基础差？别扯了。
何艾莉
2022-10-31 15:42:46
老师好，能不能告诉我一下AVL树的各种操作的复杂度和红黑树的各种操作的复杂度？以及红黑树与AVL树的不同在哪？我想准备一下面试谢谢。
写回答
1回答
-
liuyubobobo
2022-10-31
AVL 树和红黑树的所有操作的复杂度都是 O(logn) 的。
AVL 树维持了绝对的平衡，是严格意义的平衡树（任意左右子树的高度差最大为 1）；
而红黑树不是严格意义的平衡二叉树，只保持了黑平衡（黑节点绝对平衡），整棵树左右子树的高度差最大是两倍的关系。
但是，因为红黑树维持自身的平衡需要的操作更少，所以统计意义上，红黑树比 AVL 树的性能更优。（但是在复杂度分析上，他们所有的操作的复杂度是一致的，都是 O(logn) 的。）
继续加油！：）
0
相似问题