《恋上数据结构与算法一》笔记（十二）红黑树总结

目录

• 红黑树的平衡
• 平均时间复杂度
• 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.png

二 平均时间复杂度

• 搜索：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

BST.png

• AVL Tree

AVL Tree.png

• Red Black Tree

Red Black Tree.png

---

《恋上数据结构与算法一》笔记

---