怎么做整人网站,专业网站设计,收不到wordpress的邮件,免费招聘的网站目录 一、红黑树的概念二、红黑树的性质三、红黑树的节点的定义四、红黑树结构五、红黑树的插入操作参考代码 五、代码汇总 一、红黑树的概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过… 目录 一、红黑树的概念二、红黑树的性质三、红黑树的节点的定义四、红黑树结构五、红黑树的插入操作参考代码 五、代码汇总 一、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍因而是接近平衡的。如图所示
二、红黑树的性质
每个结点不是红色就是黑色。根节点是黑色的。如果一个节点是红色的则它的两个孩子结点是黑色的。对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点。每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。 问题为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 因为根节点是黑色是固定的并且不能有连续的红色节点每条路径黑色节点的个数一样也就是说最短路就是全黑最长路径就是一黑一红相间所以一条路径的红色节点要么和黑色节点一样多要么少于黑色节点即同一条路径黑色节点的占比是大于等于50%的所以最长路径一定不超过最短路径的2倍。 三、红黑树的节点的定义 //通过枚举定义红色和黑色的常量enum Colour{RED,BLACK};template class K,class Vstruct RBTreeNode{public://红黑树存放的值pairK, V _kv;//节点的三叉链指针RBTreeNodeK,V* _left;RBTreeNodeK,V* _right;RBTreeNodeK,V* _parent;//节点的颜色Colour _col;//构造函数RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};思考在节点的定义中为什么要将节点的默认颜色给成红色的 这个问题就是关于插入节点的时候我们默认插入的是黑色的节点还是红色的节点了根据红黑树的规则每一条路径的黑色节点的个数是一样的假如我们插入黑色节点那么某条路径的黑色节点就多了一个也就是说其它路径的黑色节点也要增加一个但是我们只插入了一个节点要令其它路径的黑色节点的数量都增加一个这个操作的难度显然是很大的但是如果我们默认插入一个红色节点那么我们最多违反了根节点为黑色或者连续两个红色节点的规则主要还是容易违反连续两个红色节点的规则这个问题只会影响当前节点到祖先这条路径不会影响其他路径的节点所以处理起来会更简洁一些所以我们默认插入的节点是红色的。 四、红黑树结构 五、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
按照二叉搜索树的规则插入新节点。检测新节点插入后红黑树的性质是否遭到破坏如果是就要通过变色加旋转操作维持红黑树的性质。
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点。
情况一: cur为红p为红g为黑u存在且为红。 情况二: cur为红p为红g为黑u不存在/u存在且为黑。 因为旋转后需要把p变成黑色所以p节点和p的父节点不能再出现连续两个红色节点所以旋转变色后就不用再沿祖先路径更新了。 情况一 情况二 情况三 情况四
参考代码 bool Insert(const pairK, V kv){//如果是空树那么就直接插入一个黑色节点做根即可//注意要改颜色因为节点的颜色默认是红色的if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//根据二叉搜索树的规则插入节点同时记录父节点Node* parent nullptr;Node* cur _root;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;cur-_parent parent;}else if (kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}//走到这里已经插入完成后面是检查新插入的节点有没有破坏红黑树的规则的逻辑//检查新插入的节点是否满足红黑树的规则如果不满足就要进行变色/变色旋转//因为新插入的cur节点的颜色一定是红色的当cur的父节点存在并且为红色//时说明出现了连续的两个红色节点这时需要进行变色/变色旋转如果父节点// 不存在或者存在且为黑色时就无需再处理了。// 为什么父节点有可能不存在因为这是一个循环循环更新往祖先处理可能到达根节点//到了根节点就无需再处理了while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (cur parent-_left){// grandfather// parent//cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;//这里曾经漏写了}//叔叔不存在或者存在且为黑else//(unclenullptr||uncle-_colBLACK){//单纯的左边高进行右单旋变色RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转完之后无需再沿祖先路径处理break;}}else//cur parent-_right{// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上调整cur grandfather;parent cur-_parent;//这里曾经忘记写}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//左右双旋RotateL(parent);RotateR(grandfather);//变色grandfather-_col RED;cur-_col BLACK;//旋转后就无需再沿祖先路径检查了具体原因画图理解break;}}}else//(parent grandfather-_right){Node* uncle grandfather-_left;if (cur parent-_right){// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//单纯的右边高进行左单旋变色RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转变色后就不需要再沿祖先路径检查了break;}}else//(cur parent-_left){// grandfather// parent// cur//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//根据模型可知需要右左双旋变色RotateR(parent);RotateL(grandfather);grandfather-_col RED;cur-_col BLACK;//旋转后就不需要再沿祖先路径检查了break;}}}}_num;//最后记得把根节点的颜色改成黑色_root-_col BLACK;return true;}//旋转的细节如果不清楚的话请看上一篇关于AVL树的旋转红黑树的旋转和AVL树的旋转是一样的void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* curleft cur-_left;Node* parentParent parent-_parent;parent-_right curleft;cur-_left parent;if (curleft){curleft-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}void RotateR(Node* parent){assert(parent);Node* cur parent-_left;Node* curright cur-_right;Node* parentParent parent-_parent;parent-_left curright;cur-_right parent;if (curright){curright-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}五、代码汇总
#pragma once#include iostream
using namespace std;
#include assert.hnamespace kb
{enum Colour{RED,BLACK};template class K,class Vstruct RBTreeNode{public://红黑树存放的值pairK, V _kv;//节点的三叉链指针RBTreeNodeK,V* _left;RBTreeNodeK,V* _right;RBTreeNodeK,V* _parent;//节点的颜色Colour _col;//构造函数RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template class K,class Vclass RBTree{typedef RBTreeNodeK, V Node;public:bool Insert(const pairK, V kv){//如果是空树那么就直接插入一个黑色节点做根即可//注意要改颜色因为节点的颜色默认是红色的if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//根据二叉搜索树的规则插入节点同时记录父节点Node* parent nullptr;Node* cur _root;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;cur-_parent parent;}else if (kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}//走到这里已经插入完成后面是检查新插入的节点有没有破坏红黑树的规则的逻辑//检查新插入的节点是否满足红黑树的规则如果不满足就要进行变色/变色旋转//因为新插入的cur节点的颜色一定是红色的当cur的父节点存在并且为红色//时说明出现了连续的两个红色节点这时需要进行变色/变色旋转如果父节点// 不存在或者存在且为黑色时就无需再处理了。// 为什么父节点有可能不存在因为这是一个循环循环更新往祖先处理可能到达根节点//到了根节点就无需再处理了while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (cur parent-_left){// grandfather// parent//cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;//这里曾经漏写了}//叔叔不存在或者存在且为黑else//(unclenullptr||uncle-_colBLACK){//单纯的左边高进行右单旋变色RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转完之后无需再沿祖先路径处理break;}}else//cur parent-_right{// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上调整cur grandfather;parent cur-_parent;//这里曾经忘记写}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//左右双旋RotateL(parent);RotateR(grandfather);//变色grandfather-_col RED;cur-_col BLACK;//旋转后就无需再沿祖先路径检查了具体原因画图理解break;}}}else//(parent grandfather-_right){Node* uncle grandfather-_left;if (cur parent-_right){// grandfather// parent// cur//画图//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//单纯的右边高进行左单旋变色RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;//旋转变色后就不需要再沿祖先路径检查了break;}}else//(cur parent-_left){// grandfather// parent// cur//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续沿祖先路径检查cur grandfather;parent cur-_parent;}//叔叔不存在或者存在且为黑else//(unclenullptr || uncle-_col BLACK){//根据模型可知需要右左双旋变色RotateR(parent);RotateL(grandfather);grandfather-_col RED;cur-_col BLACK;//旋转后就不需要再沿祖先路径检查了break;}}}}_num;//最后记得把根节点的颜色改成黑色_root-_col BLACK;return true;}size_t Size(){return _num;}bool Isbalance(){return _Isbalance(_root);}void Inorder(){_Inorder(_root);}private:bool CheckColour(Node* root, int blackNum, int BenchMark){//走到空树说明这条路径已经走完了需要检查黑色节点的个数和基准值相不相等if (root nullptr){//如果不相等证明不平衡返回falseif (blackNum ! BenchMark){return false;}//如果相等则说明本条路径没有出事还要检查其它路径return true;}//如果出现连续红色节点证明这棵树出问题了返回falseif (root-_col RED root-_parent root-_parent-_col RED){return false;}if (root-_col BLACK){blackNum;}//递归检查所有路径的颜色return CheckColour(root-_left, blackNum, BenchMark) CheckColour(root-_right, blackNum, BenchMark);}bool _Isbalance(Node* root){//空树可以认为是平衡的if (root nullptr){return true;}//根节点不是黑色说明这棵树出事了if (root-_col ! BLACK){return false;}//先算出一条路径的黑色节点的个数作为基准值检查其它路径的黑色节点数目是否跟这个标准值//是否一样如果不一样就证明这棵树不平衡了那么如果这个基准值本身就是错的呢那也没有关系//只要有路径的黑色节点和其它路径不相等就说明肯定有其中一条路径出问题了至于是哪条路径//出问题就不重要了int BenchMark 0;Node* cur root;while (cur){if (cur-_col BLACK){BenchMark;}cur cur-_left;}//检查所有路径中是否有连续红色节点和各路径中黑色节点的数目是否相等return CheckColour(root, 0, BenchMark);}void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.second ;_Inorder(root-_right);}//旋转的细节如果不清楚的话请看上一篇关于AVL树的旋转红黑树的旋转和AVL树的旋转是一样的void RotateL(Node* parent){assert(parent);Node* cur parent-_right;Node* curleft cur-_left;Node* parentParent parent-_parent;parent-_right curleft;cur-_left parent;if (curleft){curleft-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}void RotateR(Node* parent){assert(parent);Node* cur parent-_left;Node* curright cur-_right;Node* parentParent parent-_parent;parent-_left curright;cur-_right parent;if (curright){curright-_parent parent;}parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left cur;}else{parentParent-_right cur;}cur-_parent parentParent;}}private:Node* _root nullptr;int _num 0;//统计树的节点个数};void testRBTree(void){RBTreeint, int rbt;int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };for (const auto e : arr){rbt.Insert(make_pair(e, e));}/*rbt.Inorder();*/cout rbt.Size() endl;bool ret rbt.Isbalance();cout ret endl;cout endl;}void testRBTree1(void){RBTreeint, int rbt;int N 10000;srand((unsigned int)time(nullptr));for (size_t i0;iN;i){int e rand();rbt.Insert(make_pair(e, e));}cout rbt.Size() endl;bool ret rbt.Isbalance();cout ret endl;cout 插入完成 endl;}
}以上就是红黑树的相关内容了最重要的是要理解当红黑树插入元素后违反了红黑树的规则时该如何对节点进行旋转加变色来使这棵红黑树重新回到平衡的。至于删除节点的操作就不实现了有兴趣的可以去看看《算法导论》这本书里面有讲红黑树删除操作的。
好啦以上就是今天想要跟大家谈的关于红黑树的最重要的内容了你学会了吗如果你感觉到有所帮助那么点点小心心点点关注呗后期还会持续更新C的相关知识哦我们下期见啦
