红黑树的平衡条件
- 每个节点非黑即红
- 根节点是黑色
- 叶节点(NIL)是黑色
- 如果一个节点是红色,则它的两个子节点都是黑色的
- 从根节点出发到所有叶节点路径上,黑色节点的数量相同
红黑树的特性
- 最长路径是最短路径的2倍
- NIL节点对于删除操作很重要
- 新插入的节点是红色的
平衡调整法门
- 插入调整站在祖父节点看
- 删除调整站在父节点看
- 插入调整的情况处理一共2种
- 删除调整的情况处理一共4种
插入调整的原则
调整前后,保持路径上黑色节点的数量相同。
插入调整情况一:
操作:祖父节点变为红色,父节点和uncle节点变为黑色
插入调整情况二:
LL类型的失衡:左子树是红色 左子树的左子树也是红色
- 大右旋
- 将祖父节点和两个父节点调整为红-黑-黑(红色上浮) or 黑-红-红(红色下沉)
LR类型的失衡:左子树是红色 左子树的右子树也是红色
- 小左旋
- 变为LL类型的失衡
RR类型的失衡:右子树是红色 右子树的右子树也是红色
- 大左旋
- 红色上浮 or 红色下沉
RL类型的失衡:右子树是红色 右子树的左子树也是红色
- 小右旋
- 变为RR类型的失衡
删除什么样的节点会导致红黑树失衡?
- 删除度为2的节点 可以转换为删除度为0的节点(删除前驱或后继节点 并替换根节点的值)
- 删除度为0的红色节点:不会失衡,黑色节点数量不变。
- 删除度为1的红色节点:红黑树中不存在度为1的红色节点,子节点不能为红,如果子节点为黑并只有一个,则红黑树失衡。
- 删除度为0的黑色节点:失衡,删除后的位置为NIL(双重黑)
- 删除度为1的黑色节点:不会失衡,删除后 红色子节点变黑即可(度为1的黑色节点 其子节点必然为红色 且红色下面再无子树)
删除调整情况一:
操作:
- 当前节点(95)变为黑色(-1)
- 兄弟节点(9)变为红色(-1)
- 父节点(43)变为双重黑(+1)
删除调整情况二:
RR类型 / LL类型的失衡:
- 抓着父节点(38)左旋 / 右旋
- 当前节点(28)【双重黑】改为黑色
- 父节点(38)【可能红 可能黑】改为黑色(旋转后的两个子节点改为黑色)
- borther节点的同测子节点(72)【红色】改为黑色(旋转后的两个子节点改为黑色)
- borther节点(51)【黑色】改为原根节点(38)的颜色【可能红 可能黑】
删除调整情况三:
RL类型 / LR类型的失衡:
- 抓着brother节点小右旋 / 小左旋
- brother【黑色】变为红色
- brother异侧的失衡子节点【红色】变为黑色
- 转换为RR / LL 类型的失衡
删除调整情况四:
brother节点为红色节点:
- 大左旋 / 大右旋
- 原根节点【黑色】改为红色
- brother节点【红色】改为黑色
- 转换为双重黑的兄弟节点是黑色的情况,判断其为“情况一/二/三”中的哪一种,再递归的进行处理
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define NIL &(node::__NIL)
struct node {
node(int key = 0, int color = 0, node *lchild = NIL, node *rchild = NIL)
: key(key), color(color), lchild(lchild), rchild(rchild) {}
int key;
int color; // 0 red, 1 black, 2 double black
node *lchild, *rchild;
static node __NIL;
};
node node::__NIL(0, 1);
node *getNewNode(int key) {
return new node(key);
}
bool has_red_child(node *root) {
return root->lchild->color == 0 || root->rchild->color == 0;
}
node *left_rotate(node *root) {
node *temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
return temp;
}
node *right_rotate(node *root) {
node *temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
return temp;
}
node *insert_maintain(node *root) {
int flag = 0;
if (root->lchild->color == 0 && has_red_child(root->lchild)) flag = 1;
if (root->rchild->color == 0 && has_red_child(root->rchild)) flag = 2;
if (flag == 0) return root;
if (root->lchild->color == 0 && root->rchild->color == 0) {
root->color = 0;
root->lchild->color = root->rchild->color = 1;
return root;
}
if (flag == 1) {
if (root->lchild->rchild->color == 0) {
root->lchild = left_rotate(root->lchild);
}
root = right_rotate(root);
} else {
if (root->rchild->lchild->color == 0) {
root->rchild = right_rotate(root->rchild);
}
root = left_rotate(root);
}
root->color = 0;
root->lchild->color = root->rchild->color = 1;
return root;
}
node *__insert(node *root, int key) {
if (root == NIL) return getNewNode(key);
if (key == root->key) return root;
if (key < root->key) {
root->lchild = __insert(root->lchild, key);
} else {
root->rchild = __insert(root->rchild, key);
}
return insert_maintain(root);
}
node *insert(node *root, int key) {
root = __insert(root, key);
root->color = 1;
return root;
}
node *erase_maintain(node *root) {
if (root->lchild->color != 2 && root->rchild->color != 2) return root;
// 情况四
int flag = 0;
if (has_red_child(root)) {
root->color = 0;
if (root->lchild->color == 0) {
root = right_rotate(root); flag = 1;
} else {
root = left_rotate(root); flag = 2;
}
root->color = 1;
if (flag == 1) root->rchild = erase_maintain(root->rchild);
else root->lchild = erase_maintain(root->lchild);
return root;
}
// 情况一
if ((root->lchild->color == 1 && !has_red_child(root->lchild))
|| (root->rchild->color == 1 && !has_red_child(root->rchild))) {
root->lchild->color -= 1;
root->rchild->color -= 1;
root->color += 1;
return root;
}
// 情况二/三
if (root->lchild->color == 1) {
// L*
root->rchild->color = 1; // 双重黑改为黑
if (root->lchild->lchild->color != 0) {
// LR
root->lchild->color = 0;
root->lchild = left_rotate(root->lchild);// 左旋
root->lchild->color = 1;
}
// LL
root->lchild->color = root->color; // borther改为root颜色
root = right_rotate(root);
} else {
// R*
root->lchild->color = 1; // 双重黑改为黑
if (root->rchild->rchild->color != 0) {
// RL
root->rchild->color = 0;
root->rchild = right_rotate(root->lchild);
root->rchild->color = 1;
}
// RR
root->rchild->color = root->color; // borther改为root颜色
root = left_rotate(root);
}
root->lchild->color = root->rchild->color = 1; // 旋转后的左右子节点为黑色
return root;
}
node *predecessor(node *root) {
node *temp = root->lchild;
while (temp->rchild != NIL) temp = temp->rchild;
return temp;
}
node *__erase(node *root, int key) {
if (root == NIL) return root;
if (key < root->key) {
root->lchild = __erase(root->lchild, key);
} else if (key > root->key) {
root->rchild = __erase(root->rchild, key);
} else {
if (root->lchild == NIL || root->rchild == NIL) {
node *temp = root->lchild == NIL ? root->rchild : root->lchild;
temp->color += root->color;
delete root;
return temp;
} else {
node *temp = predecessor(root);
root->key = temp->key;
root->lchild = __erase(root->lchild, temp->key);
}
}
return erase_maintain(root);
}
node *erase(node *root, int key) {
root = __erase(root, key);
root->color = 1;
return root;
}
void clear(node *root) {
if (root == NIL) return ;
clear(root->lchild);
clear(root->rchild);
delete root;
return ;
}