文章目录
- 一、红黑树的概念
- 二、红黑树的性质
- 三、红黑树节点的定义
- 四、红黑树的插入操作
- 五、红黑树的验证
- 五、红黑树的删除
- 六、红黑树与AVL树的比较
- 七、红黑树的应用
- 八、红黑树模拟实现
一、红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
二、红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的,即树中没有连续的红色节点
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点,即每条路径的黑色节点数量相等
- 每个叶子结点(这里的叶子结点指的是空结点,也叫做NIL节点 )都是黑色的
红黑树中第三和第四条规则构成互斥,极限的最短一定是全黑,极限的最长一定是一黑一红 。
三、红黑树节点的定义
enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pair<K, V> _kv; //节点的值域Colour _col; //节点的颜色RBTreeNode<K, V>* _left; //节点的左孩子RBTreeNode<K, V>* _right; //节点的右孩子RBTreeNode<K, V>* _parent; //节点的双亲
};
四、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:一、按照二叉搜索的树规则插入新节点。二、检测新节点插入后,红黑树的性质是否造到破坏。
因为新节点的默认颜色是红色,如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三(不能有连续的红色节点),此时需要对红黑树分情况来讨论。
情况一: cur为红,p为红,g为黑,u存在且为红
cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点。此处看到的树,可能是一颗完整的树,但是也有可能是一颗子树。
解决方式是将将p,u改为黑,g改为红。继续把g当成cur,g是根节点,需要将g改为黑色,如果g是子树且g的双亲颜色为红色,则需要继续向上调整。
情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑
如果u节点不存在,那么cur一定为新插入的节点,否则就违反性质4。如果u节点存在,则一定是黑色的,cur之前也是黑色的,因为新增节点是a、b节点,所以现在它是红色。
解决方式:如果p为g的左孩子,cur为p的左孩子,则进行右单旋转;p为g的右孩子,cur为p的右孩子,则进行左单旋转。然后再将p变黑,g变红。
情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑
解决方式:如果p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;如果p为g的右孩子,cur为p的左孩子,则针对p做右单旋转。旋转后就转变为了情况二。
总结
在这三种情况中,都有cur为红,p为红,g为黑
,可以看出红黑树的关键是叔叔。U存在且为红则变色继续往上处理,U不存在或为黑,则旋转加变色。
情况二和情况三的主要区别是单旋和双旋的不同。从图中可以看出,当p g cur为一条直线的时候,也就是情况二,单旋即可;p g cur 为一条折线的时候,也就是情况三,需要双旋。
代码实现
bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur) //找插入位置{if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//新节点的默认颜色是红色,因为如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);// 关键看叔叔if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情况一 : uncle存在且为红,变色+继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}// 情况二+三:uncle不存在 + 存在且为黑else{// 情况二:右单旋+变色// g // p u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:左右单旋+变色// g // p u// cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;// 情况一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}else{// 情况二:左单旋+变色// g // u p// cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:右左单旋+变色// g // u p// cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;
}
五、红黑树的验证
红黑树的检测分为两步:一、检测其是否满足二叉搜索树,这里只需要中序遍历是否为有序序列即可。二、检测其是否满足红黑树的性质。
public:bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}int benchmark = 0;return PrevCheck(_root, 0, benchmark);}
private:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}
五、红黑树的删除
红黑树的删除过于复杂,可以参考 红黑树的删除 这篇博客
六、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log2Nlog_2 Nlog2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。
七、红黑树的应用
红黑树的应用场景建议观看这个视频讲解红黑树在linux中的3种应用场景
八、红黑树模拟实现
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pair<K, V> _kv;Colour _col;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;
};template<class K, class V>
struct RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur) //找插入位置{if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);//新节点的默认颜色是红色,因为如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);// 关键看叔叔if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情况一 : uncle存在且为红,变色+继续往上处理if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}// 情况二+三:uncle不存在 + 存在且为黑else{// 情况二:右单旋+变色// g // p u// cif (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:左右单旋+变色// g // p u// cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;// 情况一if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;// 继续往上处理cur = grandfater;parent = cur->_parent;}else{// 情况二:左单旋+变色// g // u p// cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三:右左单旋+变色// g // u p// cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}// 黑色节点数量基准值int benchmark = 0;return PrevCheck(_root, 0, benchmark);}private:bool PrevCheck(Node* root, int blackNum, int& benchmark){if (root == nullptr){if (benchmark == 0){benchmark = blackNum;return true;}if (blackNum != benchmark){cout << "某条黑色节点的数量不相等" << endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}
private:Node* _root = nullptr;
};