AVL树复杂度和红黑树复杂度

AVL 树和红黑树的所有操作的复杂度都是 O(logn) 的。

AVL 树维持了绝对的平衡，是严格意义的平衡树（任意左右子树的高度差最大为 1）；

而红黑树不是严格意义的平衡二叉树，只保持了黑平衡（黑节点绝对平衡），整棵树左右子树的高度差最大是两倍的关系。

但是，因为红黑树维持自身的平衡需要的操作更少，所以统计意义上，红黑树比 AVL 树的性能更优。（但是在复杂度分析上，他们所有的操作的复杂度是一致的，都是 O(logn) 的。）

继续加油！：）