红黑树的性质
1. 节点是 red 或者 black
2. 根节点是 black
3. 叶子节点（外部节点，空节点）都是 black
4. red 节点的子节点是 black
5. red 节点的父节点是 black
6. 从根节点到叶子节点的所有路径上不能有两个连续的 red 节点
7. 从任一节点到叶子节点的所有路径都包含相同数目的 black 节点
1. 红黑树添加节点
红黑树添加节点，我们一般在叶子节点添加红色，因为添加红色节点能更快的符合上面几条性质，比如，如果添加一个黑色节点，很容易就打破规则7，本来红黑树从任意节点到子节点的路径上都包含相同的 black 节点，但是如果这时候我们添加black 节点，那么这条规则就打破了，所以我们一般添加红色节点
所以如果叶子节点为黑色节点，我们添加红色节点没有问题，但是叶子节点是红色节点，那么久不满足性质6了，就需要做调整
黑
红
红（后添加的）
上面的情况就是 LL
黑
红
红（后添加）
这种情况就是RR
所有就需要染色，就需要将，父节点染成黑色，祖父节点染成红色，然后进行旋转，进行左旋和右旋
如果添加节点出现上溢的情况，那么将这个节点的父节点和叔父节点染成黑色，然后把原来的父节点染成red，然后当做新添加的节点来处理,递归向上，如果到了根节点还是上溢，只需要将根节点染成 black
2. 删除节点
1.如果删除的为 red 节点，那么直接删除
如果删除 black 节点：
2.如果这个black 有两个red 节点，那么不用理会，因为删除这个black 节点之后，会有相应的red节点来顶替
拥有一个 red 节点的black 节点，和叶子black 节点，如下图
3.删除拥有一个 red 节点的 black 节点：
判定条件：用以替代的子节点为 red
删除这个 black 节点之后，将替代的子节点染成黑色即可
- 删除 black 叶子节点，兄弟节点为 black
如果兄弟节点至少有一个 red 节点，那么就管兄弟借一个，此时可能会导致 B 树下溢，
1. 进行旋转操作
2. 旋转之后的中心节点，继承原来 parent 的颜色
3. 旋转之后的左右两个节点都染为黑色
- 删除叶子节点，兄弟节点为 black
如果兄弟节点没有一个 red 节点，那么就将 parent染成黑色，兄弟节点染成红色
如果 parent 为黑色，那么会导致下溢，只需要把parent当做被删除的节点就可以
- 删除 black 叶子节点，兄弟节点为红色
1. 兄弟节点染成黑色，parent 染成红色，然后进行旋转
2. 这时候又回到了5的情况，兄弟节点为 black
网友评论