《数据结构与算法》总结（一）红黑树总结

目录

• 红黑树的平衡
• 平均时间复杂度
• AVL树 VS 红黑树
• BST vs AVL Tree vs Red Black Tree

一 红黑树的平衡

1. 最初遗留的困惑：为何那5条性质，就可以保证红黑树是平衡的？
   1.1 那5条性质，可以保证红黑树等价于4阶B树
2. 相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍
3. 是一种弱平衡、黑高度平衡
4. 红黑树的最大高度是 2 ∗ log2(n + 1) ，依然是 O(logn)级别

image

二 平均时间复杂度

• 搜索：O(logn)
• 添加：O(logn)，O(1)次的旋转操作
• 删除：O(logn)，O(1) 次的旋转操作

三 AVL树 VS 红黑树

• AVL树

1. 平衡标准比较严格：每个左右子树的高度差不超过1
2. 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
3. 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn)次旋转调整

• 红黑树

1. 平衡标准比较宽松：没有一条路径会大于其他路径的2倍
2. 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40）
3. 搜索、添加、删除都是 O(logn)复杂度，其中添加、删除都仅需 O(1)次旋转调整

• 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树

• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

• 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

四 BST vs AVL Tree vs Red Black Tree

10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96

• BST

image

• AVL Tree

image

• Red Black Tree

image

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/d3012c9acdf0
来源：简书