红黑树的概念

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

红黑树的性质

1.每个结点不是红色就是黑色
2.根节点是黑色的
3.如果一个节点是红色的，则它的两个孩子结点是黑色的
4.对于每个结点，从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点
5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

enum Color
{RED, BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _color;RBTreeNode(const T& data = T(), Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_color(color){}
};

红黑树的迭代器

首先我们来看下红黑树中的迭代器应该是在什么位置

红黑树的结构中，有一个根节点，也有一个头节点，头节点是不负责存储数据的，而根节点才是常规意义上的二叉树的根节点，而红黑树中，begin()在头节点的左子树，也就是最左侧的节点（因为红黑树也是二叉平衡树），最左侧的节点就是最小的节点，end()在头节点的位置，因为如果对end()减减时，需要让迭代器走到最后一个节点的位置，也就意味着end应该指向最后一个节点的下一个位置。

首先，不关注红黑树节点中的值，因为作为迭代器，并不会对红黑树的结构进行修改，也就不会破坏红黑树，所以可以忽略红黑树的性质，只去关注它作为一棵二叉平衡树的特点。

核心的代码就变成了如何对迭代器实现Increment和Decrement操作，也就是加加减减操作

红黑树的插入

红黑树的插入实际上是分两个步骤的： 第一步，先用插入二叉搜索树的方式进行插入： 先拿到当前树的根节点，判断当前树是否为空
1.若为空，则创建一个根节点，作为头节点的parent，根节点和头节点互为parent
2.若不为空，从根节点开始，找待插入的节点位置
3.找到插入位置后，插入节点（默认的插入颜色是红色）
4.需要检测插入节点后，红黑树的性质是否被破坏了
5.检测完毕，并且进行修改
6.修改根节点的颜色，并且修改头节点的左右指向

对于步骤4是最重要的一步，因为涉及到红黑树的性质被破坏后，如何进行修改
我们可以分几种情况来进行讨论：
注意：cur为当前节点，p为父节点， g为祖父节点，u为叔叔节点

情况1.cur为红，p为红，g为黑，u存在且为红

那么就需要将p和u的颜色改为黑，同时将g的颜色改为红。
1.这时候就需要看g是否是根节点了，如果是根节点，只需要将根节点修改为黑即可。
2.如果g不是根节点，那么就需要继续向上判断，如果g的双亲是黑，也不需要进行任何修改，但是如果g的双亲是红，就违反了性质3，需要继续向上修改----->相当于将g作为cur，继续向上调整

情况2.cur为红，p为红，g为黑，u不存在/u存在且为黑

对于第一种：u不存在的情况

可以推断出，cur一定是新插入的节点，因为如果cur不是新插入的节点，那么cur和p一定要有一个是黑色，不然就违反了性质4
对于第二种：u存在的情况

u一定是黑色的，cur节点原来的颜色也是黑色的，现在看到是红色是由于cur的子树在调整时将cur的颜色由黑色改为红色了。

对于这两种场景的解决方案是：
p为g的左孩子，cur为p的左孩子，则进行右单旋；
p为g的右孩子，cur为p的右孩子，则进行左单旋。
旋转完成后，p变黑，g变红。

场景3：cur为红，p为红，g为黑，u不存在/u存在且为黑 和场景2相似，区别在于场景3中cur的位置，
如果p在g的左侧，cur在p的右侧，也就是内侧。
如果p在g的右侧，cur在p的左侧，也就是内侧。

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
通过这样的旋转之后，情况3就变成了情况2，再对情况2进行处理

当然，上述的三种情况是指parent在祖父节点的左，还有三种情况是可能在祖父节点的右。和上述的情况刚好相反。

红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($lo{g}_{2}N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的模拟实现

#pragma once#include <iostream>
using namespace std;
#include <functional>enum Color
{RED, BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _color;RBTreeNode(const T& data = T(), Color color = RED): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;
public:RBTreeIterator(Node* pNode = nullptr): _pNode(pNode){}// 具有指针类似的操作Ref operator*(){return _pNode->_data;}Ptr operator->(){return &(operator*());}// 能够移动Self& operator++(){Increment();return *this;}Self operator++(int){Self temp(*this);Increment();return temp;}Self& operator--(){Decrement();return *this;}Self operator--(int){Self temp(*this);Decrement();return temp;}// 迭代器可以比较bool operator!=(const Self& s)const{return _pNode != s._pNode;}bool operator==(const Self& s)const{return _pNode == s._pNode;}private:void Increment(){if (_pNode->_right){_pNode = _pNode->_right;while (_pNode->_left){_pNode = _pNode->_left;}}else{Node* parent = _pNode->_parent;while (_pNode == parent->_right){_pNode = parent;parent = _pNode->_parent;}// 注意特殊情况：根没有右孩子场景if(_pNode->_right != parent)_pNode = parent;}}void Decrement(){if (_pNode->_parent->_parent == _pNode && RED == _pNode->_color){_pNode = _pNode->_right;}else if (_pNode->_left){_pNode = _pNode->_left;while (_pNode->_right){_pNode = _pNode->_right;}}else{Node* parent = _pNode->_parent;while (_pNode == parent->_left){_pNode = parent;parent = _pNode->_parent;}_pNode = parent;}}
private:Node* _pNode;
};// 假设：key唯一
template<class T, class KOFD, class Compare = less<T>>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T&, T*> iterator;public:RBTree(): _size(0){_head = new Node();_head->_left = _head;_head->_right = _head;}~RBTree(){_DestroyRBTree(GetRoot());delete _head;_head = nullptr;}iterator begin(){return iterator(_head->_left);}iterator end(){return iterator(_head);}pair<iterator, bool> Insert(const T& data){// 1. 二叉搜索树// 按照二叉搜索树的规则插入新节点// 空树Node*& root = GetRoot();Node* newNode = nullptr;if (nullptr == root){newNode = root = new Node(data, BLACK);root->_parent = _head;}else{// 非空：// 找待插入节点在红黑树中的位置并保存其双亲Node* cur = root;Node* parent = _head;KOFD kofD;while (cur){parent = cur;if (_com(kofD(data), kofD(cur->_data)))cur = cur->_left;else if (_com(kofD(cur->_data), kofD(data)))cur = cur->_right;elsereturn make_pair(iterator(cur), false);}// 插入新节点newNode = cur = new Node(data);if (_com(kofD(data), kofD(parent->_data)))parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;// 2. 节点添加颜色 + 性质约束平衡性// 检测新节点插入后，红黑树的性质是否造到破坏while (_head != parent && RED == parent->_color){// 违反性质三Node* grandFather = parent->_parent;if (parent == grandFather->_left){// 课件中的三个场景：Node* uncle = grandFather->_right;if (uncle && RED == uncle->_color){// 情况一：叔叔节点存在且为红parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;cur = grandFather;parent = cur->_parent;}else{// 叔叔节点不存在 || 叔叔节点存在且为黑// 情况二和情况三if (cur == parent->_right){// 情况三RotateLeft(parent);std::swap(cur, parent);}// 情况二parent->_color = BLACK;grandFather->_color = RED;RotateRight(grandFather);}}else{// 课件中三个场景的反情况：Node* uncle = grandFather->_left;if (uncle && RED == uncle->_color){parent->_color = BLACK;uncle->_color = BLACK;grandFather->_color = RED;cur = grandFather;parent = cur->_parent;}else{if (cur == parent->_left){RotateRight(parent);std::swap(cur, parent);}parent->_color = BLACK;grandFather->_color = RED;RotateLeft(grandFather);}}}}root->_color = BLACK;_head->_left = MostLeft();_head->_right = MostRight();++_size;return make_pair(iterator(newNode), true);}size_t Size()const{return _size;}bool Empty()const{return 0 == _size;}void Clear(){_DestroyRBTree(GetRoot());_head->_left = _head;_head->_right = _head;_size = 0;}void Swap(RBTree<T, KOFD, Compare>& t){std::swap(_head, t._head);std::swap(_size, t._size);std::swap(_com, t._com);}void InOrder(){cout << "中序遍历: ";_InOrder(GetRoot());cout << endl;}iterator Find(const T& data){Node* cur = GetRoot();KOFD kofD;while (cur){if (_com(kofD(data), kofD(cur->_data)))cur = cur->_left;else if (_com(kofD(cur->_data), kofD(data)))cur = cur->_right;elsereturn iterator(cur);}return end();}bool IsVAlidTree(){Node* root = GetRoot();if (nullptr == root)return true;if (root->_color == RED){cout << "违反性质2：根是红色的" << endl;return false;}// 获取单条路径中黑色节点的个数size_t blackCount = 0;Node* cur = root;while (cur){if (BLACK == cur->_color)blackCount++;cur = cur->_left;}// 递归检测性质4return IsVAlidTree(root, blackCount, 0);}private:bool IsVAlidTree(Node* root, const size_t blackCount, size_t pathBlackCount){if (nullptr == root)return true;Node* parent = root->_parent;if (parent != _head && (RED == root->_color && RED == parent->_color)){cout << "违反了性质三：存在连在一起的红色节点!!!" << endl;return false;}if (BLACK == root->_color)pathBlackCount++;if (nullptr == root->_left && nullptr == root->_right){if (pathBlackCount != blackCount){cout << "违反了性质4：路径中黑色节点个数不一样!!!" << endl;return false;}}return IsVAlidTree(root->_left, blackCount, pathBlackCount) &&IsVAlidTree(root->_right, blackCount, pathBlackCount);}void RotateLeft(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;// 注意：右单支if (subRL)subRL = subRL->_parent = parent;subR->_left = parent;// 更新subR和parent的双亲Node* pparent = parent->_parent;parent->_parent = subR;subR->_parent = pparent;// 需要向上考虑pparentif (_head == pparent)GetRoot() = subR;else{if (parent == pparent->_left)pparent->_left = subR;elsepparent->_right = subR;}}void RotateRight(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;// 左单支if (subLR)subLR->_parent = parent;subL->_right = parent;// 更新suL和parent的双亲Node* pparent = parent->_parent;subL->_parent = pparent;parent->_parent = subL;// 向上考虑pparent的情况if (_head == pparent)GetRoot() = subL;else{if (parent == pparent->_left)pparent->_left = subL;elsepparent->_right = subL;}}void _DestroyRBTree(Node*& root){if (root){_DestroyRBTree(root->_left);_DestroyRBTree(root->_right);delete root;root = nullptr;}}void _InOrder(Node* root){if (root){_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}}Node*& GetRoot(){return _head->_parent;}Node* MostLeft(){Node* root = GetRoot();if (nullptr == root)return _head;Node* cur = root;while (cur->_left){cur = cur->_left;}return cur;}Node* MostRight(){Node* root = GetRoot();if (nullptr == root)return _head;Node* cur = root;while (cur->_right){cur = cur->_right;}return cur;}private:Node* _head;size_t _size;Compare _com;
};