平衡标准
- AVL树：每个左右子树的高度差不超过1
- 红黑树：没有一条路径会大于其他路径的2倍
最大高度
- AVL树：1.44 * log2(n+2)-1.328（100w个节点，AVL树的最大高度是28）
- 红黑树：2 * log2(n+1) （100w个节点，红黑树最大树高40）
平衡二叉搜索树的选择
- 如果搜索次数远远大于插入和删除，选择AVL树
- 如果搜索、插入、删除次数几乎差不多，选择红黑树
- 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入删除操作时少量的旋转操作，整体来说性能要优于AVL树
- 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
网友评论