25、红黑树（下）

思考：为什么红黑树的叶子节点都是黑色的空节点呢？

主要内容

实现红黑树的基本思想：类似于复原魔方，遇到具体的节点排布就对应去调整。
合格红黑树要求：
1、根节点为黑色
2、叶子节点为黑色的空节点
3、任何相邻(上下)的节点不能同时为红色
4、从任意节点到其可达到的叶子节点所有路径上，包含相同数目的黑色节点

左旋：围绕某个节点的左旋
右旋：围绕某个节点的右旋
图中的 a，b，r 表示子树，可以为空，下图来理解这两个操作

解读：
1、围绕 X 节点的左旋，就是将 X 放到它右子节点(Y)的左节点上（X 是小于它右节点），然后 Y 原本的左节点(b) 作为 X 节点的右节点(b 是大于 X 节点的)
2、围绕 X 节点的右旋，就是将 X 放到它左子节点(Y)的右节点上（X 是大于它左节点），然后 Y 原本的右节点(b) 作为 X 节点的左节点(b 是小于 X 节点的)
核心原理是：旋转过去要保证左节点比它父节点小

插入的平衡调整

插入的节点必须是红色且必须放在叶子节点上

解答思考

内容总结

新的思考