14 红黑树与二叉搜索树的缺陷
1. 二叉搜索树查找的效率 O(log N)
2.
3.
4.
5. 重点
6.
补充
补充：BST 的主要缺陷是 有序插入会退化为链表，使查找/插入/删除退化为 O(n)。红黑树通过对每条根到叶的路径着色加以限制，确保最长路径不超过最短路径的 2 倍，从而让 n 个节点的红黑树高度始终为 O(log n)，最坏情况下的查找、插入、删除也是 O(log n)。
红黑树 5 条性质：
- 每个节点要么红色，要么黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 空节点）是黑色。
- 红色节点的子节点必须是黑色（即不能出现连续两个红节点）。
- 任一节点到其所有后代叶子节点的简单路径上，黑色节点数相同（黑高一致）。
工业界广泛使用红黑树而非 AVL，是因为插入/删除时 AVL 旋转更频繁，红黑树旋转次数更少、整体性能更稳定。
来源整理自：我的有道云笔记
