线上怎么做推广,seo短视频永久入口运营,企业图标设计图案大全,5g影视文章目录 红黑树的概念红黑树的性质红黑树的模拟实现红黑树的平衡问题 整体实现和测试 本篇用于进行红黑树的拆解和模拟实现#xff0c;为之后的map和set的封装奠定基础
红黑树的概念
红黑树也是一种二叉搜索树#xff0c;但是在每一个节点的内部新增了一个用以表示该节点颜… 文章目录 红黑树的概念红黑树的性质红黑树的模拟实现红黑树的平衡问题 整体实现和测试 本篇用于进行红黑树的拆解和模拟实现为之后的map和set的封装奠定基础
红黑树的概念
红黑树也是一种二叉搜索树但是在每一个节点的内部新增了一个用以表示该节点颜色的值有黑色和红色两种通过对任何一条从根到叶子的路径上的各个节点着色方式的限制红黑树可以保证没有一条路径可以比其他路径长出两倍因此是平衡的
红黑树的基本模式如下图所示
红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么红黑树具有最长路径中节点的个数不超过最短路径个数的2倍
其实原因在于红黑树的性质在红黑树中可以存在两个相同黑色节点连在一起但是绝对不会存在两个连在一起的红色节点并且每个路径上的黑色节点数量是相同的基于这两点原因在红黑树中最长的路径不过是一个红节点穿插一个黑节点…而最短的路径就是所有黑节点是一个接着一个基于这样的原因就可以保证上面的性质了
红黑树的模拟实现
基本的定义
enum Color
{RED,BLEAK
};templateclass K, class V
struct BSTreeNode
{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;BSTreeNodeK, V* _parent;pairK, V _kv;Color _col;BSTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};为什么这里在定义信息的时候默认值使用的是RED
由于红黑树的性质可以知道一条路径中的黑节点的数量是确定的当插入的是一个红色节点时最多会影响的是当前路径的信息但是如果插入的是一个黑色节点那么势必会引起整个树中所有完整的路径中的异常会破坏红黑树中的平衡
红黑树的平衡问题
在插入新节点后红黑树的平衡可能会受到破坏下面分情况来进行讨论
定义当前节点为cur父亲节点为parent祖父节点为grandparent叔叔节点为uncle而红黑树的插入问题重点看叔叔
1. 如果双亲节点是黑色 最简单的一种情况不需要做任何处理只需要插入即可
2. cur为红色parent为红色grandfather为黑色uncle存在并且是红色 此时出现了两个红色节点相继出现的情况这种情况是不被允许的因此要做出调整把parent和uncle都改成黑色同时将grandfather改成红色
此时需要继续进行情况讨论如果grandfather是根节点那么就意味着此时调整已经完毕了不需要再进行调整因此把根节点置为黑色而如果grandfather不为根节点并且上面一个节点还是红色那么此时又有两个红色节点相继出现了此时就需要继续进行调整把grandfather当成cur然后进行调整即可 3. cur为红色parent为红色grandfather为黑色uncle不存在或者是黑色
根据uncle的情况来进行分析
如果uncle节点不存在那么就说明cur一定是新插入的节点这是因为路径下的黑色节点必定要相同此时又有两种情况可能插入在parent的左右两边 如果uncle节点存在并且是黑色那么就意味着cur节点一定是黑的现在体现为红色是因为cur子树在调整的过程中把cur的节点变成红色了如果cur是新插入节点那么红黑树原来就是错的因为下面的场景不存在 所以一定是这样的情景 而此时cur并不是新插入的节点新插入节点是cur的左右子树中的一个现在体现为红色是因为下面子树的调整把cur变成红色了它原来是黑色的
那么此时就要进行旋转了令grandparent右旋即可完成降高度的效果再进行变色即可 因此将上述的过程都综合起来就可以完成代码的实现了 bool insert(const pairK, V kv){Node* cur _root;Node* parent nullptr;// 根据搜索二叉树的基本逻辑完成if (_root nullptr){_root new Node(kv);}else{// 插入数据while (cur){if (cur-_kv.second kv.second){// 插入元素小于当前节点元素插入到左边parent cur;cur cur-_left;}else if (cur-_kv.second kv.second){// 插入元素大于当前节点元素插入到右边parent cur;cur cur-_right;}else{return false;}}// 此时parent指向最后一个节点cur为空cur new Node(kv);if (parent-_kv.second cur-_kv.second){// 如果插入节点小于它的父亲就插入到左边parent-_left cur;cur-_parent parent;}else if (parent-_kv.second cur-_kv.second){// 如果插入节点大于它的父亲就插入到右边parent-_right cur;cur-_parent parent;}else{return false;}}// 至此普通二叉搜索树的插入已经完成该进行红黑树的高度调整了// 终止条件是parent为空或者parent已经是黑色了就意味着不需要调整了// parent是红色意味着grandparent一定存在while (parent parent-_col RED){// 更变的核心是舅舅因此要先找到舅舅// 整体来说还有两种情况parent可能是grandparent的左或者右舅舅就是另外一边Node* grandparent parent-_parent;if (parent grandparent-_left){Node* uncle grandparent-_right;// 1. 舅舅存在并且是红色if (uncle uncle-_col RED){// g// p u// c// 变色parent-_col uncle-_col BLACK;grandparent-_col RED;// 向上处理cur grandparent;parent cur-_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur parent-_left){// g// p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur-_col grandparent-_col RED;parent-_col BLACK;}// 如果cur是右孩子else{// g g// p -- c -- c// c p p g// 对parent左旋对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur-_col BLACK;parent-_col grandparent-_col RED;}// 更新之后parent和grandparent顺序乱了而且也不需要继续调整了直接breakbreak;}}// parent是grandparent的右孩子相同的逻辑再进行一次else{Node* uncle grandparent-_left;if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandparent-_col RED;// 继续往上处理cur grandparent;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else{// g// p // cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}// 不管上面怎么变都无所谓只需要保证根节点是黑的就可以了_root-_col BLACK;return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}}整体实现和测试
enum Color
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree():_root(nullptr){}bool insert(const pairK, V kv){Node* cur _root;Node* parent nullptr;// 根据搜索二叉树的基本逻辑完成if (_root nullptr){_root new Node(kv);}else{// 插入数据while (cur){if (cur-_kv.second kv.second){// 插入元素小于当前节点元素插入到左边parent cur;cur cur-_left;}else if (cur-_kv.second kv.second){// 插入元素大于当前节点元素插入到右边parent cur;cur cur-_right;}else{return false;}}// 此时parent指向最后一个节点cur为空cur new Node(kv);if (parent-_kv.second cur-_kv.second){// 如果插入节点小于它的父亲就插入到左边parent-_left cur;cur-_parent parent;}else if (parent-_kv.second cur-_kv.second){// 如果插入节点大于它的父亲就插入到右边parent-_right cur;cur-_parent parent;}else{return false;}}// 至此普通二叉搜索树的插入已经完成该进行红黑树的高度调整了// 终止条件是parent为空或者parent已经是黑色了就意味着不需要调整了// parent是红色意味着grandparent一定存在while (parent parent-_col RED){// 更变的核心是舅舅因此要先找到舅舅// 整体来说还有两种情况parent可能是grandparent的左或者右舅舅就是另外一边Node* grandparent parent-_parent;if (parent grandparent-_left){Node* uncle grandparent-_right;// 1. 舅舅存在并且是红色if (uncle uncle-_col RED){// g// p u// c// 变色parent-_col uncle-_col BLACK;grandparent-_col RED;// 向上处理cur grandparent;parent cur-_parent;}// 2. 舅舅不存在else{// 如果cur是左孩子if (cur parent-_left){// g// p// c// 对grandparent进行右旋RotateR(grandparent);// 变色cur-_col grandparent-_col RED;parent-_col BLACK;}// 如果cur是右孩子else{// g g// p -- c -- c// c p p g// 对parent左旋对grandparent右旋RotateL(parent);RotateR(grandparent);// 变色cur-_col BLACK;parent-_col grandparent-_col RED;}// 更新之后parent和grandparent顺序乱了而且也不需要继续调整了直接breakbreak;}}// parent是grandparent的右孩子相同的逻辑再进行一次else{Node* uncle grandparent-_left;if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandparent-_col RED;// 继续往上处理cur grandparent;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else{// g// p // cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}// 不管上面怎么变都无所谓只需要保证根节点是黑的就可以了_root-_col BLACK;return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}}void inorder(){_inorder(_root);cout endl;}bool isbalance(){return _isbalance(_root);}private:bool _check(Node* root, int blacknum, const int RefVal){// 判断黑色路径数量是否相等if (root nullptr){if (blacknum ! RefVal){cout 黑色节点数量不相等 endl;return false;}return true;}// 判断是否有连续的红色节点if (root-_col RED root-_parent-_col RED){cout 有连续的红色节点 endl;return false;}if (root-_col BLACK){blacknum;}return _check(root-_left, blacknum, RefVal) _check(root-_right, blacknum, RefVal);}// 判断红黑树是否平衡bool _isbalance(Node* root){// 如果根节点是红的说明错了if (root-_col RED){cout 根节点是红色 endl;return false;}// 统计一下路径中有多少黑色节点int RefVal 0;Node* cur root;while (cur){if (cur-_col BLACK)RefVal;cur cur-_left;}// 判断路径中的黑色节点是否相等return _check(root, 0, RefVal);}void _inorder(Node* root){if (root nullptr)return;_inorder(root-_left);cout root-_kv.second ;_inorder(root-_right);}Node* _root nullptr;
};int main()
{const int N 100000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);}RBTreeint, int t;for (auto e : v){cout Insert: e -;t.insert(make_pair(e, e));cout t.isbalance() endl;}cout t.isbalance() endl;return 0;
}
