【红黑树】

红黑树

小杨

红黑树的概念

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

红黑树的性质

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

实际的红黑树，最长和最短并不一定存在。红黑树最短路径:h(全黑),最长路径:2*h(一黑一红).

最短路径*2>=最长路径
就查找而言，最短路径:logN,最长路径:2*logN.

红黑树节点定义

//枚举定义结点的颜色
enum Colour
{RED,BLACK
};//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{//三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//存储的键值对pair<K, V> _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏

我们默认新节点默认颜色为红色(主动破坏红黑树的性质3),如果新节点默认是黑色(那就相当于破换了性质4),破坏性质3比较好控制一点.

分析种数情况:以下图这棵树为例子:

如果cur不是新增节点：若cde具有每条路径都只有一个黑色节点，那就是有3种情况.

因此cde的组合情况有333=27种。
cur只能为x的情况，此时新增的红色节点有4种插入情况(新增节点一定是在a、b
的下面)。样例为下图:

如果cde具有2个黑色节点?估计得上万。

接下来看红黑树性质遭到破坏如何调整?
注意:我们看到的树，可能是一棵完整的树，也可能是一棵子树。
情况一:cur为红，p为红，g为黑，u存在且为红

此时cur为新增，如果如果p为黑，那么就结束了，若p也为红，那么就需要调整了，红黑树其实就是先尽量调整颜色，实在不行的话就进行旋转。但是调整颜色的话主要看的是u，而根据u可以分成两种情况。1.u存在且为红；2.u不存在或者u存在且为黑。
调整后如下图：

如果g是根节点，调整完成后，需要将g改成黑色。
如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整。

对为什么要继续进行向上调整的解释:

情况二:cur为红，p为红，g为黑，u不存在/u存在且为黑

说明:u的情况有两种

1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足红黑树性质4:每条路径黑色节点个数相同。
2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到上图左其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色有黑色改成红色。
   p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
   p为g的右孩子，cur为p的右孩子，则进行左单旋转
   p、g变色–p变黑，g变红

情况三:cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2

红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

bool IsValidRBTree()
{PNode pRoot = GetRoot();// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_color){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;PNode pCur = pRoot;while (pCur){if (BLACK == pCur->_color)blackCount++;pCur = pCur->_pLeft;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_color)k++;// 检测当前节点与其双亲是否都为红色PNode pParent = pRoot->_pParent;if (pParent && RED == pParent->_color && RED == pRoot->_color){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&_IsValidRBTree(pRoot->_pRight, k, blackCount);
}

红黑树与AVL树的比较

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

红黑树的应用

1. C++ STL库 – map/set、mutil_map/mutil_set
2. Java 库
3. linux内核
4. 其他一些库

红黑树实现代码:

//枚举定义结点的颜色
enum Colour
{RED,BLACK
};//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{//三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//存储的键值对pair<K, V> _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};//红黑树的实现
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://构造函数RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTree<K, V>& t){_root = _Copy(t._root, nullptr);}//赋值运算符重载（现代写法）RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}//析构函数~RBTree(){_Destroy(_root);_root = nullptr;}//查找函数Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_kv.first) //key值小于该结点的值{cur = cur->_left; //在该结点的左子树当中查找}else if (key > cur->_kv.first) //key值大于该结点的值{cur = cur->_right; //在该结点的右子树当中查找}else //找到了目标结点{return cur; //返回该结点}}return nullptr; //查找失败}//插入函数pair<Node*, bool> Insert(const pair<K, V>& kv){if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点{_root = new Node(kv);_root->_col = BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索树的插入方法，找到待插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //待插入结点的key值等于当前结点的key值{return make_pair(cur, false); //插入失败}}//2、将待插入结点插入到树中cur = new Node(kv); //根据所给值构造一个结点Node* newnode = cur; //记录新插入的结点（便于后序返回）if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent->_left = cur;cur->_parent = parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent->_right = cur;cur->_parent = parent;}//3、若插入结点的父结点是红色的，则需要对红黑树进行调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在if (parent == grandfather->_left) //parent是grandfather的左孩子{Node* uncle = grandfather->_right; //uncle是grandfather的右孩子if (uncle && uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateR(grandfather); //右单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}else //cur == parent->_right{RotateLR(grandfather); //左右双旋//颜色调整grandfather->_col = RED;cur->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle = grandfather->_left; //uncle是grandfather的左孩子if (uncle && uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateRL(grandfather); //右左双旋//颜色调整cur->_col = BLACK;grandfather->_col = RED;}else //cur == parent->_right{RotateL(grandfather); //左单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}}_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）return make_pair(newnode, true); //插入成功}private://拷贝树Node* _Copy(Node* root, Node* parent){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_data);copyNode->_parent = parent;copyNode->_left = _Copy(root->_left, copyNode);copyNode->_right = _Copy(root->_right, copyNode);return copyNode;}//析构函数子函数void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;//建立subRL与parent之间的联系parent->_right = subRL;if (subRL)subRL->_parent = parent;//建立parent与subR之间的联系subR->_left = parent;parent->_parent = subR;//建立subR与parentParent之间的联系if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;//建立subLR与parent之间的联系parent->_left = subLR;if (subLR)subLR->_parent = parent;//建立parent与subL之间的联系subL->_right = parent;parent->_parent = subL;//建立subL与parentParent之间的联系if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左右双旋void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}//右左双旋void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}Node* _root; //红黑树的根结点
};