常见数据结构：红黑树、B+树、hash学习

红黑树

1.什么是红黑树（性质）

红黑树要满足以下条件：
1.树中的节点都是红色或者黑色
2.红色节点不能相邻
3.所有的叶子节点都是黑节点
4.从任意节点到叶子节点的黑节点数量相等
5.红色节点的两个叶子节点是黑色节点

2.红黑树的插入和删除

1.红黑树的旋转

红黑树的旋转分为两种：左旋和右旋（不是红黑树特有，是树结构维持平衡的一种方法）

2.红黑树的插入

插入的节点是红色还是黑色？
答：红色，为什么是红色，就要结合红黑树的性质来看

1.树中的节点都是红色或者黑色
2.根节点是黑色
3.所有的叶子节点都是黑节点
4.从任意节点到叶子节点的黑节点数量相等
5.红色节点的两个叶子节点是黑色节点

如果插入节点红色节点，则有可能违背性质5,但是，如果插入节点为黑色节点，则一定会违背性质4。所以，在”可能违背“和“一定违背”之间，我们尽量选择“可能违背“，这样也可以简化操作和减少错误
（个人是这样理解的，也有可能说的不对，做个参考就行，记住插入的是红色节点就行。）

首先说一下不违背性质5的情况（此时，插入节点后不需要调整）：
1.插入的节点为根节点
2.插入的节点的父节点为黑色节点
由于每次插入的节点都是叶子节点，而红黑树的叶子节点都是隐藏的黑节点，所以，不需要考虑插入节点的子结点为红色节点的情况。

所以，违背性质5时，只可能是插入节点的父节点为红节点
那么在违背了性质5后，我们应该怎么调整这颗树，让他变成一个正确的红黑树呢？

这时，我们会自然而然的想到，能不能通过旋转来调整呢？
答案是不能的，为什么呢？
如下图所示
第一种情况，当插入节点的叔叔节点（父节点的兄弟节点）为黑色的情况（这种情况也包括没有叔叔节点的情况，因为红黑树默认叶子节点隐藏且为黑色节点），不管左旋还是右旋，都会违背性质4（任意节点到叶子节点的黑节点数量相等）。

第二种情况，当当插入节点的叔叔节点（父节点的兄弟节点）为红色的情况，不管怎么转都会有两个红色节点相邻

由此可见，想要只靠旋转来解决问题是一定不行的那应该怎么办呢？

既然光靠外部改变无法达到我们的目的，那不如就从内部找原因！！改变节点颜色！！！
这可行吗？？？ 我们试一下就知道了

第二种情况好像解决了（在局部解决了，至于整体，可能还需再调整）
整体怎么调整呢？？——————>将这颗调整完的子树看作一个插入节点就好了。
（注意，这只是一颗子树，所以他的根节点不需要是黑色的，如果图示为一颗完整的红黑树，那么直接保留第一次染色完的状态即可）
但是对于第一种情况好像不太适用，染色后好像还是会违背性质4

离胜利只有一步之遥了，只要把第一种情况解决了，就彻底解决了红黑树的插入问题了。
既然单独的旋转或者染色没法解决，那么，就一起上！！

怎么转？怎么染？取决于第一种情况中有几种状态

可以分为四个状态，为了更清晰的理解，我们去除掉一些无关紧要的黑色节点，则简化结果如图

首先我们关注状态二和状态三，似乎这两种状态挺好调整的，
首先满足性质5,将c染成黑色，变成如下两颗树

此时，性质5满足了，但是性质4又不满足了，那么应该先旋转好呢？还是继续染色呢
如果先染色：将a染成红色，万一a的父节点又是一个红色节点，那该怎么办呢？好像又回到了这两种状态，层层递归，无限循环，

所以还是旋转吧，至少旋转不会又回到这种状态。

等等，好像只要把a染成红色就成了！

为什么呢？
让我们来对比一下刚开始的状态和a染完色的状态

黑色节点的数量没变且都为根节点！！完全满足性质4,且 完美满足性质5！！成了

只剩下了两种状态

使用刚才的方法可不可行呢？
1.染色————>没问题
2.旋转————>好像出问题了

怎么转啊，我已经晕了，为了保证有序存储，好像状态一要先以c为根节点右旋，在以a为根节点左旋，状态四反之。
等等，以c为根节点旋转

好眼熟啊，把c染回去看看

这不就是状态二和状态三吗

节点名称変了，形式不变，换汤不换药啊，直接走之前的流程就行了！
到这里恍然大悟，原来状态一和状态四应该先旋转啊

到这里，所有的情况就都成功插入了！

总结一下，直接上图

太晚了今天先到这，下次再写。