红黑树的学习（变色以及旋转）
二叉树
这样的结构有什么好处呢，下面来试着查询一下226
这样可以提升查找效率，时间为O（Log n），但是有可能左右不平衡，造成瘸子对象，所以引入平衡二叉树
红黑树
红黑树是一种平衡二叉树，除了有二叉树的特点外，还有以下特点
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子的节点都是黑色的空节点（NULL）
- 每个红色节点的两个子节点都是黑色的。
- 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。
根据第五条特性，可以推断黑色节点的兄弟节点也是黑色节点，n即为叶子结点
插入时默认为红色（因为默认为黑色会更复杂，不信的可以试试），现在假如插入12的节点，图示
可知依然满足5个特性，现在假如插入21的节点
可知违反了第四特性，这个时候为了保持平衡，红黑树可以自我调整，通过左旋、右旋、变色来保持自平衡
左旋
右旋
静态图如下
下面我们再回到上面的问题
记住以下规则
调整恢复过程中千万不能破坏其他性质，否则只会带来更多难以解决的问题，指针指向的是需要调整的节点，只要我们能把指针指向的节点的父节点调整为黑色，并且没有破坏性质那么问题就解决了。那么总结一下，插入后的所有情况值可能有如下五种
1.插入节点z为根节点——这种情况好办，直接染黑完事，我们不讨论
2.父节点为黑色节点——这种情况最好办，根本没有破坏红黑树的五大性质，不需要做任何调整，我们不讨论
3.父节点为红色节点，叔节点也为红色（变色）
4.父节点为红色节点，叔节点为黑色节点，当前节点为右孩子
5.父节点为红色节点，叔节点为黑色节点，当前节点为左孩子
由于22和21两个节点都是红色，违反了特性4，所以首先把22变成黑色
22变黑之后，则通过21节点的黑色数加一，所以把25变红，根据特性四，再把27变黑现在整个情况如图
此时指针在25，父节点和叔节点都是红色，符合第二种情况，将17和8染黑，完成转换，如图
总结
总的来说就是
父节点和叔节点都为红，将两者都变为黑，并把祖父变红（根节点变黑）
父节点为红，叔节点为黑，分为以下四种
以父为旋转点右旋
先以我为旋转点左旋，再以父为旋转点右旋
以我为旋转点右旋，再以父为旋转点左旋
以父为旋转点左旋