目录

一、概念

二、红黑树的插入操作

第一步: 按照二叉搜索树的规则插入新节点

第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整

情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

三、红黑树的验证

检测其是否满足二叉搜索树

检测其是否满足红黑树的性质

四、完整代码

五、红黑树与AVL树的比较

一、概念

红黑树，是一种二叉搜索树。但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出两倍，因而是接近平衡的。

性质:
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 若一个节点是红色的，则它的两个孩子结点是黑色的(即树中没有连续的红色结点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(即每条路径上黑色结点数量相等)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NIF)

二、红黑树的插入操作

红黑树的插入操作大致可以分成两步:

第一步: 按照二叉搜索树的规则插入新节点

bool insert(const pair& kv) {if (_root == nullptr) {_root = new TreeNode(kv);_root->_color = BLACK;return true;}TreeNode* parent = nullptr;TreeNode* cur = _root;while (cur != nullptr) {if (kv.first > cur->_data.first) {parent = cur;cur = cur->_right;}else if (kv.first < cur->_data.first) {parent = cur;cur = cur->_left;}else return false;}cur = new TreeNode(kv);cur->_color = RED;if (kv.first > parent->_data.first) {parent->_right = cur;}else { //kv.first < parent->_data.first)parent->_left = cur;}cur->_parent = parent;//………………}

第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整

新节点的默认颜色是红色，若其双亲结点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入结点的双亲结点颜色为红色时，就出现了连续的红色结点，此时需要对红黑树分情况来讨论：

情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红

if (uncle != nullptr && uncle->_color == RED) {parent->_color = uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;
}

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)

uncle的情况有两种:

1.若uncle结点不存在时，cur结点一定是新增结点。若cur不是新增结点，则cur和parent之间一定有一个黑色结点。这不满足性质4:每条路径上黑色结点的个数相同。

2.若uncle存在且为黑色，那么cur原来的颜色一定为黑色。看到cur结点是红色，是因为cur的子树在调整的过程中将cur的颜色从黑色改变为红色。

//右单旋 + 变色
if (cur == parent->_left) {rotate_right(grandfather);grandfather->_color = RED;parent->_color = BLACK;
}//左单旋 + 变色
if (cur == parent->_right) {rotate_left(grandfather);grandfather->_color = RED;parent->_color = BLACK;
}

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)

//左右双旋 + 变色
else {//cur == parent->_rightrotate_left(parent);rotate_right(grandfather);cur->_color = BLACK;grandfather->_color = RED;
}//右左双旋 + 变色
else {//cur == parent->_leftrotate_right(parent);rotate_left(grandfather);cur->_color = BLACK;grandfather->_color = RED;
}

三、红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树

使用中序遍历判断其是否有序即可，这里不做过多解释

检测其是否满足红黑树的性质

