红黑树同AVL树（平衡二叉树），都是在进行插入和删除时，通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。俩者不同的是：AVL树是严格的平衡二叉树，平衡条件必须满足所有节点的左右子树高度差不超过1，而红黑树只是尽量达到平衡，可以存在左右子树高度差超过1的情况存在。
红黑树性质：
1、每一个节点要么黑色要么红色。
2、根节点一定为黑色。
3、每一个叶子节点（每条树枝末端隐藏的空节点NIL）都为黑色。
4、每一个红色的节点的俩个子节点必为黑色（即不能存在连续俩个红色节点相连）。
5、每一个节点的所有支路到叶子节点途径上有相同的黑色节点数目。
// 枚举节点颜色类型
enum COLOR { RED, BLACK };
typedef int keyType;
// 节点
class RBTNode {
public:
RBTNode(keyType key) :Key(key), Left(NULL), Right(NULL), Parent(NULL), Color(RED) {}
keyType Key;
RBTNode* Left;
RBTNode* Right;
RBTNode* Parent;
COLOR Color;
};
// 红黑树
class RBT {
public:
bool Insert(keyType key); // 插入
bool Delete(keyType key); // 删除
RBT() :Root(NULL) {}
RBT(keyType key) :Root(new RBTNode(key)) {}
RBTNode* Root;
};插入：
// 插入
bool RBT::Insert(keyType key) {
if (NULL == Root) {
Root = new RBTNode(key);
Root->Color = BLACK;
return true;
}
RBTNode* T = Root;
while (1) {
if (key == T->Key) return false;
else if (key < T->Key) {
if (NULL == T->Left) break;
T = T->Left;
}
else {
if (NULL == T->Right) break;
T = T->Right;
}
}
if (key < T->Key) {
T->Left = new RBTNode(key);
T->Left->Parent = T;
T = T->Left;
}
else {
T->Right = new RBTNode(key);
T->Right->Parent = T;
T = T->Right;
}
// 颜色修正
RBT_Fix(*this, T);
return true;
}节点插入插入操作跟二叉查找树相同，区别在与，插入之后节点的颜色是否需要改变。
旋转操作：
左旋：
右旋：
// 左旋
void LRotate(RBT &Tree, RBTNode* node) {
RBTNode* T = node->Right;
RBTNode* P = node->Parent;
node->Right = T->Left;
T->Left = node;
if (node->Right) node->Right->Parent = node;
T->Parent = P;
node->Parent = T;
if (NULL == T->Parent) Tree.Root = T;
else {
if (node == P->Left) P->Left = T;
else P->Right = T;
}
}
// 右旋
void RRotate(RBT &Tree, RBTNode* node) {
RBTNode* T = node->Left;
RBTNode* P = node->Parent;
node->Left = T->Right;
T->Right = node;
if (node->Left) node->Left->Parent = node;
T->Parent = P;
node->Parent = T;
if (NULL == T->Parent) Tree.Root = T;
else {
if (node == P->Left) P->Left = T;
else P->Right = T;
}
}节点颜色调节：
默认插入节点的颜色为红色。若为黑色则会频繁违反黑红树的性质5，需要频繁的调整。
1. 当插入节点的父节点为黑色时，不影响红黑树的结构性质，不需要进行调整。
2. 当父节点为红色时，又存在不同的情况。
2.1 父节点的兄弟节点（叔节点）为红色，则祖父节必定存在且为黑色。
将祖父节点变为红色，父节点和叔节点变为黑色，将祖父节点设为新的插入节点。（这只是 局部的调整完毕，将祖父节点变为红色，若祖父节点的父节点为红色则会再次失衡，所以需 将祖父节点设为新的插入节点判断是否需要变色调整）
2.2 叔节点的颜色为黑色，又分俩种情况
2.2.1 插入节点为父节点的左孩子
2.2.1.1 父节点为祖父节点的左孩子。将祖父节点变为红，父节点变为黑，右旋祖 父节点
2.2.1.2 父节点为祖父节点的右孩子。右旋父节点，将父节点和插入节点互换，变 为2.2.2.2的情况。
2.2.2 插入节点为父节点的右孩子
2.2.2.1 父节点为祖父节点的左孩子。左旋父节点，将父节点和插入节点互换，变 为2.2.1.1的情况。
2.2.2.2 父节点为祖父节点的右孩子。将父节点变为黑色，祖父节点变为红色，左 旋祖父节点。
// 改色
void RBT_Fix(RBT &Tree, RBTNode* node) {
RBTNode* P = node->Parent;
RBTNode* GP = NULL;
RBTNode* U = NULL;
// 1. 父亲节点为红（必存在祖父节点）
while (P&&P->Color == RED) {
GP = P->Parent;
// 1.1 父为祖父左孩子
if (P == GP->Left) {
U = GP->Right;
// 1.1.1 叔节为红 ---> 祖父节点必为黑 黑红红--> 红黑黑
if (U&&U->Color == RED) {
GP->Color = RED;
P->Color = BLACK;
U->Color = BLACK;
node = GP;
P = node->Parent;
}
// 1.1.2 叔节点为黑（含NIL黑节点）
else {
// 1.1.2.1 插入节点为P 的左孩子
if (node == P->Left) {
GP->Color = RED;
P->Color = BLACK;
RRotate(Tree, GP);
}
// 1.1.2.1 插入节点为P 的右孩子
else {
RBTNode* T = P;
LRotate(Tree, P);
P = node;
node = T;
}
}
}
// 1.2 父为祖父右孩子
else {
U = GP->Left;
// 1.2.1 叔节点为红色
if (U&&U->Color == RED) {
GP->Color = RED;
P->Color = BLACK;
U->Color = BLACK;
node = GP;
P = node->Parent;
}
// 1.2.2 叔节点为黑色
else {
// 插入节点为父节点的左孩子
if (node == P->Left) {
RBTNode* T = P;
RRotate(Tree, P);
P = node;
node = P;
}
// 插入节点为父节点的右孩子
else {
GP->Color = RED;
P->Color = BLACK;
LRotate(Tree, GP);
}
}
}
}
// 2. 父亲节点为黑 （不需要调整）
Tree.Root->Color = BLACK;
}删除：
红黑树的删除操作相较于插入操作更加复杂，另开一篇记录，红黑树删除。