国外建站数据,小城镇建设官方网站,网络营销推广的目标与策略,可以做软件的网站有哪些功能吗✅1主页#xff1a;我的代码爱吃辣#x1f4c3;2知识讲解#xff1a;数据结构——红黑树☂️3开发环境#xff1a;Visual Studio 2022#x1f4ac;4前言#xff1a;红黑树也是一颗二叉搜索树#xff0c;其作为map#xff0c;set的底层… ✅1主页我的代码爱吃辣2知识讲解数据结构——红黑树☂️3开发环境Visual Studio 20224前言红黑树也是一颗二叉搜索树其作为mapset的底层容器具有非常好的搜索性能仅仅通过控制颜色和位置就能达到一种近似平衡的效果大大减少了旋转的次数。 目录
一.红黑树的概念
二. 红黑树的性质
三.红黑树节点及其整体的定义
四.红黑树的插入操作
五.红黑树 find
六.析构函数
七.红黑树的验证
八. 红黑树与AVL树的比较 一.红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 二. 红黑树的性质
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)NIL结点 思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 答案因为性质3限制了一条路径上不可能出现连续的两个红色结点。又因为性质4每条路径上黑色结点数目相同那么最短路径就一定是全是黑色结点的路径最长路径一定是红黑交错的路径因为根节点一定是黑色那么最长路径上红黑结点树一定是相等的所以最长路径最多是最短路径的两倍。 三.红黑树节点及其整体的定义
//枚举
enum Color
{RED,//红色BLACK//黑色
};
templateclass K,class V
struct _RBTreeNode
{_RBTreeNode(pairK,V kv):_kv(kv),_col(RED),//默认红色_left(nullptr),_right(nullptr),_parent(nullptr){}pairK, V _kv; //存储数值Color _col; //颜色_RBTreeNodeK, V* _left; //左孩子_RBTreeNodeK, V* _right; //右孩子_RBTreeNodeK, V* _parent; //父亲
};
#pragma once
#includeiostream
using namespace std;templateclass K,class V
class RBTRee
{typedef _RBTreeNodeK, V Node;//结点
public:Node* find(const K key){//....}bool insert(pairK, V kv){//....}void Inorder(){//...}~RBTRee(){//...}private:Node* _root nullptr;//根节点
}; 思考在节点的定义中为什么要将节点的默认颜色给成红色的 答案新创建的结点妖色要么红色要么黑色除了颜色区别之外就是在插入时对整个树的影响不同如果插入的是黑色会影响整颗树所有路径上的黑色结点说就会不同必然违反性质4。如果插入的是红色结点仅仅是局部的影响可能会影响性质3一定不会影响性质4。 四.红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索的树规则插入新节点。
bool insert(pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;}}//找到了合适的位置cur new Node(kv);if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//....
}
因为性质2所以我们每一次插入数据都想根节点变成黑色。
2.检测新节点插入后红黑树的性质是否造到破坏若满足直接退出否则对红黑树进行旋转着色处理。
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点。
情况一 cur为红p为红g为黑u存在且为红 解决方式将 p , u 改为黑g 改为红然后把 g 当成 cur继续向上调整。 情况二: cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的左孩子则进行右单旋转相反p、g变色--p变黑g变红
情况三cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的右孩子则针对p做左单旋转 p为g的左孩子cur为p的左孩子则进行右单旋转相反p、g变色--p变黑g变红
这里的cur的也有可能是新增的结点如果是cur本身就是新增节点那么u结点就是不存在的否则违反规则 4也有可能是因为cur下面的结点变黑导致 cur 变红色。 代码 while (parent parent-_col RED){Node* grandfather parent-_parent;// g(B) g(R)// p(R) u(R) -- p(B) u(B)//c(R) c(R)if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //u不存在/u存在且为黑旋转变色{// g(B) p(R)// p(R) u(B) -- u(B) g(B)//c(R) u(B)if (cur parent-_left){//右单旋RotateR(grandfather);parent-_col BLACK;//cur-_col RED;grandfather-_col RED;}else{// g(B) P(B) // p(R) u(B) -- c(R) g(R)// c(R) u(B)// 左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else //grandfather-_right parent,与上述情况相反{Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //u不存在/u存在且为黑旋转变色{if (cur parent-_right){//左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// 右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}} 旋转 void RotateL(Node* parent){Node* curR parent-_right;Node* curRL curR-_left;//调整结点并且修改其父亲结点指针parent-_right curRL;if (curRL)//可能为空{curRL-_parent parent;}//在修改子树根节点之前保存子树根节点的父亲Node* pparent parent-_parent;//修改子树根节点curR-_left parent;parent-_parent curR;//子树根节点有可能是整棵树的根节点if (pparent nullptr){_root curR;_root-_parent nullptr;}else//子树根节点不是整棵树的根节点{//还要看子树是它父亲的左孩子还是右孩子if (pparent-_left parent){pparent-_left curR;}else{pparent-_right curR;}curR-_parent pparent;}}void RotateR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;parent-_left curLR;if (curLR){curLR-_parent parent;}Node* pparent parent-_parent;curL-_right parent;parent-_parent curL;if (parent _root){_root curL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left curL;}else{pparent-_right curL;}curL-_parent pparent;}}
红黑树顺序插入 红黑树随机插入 五.红黑树 find
根据二叉搜索树特性去查找 Node* find(const K key){Node* cur _root;while (cur){if (key cur-_kv.first){cur cur-_left;}else if (key cur-_kv.first){cur cur-_right;}else{return cur;}}return nullptr;}
六.析构函数
后续遍历析构树 ~RBTRee(){_Destrory(_root);_root nullptr;}void _Destrory(Node* root){if (root nullptr){return;}_Destrory(root-_left);_Destrory(root-_right);delete root;} 七.红黑树的验证
红黑树的检测分为两步
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质 其中是否满足搜索树我们只要对其中序遍历是否有序即可。 完整代码
#pragma once
#includeiostream
using namespace std;enum Color
{RED,BLACK
};
templateclass K,class V
struct _RBTreeNode
{_RBTreeNode(pairK,V kv):_kv(kv),_col(RED),_left(nullptr),_right(nullptr),_parent(nullptr){}pairK, V _kv;Color _col;_RBTreeNodeK, V* _left;_RBTreeNodeK, V* _right;_RBTreeNodeK, V* _parent;
};templateclass K,class V
class RBTRee
{typedef _RBTreeNodeK, V Node;
public:Node* find(const K key){Node* cur _root;while (cur){if (key cur-_kv.first){cur cur-_left;}else if (key cur-_kv.first){cur cur-_right;}else{return cur;}}return nullptr;}bool insert(pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(kv);//找到了合适的位置if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while ( parent parent-_col RED){Node* grandfather parent-_parent;// g(B) g(R)// p(R) u(R) -- p(B) u(B)//c(R) c(R)if ( grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //u不存在/u存在且为黑旋转变色{// g(B) p(R)// p(R) u(B) -- u(B) g(B)//c(R) u(B)if (cur parent-_left){//右单旋RotateR(grandfather);parent-_col BLACK;//cur-_col RED;grandfather-_col RED;}else{// g(B) P(B) // p(R) u(B) -- c(R) g(R)// c(R) u(B)// 左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else //grandfather-_right parent,与上述情况相反{Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else //u不存在/u存在且为黑旋转变色{if (cur parent-_right){//左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// 右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void Inorder(vectorK v){_inorder(_root,v);cout endl;}~RBTRee(){_Destrory(_root);_root nullptr;}private:void _Destrory(Node* root){if (root nullptr){return;}_Destrory(root-_left);_Destrory(root-_right);delete root;}void _inorder(Node* root, vectorK v){if (root nullptr){return;}_inorder(root-_left,v);v.push_back(root-_kv.first);_inorder(root-_right,v);}void RotateL(Node* parent){Node* curR parent-_right;Node* curRL curR-_left;//调整结点并且修改其父亲结点指针parent-_right curRL;if (curRL)//可能为空{curRL-_parent parent;}//在修改子树根节点之前保存子树根节点的父亲Node* pparent parent-_parent;//修改子树根节点curR-_left parent;parent-_parent curR;//子树根节点有可能是整棵树的根节点if (pparent nullptr){_root curR;_root-_parent nullptr;}else//子树根节点不是整棵树的根节点{//还要看子树是它父亲的左孩子还是右孩子if (pparent-_left parent){pparent-_left curR;}else{pparent-_right curR;}curR-_parent pparent;}}void RotateR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;parent-_left curLR;if (curLR){curLR-_parent parent;}Node* pparent parent-_parent;curL-_right parent;parent-_parent curL;if (parent _root){_root curL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left curL;}else{pparent-_right curL;}curL-_parent pparent;}}Node* _root nullptr;}; //传参时benchmark是-1代表还没有基准值当走完第一条路径时//将第一条路径的黑色节点数作为基准值后续路径走到null时就与基准值比较。//blacknum记录路径上的黑色节点数bool _isRBTree(Node* root, int blacknum, int benchmark){if (root nullptr){if (benchmark -1){benchmark blacknum;}else{if (blacknum ! benchmark){cout black Node ! endl;return false;}}return true;}if (root-_col BLACK){blacknum;}//判断时候出现两个连续的红色结点if (root-_col RED root-_parent root-_parent-_col RED){cout red connect endl;return false;}return _isRBTree(root-_left, blacknum, benchmark) _isRBTree(root-_right, blacknum, benchmark);}
main.cpp
#includevector
#includecassert
#includeRB_Tree.hppint main()
{RBTReeint, int rb;int i 100000;while(i--){int num rand() i;rb.insert(make_pair(num,num));}vectorint v;rb.Inorder(v);for (int i 0; i v.size() - 1; i){if (v[i] v[i 1]){assert(0);}}cout rb.isRBTree() endl;return 0;
} 八. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O()红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红 黑树更多。
