一、红黑树性质
- 节点是黑色或者是红色
- 根节点是黑色
- 叶子节点都是黑色（叶子节点指的是外部节点或者称之为空节点）
- 红色节点的子节点都是黑色节点（红节点的父节点肯定是黑节点。不会出现连续两个红节点）
- 从任意节点到叶子节点的所有路径都包含相同数量的黑色节点
二、红黑树的添加
- 红黑树的添加的都是叶子节点。添加完维护红黑树的五条性质（也就保证了此树的平衡性），下面先把添加之后维护平衡的代码贴出来。
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根节点 或者 上溢到达了根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterAdd(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
-
添加的如果是根节点 或者上溢到了根节点只需将根节点染黑即可（添加的根节点染黑不用解释了，上溢到根节点如下图）
1、上溢到根节点 添加节点的父节点为黑色时 则return。（此时不影响红黑树的性质）
父节点为红色，叔父节点为红色时，则出现上溢，父节点叔父节点染黑，祖父节点染红，递归调用本方法把祖父节点传进去。（可参考 1 图 ，如果为上溢到根节点，则继续判断父节点与叔父节点颜色，严么上溢要么旋转保持平衡)
-
父节点为红色，叔父节点为黑色。如图所示，父节点在祖父节点的左边，添加节点在父节点的右边。自己染黑，祖父节点染红。
父节点左旋，祖父节点右旋。即可维持平衡。
(1、父节点在祖父节点的左边，添加节点在父节点的左边。
2、父节点在祖父节点的右边，添加节点在父节点的左边。
3、父节点在祖父节点的右边，添加节点在父节点的右边。
等情况也是通过染色旋转解决)
2、旋转操作.png
三、红黑树的删除
- 红黑树真正删除的都是度为1的节点或者是叶子节点（先贴代码，在讲解）
protected void afterRemove(Node<E> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
- 如果删除的节点是叶子节点并且为红色 或者 用以替代删除节点为红色时 染黑该节点 return;(1、删除的节点是叶子节点并且为红色此时父节点指点该节点的已经被清空 在染红此节点也没问题。2、用以替代删除节点为红色时，证明删除的节点度为1 并且替代它的是他的子节点，子节点并且是叶子节点，删除时此节点的父节点直接指向子节点，此时染黑替代的节点，也没问题)
- 删除的是根节点，此时 root 已经被清空 直接 return
-
到这里就只剩 删除黑色叶子了 这一步很复杂我分步讲解
1、被删除节点在父节点的左边或者右边 两种情况
左
2、兄弟节点为红色时，需要调整，让兄弟节点变为黑色
1、删除黑色叶子兄弟节点为红.png
3、此时删除黑色叶子节点的兄弟节点必为黑色 。
（1、兄弟节点的左右子节点为黑色 则表明兄弟节点不能借给被删除节点 节点，父节点下来与兄弟节点合并，这时父节点如果是红色则父节点染黑，兄弟节点染红。如果父节点为黑，则父节点产生下溢，递归调用自身方法（研究表明下溢情况不会连续下溢三次以上））
（2、来到这里兄弟节点必有一个或两个红色节点，然后通过染色，旋转即可恢复平衡）
右
右的逻辑和左的一样对称着写（想）就行
红黑树的平衡
- 红黑树没有做到完全平衡，没有一条路径是其他路径的两倍以上
- 黑色节点是完全平衡的
- 最大高度是 2 * log2(n + 1)
红黑树平均时间复杂度
- 搜索： O(logn) | 最大搜索次数：log2(n + 1)
- 添加： O(logn) | 最大搜索次数：log2(n + 1) | 旋转 O(1)次的旋转
- 删除： O(logn) | 最大搜索次数：log2(n + 1) | 旋转O(1)次的旋转
AVL平均时间复杂度
- 搜索： O(logn) | 最大搜索次数：log2(n + 1)
- 添加： O(logn) | 最大搜索次数：log2(n + 1) | 旋转：O(1)次的旋转
- 删除： O(logn) | 最大搜索次数：log2(n + 1) |旋转：O(log2(n + 1))次的旋转
