25、红黑树（上）

思考：为什么工程中都用红黑树这种二叉树？

主要内容

平衡二叉查找树：任意节点的左右子树高度相差不能大于 1

平衡二叉查找树最开始的初衷是为了避免二叉查找树在频繁插入、删除后，退化成链表，导致时间复杂度增加。
所以平衡二叉查找树的重点是“平衡”，让左右子树相差不要那么大。所以“数字 1”并不是固定的

红黑树

平衡二叉查找树的实际运用，是个“明星树”。
红黑树：Red-Black Tree，简称 R-B Tree。
定义：该树中的节点，一类被标记为黑色，一类被标记为红色
额外要求：
1、根节点是黑色
2、叶子节点是黑色的空节点，不能存储数据
3、任何相邻(父子)节点不能同时为红色
4、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

所以红黑树是“近似平衡”，为了不让左右子树偏差太大，性能上退化不严重。

解答思考

思考：为什么工程中都用红黑树这种二叉树？

解答：它只是“近似平衡”，而非严格平衡，所以维护平衡成本低，并且性能还稳定

内容总结

红黑树是为了避免普通二叉查找树的操作中带来的时间复杂度退化问题，所以诞生了它。
它的高度近似 log2n，时间复杂度为 O(logn)，并且性能比较稳定，所以工程中喜欢用它。

新的思考

动态数据结构支持动态的数据插入、删除、查找操作，除了红黑树，我们前面还学习过哪些呢？能对比一下各自的优势、劣势，以及应用场景吗？