红黑树
二叉搜索树
二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
二叉搜索树简单的说就是：对树中任何结点x，其左子树中的关键字最大不超过x.key，即对左子树中任一结点y，有y.key
下面这两棵树都是搜索树
平衡二叉搜索树
又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。如图：
最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。
红黑树
首先红黑树是一颗二叉搜索树，是一种自平衡二叉搜索树。在二叉搜索树的基础上满足以下性质：
- 每个结点是红色或者黑色
- 根结点永远是黑色
- 每个叶子结点都是黑色的空结点（Null结点）
- 若一个结点是红色的，那么他的子结点必须是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
- 对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点
如下图示例
识别红黑树
1和3不满足第五点性质
4不满足第二点性质
红黑树结点结构
template
struct RBTreeNode {
Color color; // 描述结点颜色
RBTreeNode *parent; // 指向该结点的父结点，若该结点为根结点，则为NIL
RBTreeNode *left; // 指向左子树
RBTreeNode *right; // 指向右子树
K key;
V value;
};
声明一颗红黑树
template
class RBTree {
/*省略各种方法*/
private:
RBTreeNode *m_root;
// 由于根节点和叶子结点属性值为NIL，为了便于处理红黑树代码中的边界条件，使用一个哨兵T.nil来代表所有的NIL
RBTreeNode *m_nil;
};
红黑树的搜索
? 由于每一棵红黑树都是二叉搜索树，可以使用与搜索普通二又搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。
? 对普通二又搜索树进行搜索的时间复杂性为O（h），对于红黑树则为O（log2n）。因为在搜索普通二又搜索树、AVL树和红黑树时使用了相同的代码，并且在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下AVL树能获得最优的时间复杂性。
红黑树的插入
前提条件，新插入结点的颜色默认红色。原因：若为黑色，插入后必将违反红黑树的第五条特性，所有从根到外部结点的路径上的黑色结点个数不等。每次都得旋转，且高度不好判断,操作起来比较麻烦。若为红色，属于有可能违反红黑树第四条特性，但不是每次都会违反。只需要判断连续两个结点不同时为红色，若为红色，则进行平衡（旋转），相对来说操作简单。
如果插入前是空树，那么新元素将成为根结点，根结点必须染成黑色。
非空树的情况：
先默认父结点是祖父结点的左子树（作为右子树的时候，与左子树的情况属于镜像对称，处理与左子树的处理反过来就可以了）
1.若插入结点位置的父结点是黑色结点，则特性没有破坏，不需要进行平衡操作
2.若父结点是红色结点（祖父结点必为黑色），则会出现连续两个红色结点的情形（违反第四特性），要进行平衡操作，这时还要考虑父结点的兄弟结点
-
如果父结点的兄弟结点（后续简称叔结点）是红色结点，则把祖父结点颜色变成红色，父结点与叔结点变成黑色。然后向上递归处理，即把当前结点的指向祖父结点，变成祖父结点后，再次插入的相关判断
如下列所示，往红黑树插入1结点
找到位置，插入1结点，发现1结点的父结点5是红色的，同时叔结点也是红色的，则进行换色
把父结点5和叔结点13的颜色变成黑色，再把祖父结点9的颜色变成红色。初步插入完成。
然后向上传递处理，当前结点指向祖父结点。发现此时当前9结点的父结点18是黑色，特性没有破坏，不需要进行平衡操作。插入操作结束。
PS：由于平衡过程中，有可能把root结点变成红色，所以插入操作结束，最后顺手一下把root结点的颜色再次设置为黑色，以满足第二特性。参考下列情形插入8
-
如果叔结点是黑色结点
-
且当前结点是左子树
对祖父结点做一次右旋，交换父结点和祖父结点的颜色，就可恢复红黑树的特性，并结束重新平衡过程。然后向上传递处理。如下插入1
-
且当前结点是右子树
先对父结点做一次左旋，对祖父结点做一次右旋，交换父结点和祖父结点的颜色。就可恢复红黑树的特性，并结束重新平衡过程。然后向上传递处理。如下插入6
对05结点进行左旋
对09结点右旋
变色
-
红黑树结点旋转
设计每个结点各有三个指针，分别指向各自的左右子树以及父结点
1.左旋（动3个方向，6个指向）
- X的右子树指针，指向Y的左子树
- Y的左子树的指向父结点的指针，指向X
- Y的父结点指针，指向X的父结点
- X的父结点的指向X的指针，指向Y（这里得判断三种情况（1.X本身是根节点，即其父结点是空节点；2.X是其父结点的左子树；3.X是父结点的右子树））
- Y的左子树指针指向X
- X的指向父结点的指针，指向Y
2.右旋（一样是动3个方向，6个指向，和左旋反过来）
- Y的左子树指针，指向X的右子树
- X的右子树的指向父节点的指针，指向Y
- X的父结点指针，指向Y的父结点
- Y的父结点的指向X的指针，指向X(同上推导情况)
- X的左子树指针指向Y
- Y的指向父结点的指针，指向X
红黑树删除
待续
示例代码：
enum class Color {
RED, BLACK
};
template
struct RBTreeNode {
Color color;
RBTreeNode *parent;
RBTreeNode *left;
RBTreeNode *right;
K key;
V value;
RBTreeNode() : color(Color::RED), parent(nullptr), left(nullptr), right(nullptr) {}
RBTreeNode(const K &k, const V &v) : color(Color::RED), parent(nullptr), left(nullptr), right(nullptr), key(k),
value(v) {}
};
template
class RBTree {
using RBTNode = RBTreeNode;
public:
RBTree() {
m_nil = NewNode();
m_nil->color = Color::BLACK;
m_root = m_nil;
}
~RBTree() {
DestroyTree(m_root); //销毁创建的非Nil结点
delete m_nil; //最后删除Nil结点
m_nil = nullptr;
}
public:
/*省略部分方法*/
//插入
bool Insert(RBTNode *node);
//插入修正
void InsertFixup(RBTNode *node);
private:
//创建结点
RBTreeNode *NewNode(const K &k = K{}, const V &v = V{}) {
auto *node = new RBTNode();
return node;
}
//销毁红黑树
void Destroy(RBTNode *&root) {
if (root == m_nil) {
return;
}
if (root->left != m_nil) {
Destroy(root->left);
}
if (root->right != m_nil) {
Destroy(root->right);
}
delete root;
root = nullptr;
}
//左旋
void LeftRotate(RBTNode *x);
//右旋
void RightRotate(RBTNode *y);
private:
RBTNode *m_root;
RBTNode *m_nil;
};
template
bool RBTree::Insert(RBTNode *node) {
auto x = m_root;
auto y = m_nil; // 记录要插入结点位置的父结点
while (x != m_nil) {
y = x;
if (node->key > x->key) {
x = x->right;
} else if (node->key < x->key) {
x = x->left;
} else {
//这里看实际需求，key相同即可以做值覆盖（x->value = node->value）。也可以不操作，默认插入失败
return false;
}
}
node->parent = y;
if (y == m_nil) {
m_root = node;
} else if (node->key > y->key) {
y->right = node;
} else {
y->left = node;
}
node->left = m_nil;
node->right = m_nil;
// node->color = Color::RED;
//调整平衡
InsertFixup(node);
return true;
}
template
void RBTree::LeftRotate(RBTNode *x) {
auto y = x->right;
x->right = y->left;
if (y->left != m_nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == m_nil) {
m_root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
template
void RBTree::RightRotate(RBTNode *y) {
auto x = y->left;
y->left = x->right;
if (x->right != m_nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == m_nil) {
m_root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
template
void RBTree::InsertFixup(RBTNode *node) {
//父结点是红色
while (node->parent->color == Color::RED) {
//父结点本身是左子树
if (node->parent == node->parent->parent->left) {
//叔结点
auto uncleNode = node->parent->parent->right;
//叔结点也是红色
if (uncleNode->color == Color::RED) {
node->parent->color = Color::BLACK;
uncleNode->color = Color::BLACK;
node->parent->parent->color = Color::RED;
//将结点指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色
node = node->parent->parent;
} else {//叔结点是黑色的（可以是叶子结点）
// 插入结点是其父结点的右子树--对其父结点左旋
if (node == node->parent->right) {
LeftRotate(node->parent);
}
//左旋后或者本身插入结点是其父结点的左子树
//代码先变色-再旋转好处理一点
node->parent->color = Color::BLACK;
node->parent->parent->color = Color::RED;
//右旋
RightRotate(node->parent->parent);
}
} else {
auto uncleNode = node->parent->parent->left;
if (uncleNode->color == Color::RED) {
node->parent->color = Color::BLACK;
uncleNode->color = Color::BLACK;
node->parent->parent->color = Color::RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
RightRotate(node);
}
node->parent->color = Color::BLACK;
node->parent->parent->color = Color::RED;
LeftRotate(node->parent->parent);
}
}
}
m_root->color = Color::BLACK;
}