使用c++实现红黑树的构建和插入

1.红黑树简介：

红黑树实际上和AVL都属于一棵用于存储数据的平衡二叉搜索树，但是这棵树并不是使用平衡因子去维持平衡的，而是结合限制条件对结点标红标黑去让树达到类似平衡的效果。

2.红黑树的限制条件和效率分析：

2.1限制条件

1. 每个结点不是红⾊就是⿊⾊

2. 根结点是⿊⾊的

3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的

红⾊结点。

4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

2.2效率分析

由规则四可以知道每条路径上的黑结点个数相同，那么在极端情况下，最短路径就是全黑，最长路径就是一黑一红，设最短路径长度为h，最长则为2h，-1<N<,推导可得h基本上就是为一个logn，说明在插入的时候最差的时间复杂度也就为接近2*logn。

3.红黑树构建时的准备：

3.1红黑标记：

3.2红黑树的结点结构设计：

这里每个结点默认都是处理为红色，因为如果你处理成黑色的话，那当别的地方要处理成红色的时候，别的地方要保持规则四就很困难了，因为这个存储结构是一棵树。

3.3红黑树的结构设计：

template<class K, class V>
class rb_tree {typedef rb_tree_node<K,V> node;
private:node* root_=nullptr;
};

基本上和AVL树很类似。

3.4处理前的插入：

