数据结构复习
红黑树：
红黑树是具有下列着色性质的二叉查找树：
- 每一个节点或者是红色，或者是黑色
- 根是黑色的
- 如果一个节点是红色的，那么它的子节点必须是黑色的
- 从一个节点到一个null指针的每一条路径必须包含相同数目的黑色节点
着色法则的一个结论是，红黑树的高最多是2log(N+1)，因此，查找操作保证是一种对数的操作。
当将一个新项插入到树中时，通常把新项作为树叶放到树中，如果把该项涂成黑色，那么肯定违反条件4，因为那会建立一条更长的黑节点的路径，因此，这一项必须涂成红色。如果它的父节点是黑的，那么插入完成，如果它的父节点已经是红色的，则得到连续的红色节点，这就违反了条件3。在这种情况下，我们必须调整该树以确保条件3满足（且又不引起条件4被破坏）。用于完成这项任务的基本操作是颜色的改变和树木的旋转。
假设将新插入的新节点标记为X，此时X为红色，如果X为根节点，那么将X标记为黑色
如果X不是根节点，当X的父节点（parent）和父节点的兄弟节点（uncle）都为红色时：
- 将parent和uncle都标记为黑色
- 将grand parent（祖父）标记为红色
- 对变色后的祖父节点重复这个过程
如图所示：
X为红色，X的parent和uncle均为红色，此时将p和u均标记为黑色，将g标记为红色，发现g为祖父节点，将g标记为黑色，退出。
如果X不是根节点，当X的parent节点为为红，x的uncle节点为黑时，分四种情况处理（这时处理步骤主要是旋转）：
- 左左（parent节点是祖父节点的左节点，X节点是parent节点的左节点）：
这时向右旋转g（可以想象为手提起P节点），然后交换p和g的颜色即可。 - 左右：
首先左旋，使得X的父节点p被x取代，同时父节点P成为X的左孩子，然后应用左左情况 - 右右：
和左左相同，镜像 - 右左：
首先右旋，使得X的父节点P被X取代，同时父节点P成为X的右孩子，然后应用右右情况
参考：
https://zhuanlan.zhihu.com/p/79980618?utm_source=cn.wiz.note