bool IsBalance() {//空树也是红黑树if (_root == nullptr) return true;//根结点是黑色的if (_root->_color != BLACK) return false;int benchmark = 0;//基准值return _IsBalance(_root, 0, benchmark);
}bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) {if (root == nullptr) {if (benchmark == 0) {benchmark = blackNum;//将第一条路径的blackNum设为基准值return true;}else {return blackNum == benchmark;}}if (root->_color == BLACK) ++blackNum;if (root->_color == RED && root->_parent->_color == RED) return false;//逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点return _IsBalance(root->_left, blackNum, benchmark) && _IsBalance(root->_right, blackNum, benchmark);
}

四、完整代码

#include
#include
using std::pair;
using std::make_pair;
using std::cout;
using std::cout;
using std::endl;enum Color { RED,BLACK };
template
struct RedBlackTreeNode {RedBlackTreeNode(const pair& kv) :_parent(nullptr), _left(nullptr), _right(nullptr), _data(kv),_color(RED){}RedBlackTreeNode* _parent;RedBlackTreeNode* _left;RedBlackTreeNode* _right;pair _data;Color _color;
};template
class RedBlackTree 
{typedef RedBlackTreeNode TreeNode;
public:bool insert(const pair& kv) {if (_root == nullptr) {_root = new TreeNode(kv);_root->_color = BLACK;return true;}TreeNode* parent = nullptr;TreeNode* cur = _root;while (cur != nullptr) {if (kv.first > cur->_data.first) {parent = cur;cur = cur->_right;}else if (kv.first < cur->_data.first) {parent = cur;cur = cur->_left;}else return false;}cur = new TreeNode(kv);cur->_color = RED;if (kv.first > parent->_data.first) {parent->_right = cur;}else { //kv.first < parent->_data.first)parent->_left = cur;}cur->_parent = parent;while (parent && parent->_color == RED){TreeNode* grandfather = parent->_parent;assert(grandfather != nullptr);//当parent结点为红时，grandfather结点必不为空(根结点为黑)assert(grandfather->_color == BLACK);//当parent结点为红时，grandfather结点必为黑色(否则违反性质，出现连续的红色结点)if (parent == grandfather->_left) {TreeNode* uncle = grandfather->_right;if (uncle != nullptr && uncle->_color == RED) {parent->_color = uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else {//uncle不存在或者为黑//右单旋 + 变色if (cur == parent->_left) {rotate_right(grandfather);grandfather->_color = RED;parent->_color = BLACK;}//左右双旋 + 变色else {//cur == parent->_rightrotate_left(parent);rotate_right(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else {//parent == grandfather->_rightTreeNode* uncle = grandfather->_left;if (uncle != nullptr && uncle->_color == RED) {parent->_color = uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = cur->_parent;}else {//uncle不存在或者为黑//左单旋 + 变色if (cur == parent->_right) {rotate_left(grandfather);grandfather->_color = RED;parent->_color = BLACK;}//右左双旋 + 变色else {//cur == parent->_leftrotate_right(parent);rotate_left(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}}_root->_color = BLACK;return true;}void inorder() {_inorder(_root);}bool IsBalance() {//空树也是红黑树if (_root == nullptr) return true;//根结点是黑色的if (_root->_color != BLACK) return false;int benchmark = 0;//基准值return _IsBalance(_root, 0, benchmark);}
private:void _inorder(TreeNode* root) {if (root == nullptr) {return;}_inorder(root->_left);cout << root->_data.first << ":" << root->_data.second << " ";_inorder(root->_right);}bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) {if (root == nullptr) {if (benchmark == 0) {benchmark = blackNum;return true;}else {return blackNum == benchmark;}}if (root->_color == BLACK) ++blackNum;if (root->_color == RED && root->_parent->_color == RED) return false;//逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点return _IsBalance(root->_left, blackNum, benchmark) && _IsBalance(root->_right, blackNum, benchmark);}void rotate_left(TreeNode* parent) {TreeNode* subR = parent->_right;TreeNode* subRL = subR->_left;TreeNode* pparent = parent->_parent;parent->_right = subRL;if (subRL != nullptr) subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;//解决根结点变换带来的问题if (_root == parent) {_root = subR;subR->_parent = nullptr;}else {if (pparent->_left == parent) pparent->_left = subR;else pparent->_right = subR;subR->_parent = pparent;}}void rotate_right(TreeNode* parent) {TreeNode* subL = parent->_left;TreeNode* subLR = subL->_right;TreeNode* pparent = parent->_parent;parent->_left = subLR;if (subLR != nullptr) subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) {_root = subL;subL->_parent = nullptr;}else {if (pparent->_left == parent) pparent->_left = subL;else pparent->_right = subL;subL->_parent = pparent;}}private:TreeNode* _root = nullptr;
};void RBTreeTest() {size_t N = 10000;srand((unsigned)time(NULL));RedBlackTree t;for (size_t i = 0; i < N; ++i) {int x = rand();//cout << "insert:" << x << ":" << i << endl;t.insert(make_pair(x, i));}t.inorder();cout << t.IsBalance() << endl;}
int main() 
{RBTreeTest();return 0;
}

五、红黑树与AVL树的比较

与AVL树的平衡 (左右高度差不超过1) 相比，红黑树的平衡(没有一条路径会比其他路径长出两倍)并没有那么严格。所以两者在插入或删除相同数据时，红黑树需要旋转调整的次数更少，这使得红黑树的性能略高于AVL树。
可是AVL树更加平衡，查找数据所需的次数不是更加少吗？在AVL树与红黑树中进行数据的查找都十分快捷(譬如在查找100万数据中进行查找只需大概20次)，对于CPU从时间上来说并不会造成什么负担。
总的来说，AVL树更适用于插入删除不频繁，只对查找要求较高的场景; 红黑树相较于AVL树更适应对插入、删除、查找要求都较高的场景，红黑树在实际中运用更加广泛。