bool insert(const pair<K, V>& kv) {if (root_ == nullptr) {root_ = new node(kv);root_->col = BLACK;//规定的根为黑色return true;}node* cur = root_;//这部分就和别的二叉搜索树一致node* parent = root_;while (cur) {if (cur->kv_.first > kv.first) {parent = cur;cur = cur->left;}else if (cur->kv_.first < kv.first) {parent = cur;cur = cur->right;}else {return false;}}cur = new node(kv);if (parent->kv_.first > kv.first) {parent->left = cur;}else {parent->right = cur;}cur->parent = parent;

4.对违反规则的地方进行处理：

4.1情况1：

当插入x时，因为红色的子结点必须是黑色的，所以需要进行处理，如果他的叔叔结点是红色的，那么无论他是在6还是15插入，只需要把它的叔叔结点和父亲结点变为黑色，然后再把它的父亲变为红色。那么就能保证规则不被破坏，每条路的黑结点个数都相同。这里并不是就是结束！当变为红色的时候，可能导致上面的规则遭到破坏，也就是它的上方可能是红色的，那么它也得进行类似的处理。

4.2情况2：

当插入位置为在cur且叔叔为黑色或者不存在的时候，通过这样处理之后可以让规则得到满足。也就是进行一次右单选再与情况1进行相同方式的变色。

4.3情况3：

当cur位置为在cur且叔叔为黑色或者不存在的时候，通过这样处理之后可以让规则得到满足。也就是进行一次左单选再右单旋最后与情况1进行相同方式的变色。

---

这里还存在一种特殊情况，就是有可能根结点会被处理成红色，但是，根结点实际上是不会影响分路上黑结点分布相同的。所以最后只需要把根结点也处理成黑色就能保证规则不会出现问题。

通过这三种情况就能够把所有情况给包含进去了。

4.4代码展示：

	while (parent && parent->col == RED) {//node* grandfather = parent->parent;if (grandfather->left == parent) {//处理左子树if (grandfather->right && grandfather->right->col == RED) {//叔是红色parent->col = BLACK;//变色grandfather->right->col = BLACK;grandfather->col = RED;cur = grandfather;//往上接着迭代parent = grandfather->parent;}else {//叔叔不存在或者叔叔为黑色if (cur == parent->left) {//只需要单旋就能解决rotateR(grandfather);grandfather->col = RED;parent->col = BLACK;}else {//需要双旋才能解决rotateL(parent);rotateR(grandfather);grandfather->col = RED;parent->col = BLACK;}break;}}else {if (grandfather->left&&grandfather->left->col == RED) {//叔是红色parent->col = BLACK;//变色grandfather->left->col = BLACK;grandfather->col = RED;cur = grandfather;//往上接着迭代parent = grandfather->parent;}else {//叔叔不存在或者叔叔为黑色if (cur == parent->right) {//只需要单旋就能解决rotateL(grandfather);grandfather->col = RED;parent->col = BLACK;}else {//需要双旋才能解决rotateR(parent);rotateL(grandfather);grandfather->col = RED;parent->col = BLACK;}break;}}}root_->col = BLACK;//最后记得把根结点的颜色变为黑色return true;
}

5.完整代码展示：

#include <iostream>
using namespace std;
enum color {RED,BLACK
};
template<class K,class V>
class rb_tree_node {
public:rb_tree_node(const pair<K, V>& kv) :kv_(kv), right(nullptr), left(nullptr), parent(nullptr), col (RED){}rb_tree_node* right;rb_tree_node* left;rb_tree_node* parent;pair<K, V> kv_;color col;
};
template<class K, class V>
class rb_tree {typedef rb_tree_node<K,V> node;
public:bool insert(const pair<K, V>& kv) {if (root_ == nullptr) {root_ = new node(kv);root_->col = BLACK;return true;}node* cur = root_;node* parent = root_;while (cur) {if (cur->kv_.first > kv.first) {parent = cur;cur = cur->left;}else if (cur->kv_.first < kv.first) {parent = cur;cur = cur->right;}else {return false;}}cur = new node(kv);if (parent->kv_.first > kv.first) {parent->left = cur;}else {parent->right = cur;}cur->parent = parent;while (parent && parent->col == RED) {node* grandfather = parent->parent;if (grandfather->left == parent) {if (grandfather->right && grandfather->right->col == RED) {//叔是红色parent->col = BLACK;//变色grandfather->right->col = BLACK;grandfather->col = RED;cur = grandfather;//往上接着迭代parent = grandfather->parent;}else {//叔叔不存在或者叔叔为黑色if (cur == parent->left) {//只需要单旋就能解决rotateR(grandfather);grandfather->col = RED;parent->col = BLACK;}else {//需要双旋才能解决rotateL(parent);rotateR(grandfather);grandfather->col = RED;parent->col = BLACK;}break;}}else {if (grandfather->left&&grandfather->left->col == RED) {//叔是红色parent->col = BLACK;//变色grandfather->left->col = BLACK;grandfather->col = RED;cur = grandfather;//往上接着迭代parent = grandfather->parent;}else {//叔叔不存在或者叔叔为黑色if (cur == parent->right) {//只需要单旋就能解决rotateL(grandfather);grandfather->col = RED;parent->col = BLACK;}else {//需要双旋才能解决rotateR(parent);rotateL(grandfather);grandfather->col = RED;parent->col = BLACK;}break;}}}root_->col = BLACK;return true;}void rotateR(node* parent) {node* sub_L = parent->left;node* sub_LR = sub_L->right;parent->left = sub_LR;if (sub_LR) {sub_LR->parent = parent;}sub_L->right = parent;if (parent == root_) {root_ = sub_L;}node* ppnode;ppnode = parent->parent;if (ppnode) {if (ppnode->right == parent) {ppnode->right = sub_L;}else {ppnode->left = sub_L;}}parent->parent = sub_L;}void rotateL(node* parent) {node* sub_R = parent->right;node* sub_RL = sub_R->left;parent->right = sub_RL;if (sub_RL) {sub_RL->parent = parent;}sub_R->left = parent;if (parent == root_) {root_ = sub_R;}node* ppnode;ppnode = parent->parent;if (ppnode) {if (ppnode->right == parent) {ppnode->right = sub_R;}else {ppnode->left = sub_R;}}parent->parent = sub_R;}void inorder() {inorder_(root_);}
private:void inorder_(node* root) {if (root == nullptr) {return;}inorder_(root->left);cout << root->kv_.first <<" ";inorder_(root->right);}node* root_=nullptr;
};
int main() {rb_tree<int, int>tree1;tree1.insert({ 2,2 });tree1.insert({ 3,2 });tree1.insert({ 1,2 });tree1.insert({ 5,2 });tree1.insert({ 4,2 });tree1.insert({ 6,2 });tree1.inorder();return 0;
}