12_AVL树 vs 红黑树

平衡标准

• AVL树：每个左右子树的高度差不超过1
• 红黑树：没有一条路径会大于其他路径的2倍

最大高度

• AVL树：1.44 * log2(n+2)-1.328（100w个节点，AVL树的最大高度是28）
• 红黑树：2 * log2(n+1) （100w个节点，红黑树最大树高40）

平衡二叉搜索树的选择

• 如果搜索次数远远大于插入和删除，选择AVL树
• 如果搜索、插入、删除次数几乎差不多，选择红黑树
• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入删除操作时少量的旋转操作，整体来说性能要优于AVL树
• 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树