手撕红黑树

学了很久编程了，红黑树在我们耳边早就如雷贯耳，都说他是数据结构中最难的几种结构了，但是，实际上学会了之后，你会发现他还是很简单的，个人认为他还没有AVL树的旋转难，好了，老规矩，来上代码：

#pragma once
#pragma once
#include <iostream>
#include <set>
#include <map>
#include <assert.h>
#include <math.h>
#include <vector>
using namespace std;
namespace cc
{enum colour{RED,BLACK};template<class K, class V>struct RBtreenode{colour _col;pair<K, V> _val;RBtreenode<K, V>* _left;RBtreenode<K, V>* _right;RBtreenode<K, V>* _parent;RBtreenode(const pair<K, V>& x):_val(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template<class K, class V>class RBtree{public:typedef RBtreenode<K, V> node;void reor(node* parent){node* sub = parent->_left;node* subr = sub->_right;if (_root == parent){_root = sub;sub->_parent = nullptr;sub->_right = parent;parent->_parent = sub;parent->_left = subr;if (subr)subr->_parent = parent;}else{node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = sub;elsepparent->_right = sub;sub->_parent = pparent;sub->_right = parent;parent->_parent = sub;parent->_left = subr;if (subr)subr->_parent = parent;}}void reol(node* parent){node* sub = parent->_right;node* subl = sub->_left;if (_root == parent){_root = sub;sub->_parent = nullptr;sub->_left = parent;parent->_parent = sub;parent->_right = subl;if (subl)subl->_parent = parent;}else{node* pparent = parent->_parent;if (pparent->_left = parent)pparent->_left = sub;elsepparent->_right = sub;sub->_parent = pparent;sub->_left = parent;parent->_parent = sub;parent->_right = subl;if (subl)subl->_parent = parent;}}bool insert(const pair<K, V>& x){if (_root == nullptr){_root = new node(x);_root->_col = BLACK;return true;}node* parent = nullptr;node* cur = _root;while (cur){if (x.first < cur->_val.first){parent = cur;cur = cur->_left;}else if (x.first > cur->_val.first){parent = cur;cur = cur->_right;}elsereturn false;}cur = new node(x);if (parent->_val.first > x.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;node* grandfather = parent->_parent;while (parent && parent->_col == RED){if (grandfather->_left == parent){node* uncle = grandfather->_right;//情况一：只染色if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;if (grandfather == _root){grandfather->_col = BLACK;break;}}//情况二+三：旋转+染色else if (uncle && uncle->_col == BLACK){if (parent->_left == cur){//单旋reor(grandfather);//染色grandfather->_col = RED;parent->_col = BLACK;}else{//双旋reol(parent);reor(grandfather);//染色cur->_col = BLACK;//爷爷节点变红grandfather->_col = RED;}break;}else if (uncle == nullptr){if (parent->_left == cur){reor(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{reol(parent);reor(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;if (_root == grandfather){grandfather->_col = BLACK;break;}}else if (uncle && uncle->_col == BLACK){if (parent->_left == cur){reor(parent);reol(grandfather);grandfather->_col = RED;cur->_col = BLACK;}else{reol(grandfather);grandfather->_col = RED;parent->_col = BLACK;}break;}else if (uncle == nullptr){if (parent->_left = cur){reor(parent);reol(grandfather);cur->_col = BLACK;grandfather->_col = RED;}else{reol(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}}cur = grandfather;parent = cur->_parent;grandfather = parent->_parent;}return true;}bool check(){return _check(_root);}void print(){prin(_root);}void prin(node* root,int num){if (root == nullptr)return;if (root->_col == BLACK)num++;if (root->_left == root->_right &&root->_left == nullptr)cout << num << endl;prin(root->_left,num);prin(root->_right,num);}bool _check(node* root){if (root == nullptr){if (root->_col != BLACK)exit(-1);return true;}if (root->_parent && root->_parent->_col == RED){cout << "异常退出" << endl;exit(-1);}int num = 0;prin(root, num);}private:node* _root = nullptr;};
}

其实和AVL树的代码差不多，唯一不同的是，我们没有平衡因子了，但是有颜色。

下面来说说红黑树的规则：

1.一个节点不是红色就是黑色

2.根节点必须是黑色

3.红色节点的两个孩子必须是黑色节点

4.每条路径的黑色节点个数相同

5.叶子结点（NIL节点）是黑色的

上面就是红黑树的规则，红黑树的代码就在上面，现在说一下红黑树的具体实现规则：

1.如果叔叔节点存在且叔叔节点为红色，那么，把父节点和叔叔节点染成黑色，组父节点染成红色，如果此时的祖父节点是根节点，那么，就在把祖父节点染成黑色。如果不是，就把新插入的节点更新成祖父节点，依次往上更新，直到父节点为空或是父节点的颜色为黑色就停止。

2.如果叔叔节点存在，且叔叔节点是黑色的，那么此时就要判断新插入的节点在父节点的左还右，如果父节点，祖父节点，新插入的节点成一条线，那么此时就是单旋，然后旋转完成之后把父节点染成黑色，祖父节点染成红色。

3.如果叔叔节点存在，且为黑色，新插入节点与父节点，祖父节点形成折线，那么此时应该是双旋，旋转完成之后，把新插入的节点染成黑色，祖父节点染成红色。

4.如果叔叔节点不存在，那就看是上面的额那种情况，是那种旋转，找到对应的旋转就好了。

以上就是实现红黑树代码的具体细节。

AVL树和红黑树的对比：

其实AVL树和红黑树两个各有各的好处，是的，个人认为两个各有各的好处，因为AVL对树高比较严格，所以导致旋转点额次数就多，所以就会有额外的消耗，但是红黑树就没有这么多的消耗了，因为红黑树的上面几个规则，导致红黑树最长路径不得超过对短路径的两倍，所以，红黑树也会旋转，但是插入同等节点的条件下，红黑树旋转点次数肯定比AVL树少，但是AVL树是严格的logn，而红黑树是不太严格的logn，所以我说是各有各的好。

以上就是红黑树的规则讲解以及代码实现。希望大家能够多多支持！！谢谢！