【C++练级之路】【Lv.16】红黑树(冰与火的碰撞,红与黑的史诗)
时间:2024-03-27 17:55:44 来源:网络cs 作者:璐璐 栏目:监控软件 阅读:
文章目录
引言一、红黑树的概念二、红黑树的模拟实现2.1 结点2.2 成员变量2.3 插入情况一:uncle在左,parent在右==如果uncle存在且为红色==:==如果uncle不存在,或者存在且为黑色==: 情况二:parent在左,uncle在右==如果uncle存在且为红色==:==如果uncle不存在,或者存在且为黑色==: 三、红黑树的验证四、红黑树的性能4.1 优势4.2 适用场景
引言
之前学习的AVL树,是一种平衡二叉搜索树,它追求绝对平衡,从而导致插入和删除性能较差。而今天学习的红黑树,是另一种平衡二叉搜索树,它追求相对平衡,使得增删查改的性能都极佳,时间复杂度皆为O(log2N),是数据结构中的精华,天才般的设想!
一、红黑树的概念
红黑树,顾名思义,其节点有红和黑两种颜色。
之所以新增结点颜色的标记,是因为通过结点着色方式的限制,能够让红黑树的最长路径不超过最短路径的两倍,以保证相对平衡。
红黑树满足五条性质:
所有结点非黑即红根结点为黑色NIL结点为黑色红色结点的子结点必为黑色任意结点到其叶子NIL结点的所有路径,都包含相同的黑色结点在红黑树中,NIL节点(也称为空节点)是叶子节点的一种特殊表示。它们不是实际存储数据的节点,而是树结构中的占位符,用于定义树的边界。所有的红黑树都以NIL节点为叶子节点,这些NIL节点在视觉上通常不被画出来。
性质解读:
性质4:表明不能有连续的红色结点性质4+性质5: 理论最短路径:全为黑色结点理论最长路径:红黑相间这样,就保证了最长路径不超过最短路径的两倍。
二、红黑树的模拟实现
2.1 结点
enum Color{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;Color _col;RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}};
细节:
使用三叉链,增加了指向parent的指针使用KV模型,数据存储键值对pair结点储存颜色,同时颜色使用枚举结点的颜色初始化为红色说明:为什么结点的颜色初始化为红色呢?因为插入新节点时(不为根部),如果插入黑色,就会直接破坏性质5,导致每条路径黑结点数目不同;而如果插入红色,有可能不会破坏性质4,所以结点初始化为红色更优。
2.2 成员变量
template<class K, class V>class RBTree{protected:typedef RBTreeNode<K, V> Node;public:protected:Node* _root = nullptr;};
2.3 插入
因为红黑树也是二叉搜索树,所以默认成员函数和遍历与之前写的没什么不同,这里重点讲解红黑树的插入。
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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_right == parent)//uncle在左,parent在右{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED)//uncle为红,变色+向上调整{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle为空或为黑,变色+旋转{if (parent->_right == cur)//左单旋{RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//右左旋{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}else//parent在左,uncle在右{Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur)//右单旋{RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//左右旋{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}}_root->_col = BLACK;return true;}
思路:
以二叉搜索树的方式正常插入讨论并调整结点的颜色,以及调整结构,使之满足红黑树的性质循环条件:while (parent && parent->_col == RED)
保证了parent存在且为红,grandparent存在且为黑
情况一:uncle在左,parent在右
如果uncle存在且为红色:
处理方法:
将parent和uncle变黑,grandparent变红cur = grandparent,parent = cur->_parent,继续向上调整防止grandparent为根节点却变红,在循环结束后将根节点变为黑色如果uncle不存在,或者存在且为黑色:
当cur在右部外侧时:
处理方法:
当cur在右部内侧时:
处理方法:
先对parent进行右单旋再对grandparent进行左单旋最后将cur变黑,grandparent变红情况二:parent在左,uncle在右
如果uncle存在且为红色:
处理方法:
将parent和uncle变黑,grandparent变红cur = grandparent,parent = cur->_parent,继续向上调整防止grandparent为根节点却变红,在循环结束后将根节点变为黑色如果uncle不存在,或者存在且为黑色:
当cur在左部外侧时:
处理方法:
当cur在左部内侧时:
处理方法:
先对parent进行左单旋再对grandparent进行右单旋最后将cur变黑,grandparent变红红黑树插入的核心口诀:uncle存在且为红,变色+向上调整,uncle不存在或为黑,变色+旋转
附上旋转的实现:
void RotateL(Node* parent){Node* grandparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subR;}else{grandparent->_left = subR;}}else{_root = subR;}subR->_parent = grandparent;}void RotateR(Node* parent){Node* grandparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subL;}else{grandparent->_left = subL;}}else{_root = subL;}subL->_parent = grandparent;}
三、红黑树的验证
bool IsBalance(){if (_root && _root->_col == RED){cout << "根结点为红色" << endl;return false;}int benchMark = 0;//基准值Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchMark;}cur = cur->_right;}return Check(_root, 0, benchMark);}bool Check(Node* root, int blackNum, int benchMark){if (root == nullptr){if (blackNum != benchMark){cout << "某条路径黑色结点数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "存在连续的红色结点" << endl;return false;}return Check(root->_left, blackNum, benchMark)&& Check(root->_right, blackNum, benchMark);}
细节:
验证根节点是否为黑先计算出一条路径的黑色结点个数作为基准值,再在递归中比较每条路径的黑色结点是否相等若该节点为红,检测其parent是否为红,判断是否存在连续的红色节点四、红黑树的性能
4.1 优势
红黑树是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对AVL树而言,降低了插入和旋转的次数。
4.2 适用场景
因此,在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。
本文链接:https://www.kjpai.cn/news/2024-03-27/149653.html,文章来源:网络cs,作者:璐璐,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!
上一篇:已解决java.lang.NoClassDefFoundError异常的正确解决方法,亲测有效!!!已解决java.lang.NoClassDefFoundError异常的正确解决方法,亲测有效!!!
下一篇:返回列表