4.红黑树
红黑树
- 红黑树是一种自平衡的
二叉查找树，属于AVL平衡树的一种特殊形式
特征：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色，则其两个子节点必须是黑色。
- 从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。
红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度
解决了AVL树的什么问题：
- AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
- 在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
- 红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL。红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
- 红黑树的红黑规则，保证最坏的情况下，也能在O(log 2N)时间内完成查找操作