js网站开发,长春最新发布信息,北京搜索关键词优化,怎么做一个网站app吗目录 一、前言
二、正文
2.1 红黑树的概念
2.2 红黑树的性质
2.3红黑树节点的定义 2.4 红黑树的插入 2.4.1 情况一
2.4.2 情况二
编辑 2.4.3 情况三 2.5 红黑树的验证 三、全部代码 四、结语 一、前言 在上一篇博客中#xff0c;为小伙伴们进行了AVL树的讲解#… 目录 一、前言
二、正文
2.1 红黑树的概念
2.2 红黑树的性质
2.3红黑树节点的定义 2.4 红黑树的插入 2.4.1 情况一
2.4.2 情况二
编辑 2.4.3 情况三 2.5 红黑树的验证 三、全部代码 四、结语 一、前言 在上一篇博客中为小伙伴们进行了AVL树的讲解但是由于在实际场景中大部分插入的数据都是无序的所以红黑树的应用相较于AVL树会更会广泛插入相同的数据红黑树的旋转次数会比AVL树少很多且其层数也不会像二叉搜索树那样高。因此在本篇博客中为大家带来红黑树的讲解如有不足之处欢迎各位大佬们给予指正 二、正文
2.1 红黑树的概念 红黑树是一棵二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 以下图为例我们发现最短的路径上有三个节点最长的路径有4个节点并没有超出最短路径的两倍。 2.2 红黑树的性质 在上面中我们了解到一颗红黑树中最长路径的节点不超过最短路径的两倍那么我们到底该如何让一颗二叉搜索树变成这样的一颗红黑树呢这就需要满足红黑树的以下几个性质 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 2.3红黑树节点的定义 那么在了解完红黑树的概念及其性质后接下来我们就来讲讲该如何实现这样的一颗红黑树。 首先我们要明确的是红黑树的底层结构其实是与AVL树是一样的都是一颗搜索二叉树且为了使他们的结构都能达到各自的平衡因此都需要采取三叉链的结构即树节点内必须包含父亲左孩子和右孩子三个节点指针以方便树的旋转平衡。除此之外既然是红黑树其节点就是有“颜色”的那么理所应当的我们在每个节点内还需要定义一个颜色我们可以通过枚举的方式来实现这也是其与AVL树不同的地方所在。 当然这里还有一个额外需要注意的地方就是对于一个节点的初始化其三叉链的节点指针好说定义为空指针即可但是颜色我们该定义为黑色还是红色呢在这里我们采取的是红色这里其实是考虑在尽量影响较少红黑树的结构下我们选择的因为如果当我们将新插入节点的颜色定义为黑色时那么该节点所处路径下的黑色节点数就都会加一就会与其他路径的黑色节点数不同在调整次数为各个路径黑色节点数相同就会比较麻烦反之若是插入新节点的颜色为红色那么就不会影响该路径的黑色节点数倘若插入处的父亲节点为黑色那么插入后仍为一颗红黑树。如果父亲节点为红色虽然违背了红黑树“红色节点的左右孩子节点都是黑色”这一点但是通过变色或者旋转的方式我们还是能够比较轻松将其重新变成一颗红黑树相较于去调整其他路径的黑色节点数来说因此我们在创建一个新节点的时候会将其颜色初始化为红色。 具体代码如下 //枚举红色和黑色
enum Color
{RED,BLACK
};//红黑树节点的定义
template class K,class V
struct RBTreeNode
{//采取三叉链的方式方便树的旋转平衡RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;//颜色Color _col;pairK, V _kv;RBTreeNode(const pairK ,V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //默认初始化为红色, _kv(kv){}
}; 2.4 红黑树的插入 在成功创建完一个红色的新节点后接下来的操作就是将这个新节点插入树中。 首先第一步就是找到其应所处的位置。由于红黑树的底层结构是一颗二叉搜索树因此我们只需要从根节点开始不断进行数值的比较若是比插入节点的数值大就来到左子树比插入的节点数据小就来到右子树直至找到空指针为止那么该处就是新节点所应该插入的位置。要注意的是如果遇到插入的数据在比较时遇到相同时就应该退出来无需插入。无重复数据的红黑树 第二步就是进行新节点与父亲节点的链接若是父亲节点的数据大于新节点就链接到其左子树小于新节点则链接到右子树。 第三步就是进行红黑树规则的判断判断在插入该节点后是否仍满足一颗红黑树若是不满足则需要进行相对应的调整使其重新变为一颗红黑树这也是其在插入过程中最为重要的一步。那么我们该如何判断在插入新节点后此树是否仍为一颗红黑树呢其实在上面新节点的颜色选择上已经点出了由于我们插入新节点的颜色是红色那么其违反的规则只有一条就是“红色节点的左右子树必须都为黑色节点”因此只要新节点的父亲节点为红色就说明我们插入新节点后此树就不再是一颗红黑树需要我们对此树进行一个调整使其重新变成一颗红黑树。 代码框架如下 bool Insert(const pairK, V kv){//空树if (_root nullptr){_root new Node(kv);}//树不为空else{//寻找父亲结点Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else return false;}//插入新节点cur new Node(kv);if (cur-_kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//检测插入新节点后红黑树的性质是否发生变化while (parent parent-_col RED){…… }}//无论进行怎样的处理 根结点都为黑_root-_col BLACK;return true;} 当我们找好位置插入新节点后若是父亲节点的颜色为黑色自然满足红黑树的性质不需要再继续调整但是如果父亲节点的颜色为红色那么就不满足红黑树的性质我们就需要根据不同的情况进行调整下面我们就对这几种情况进行逐一的讲解。 注cur为当前节点p为父亲节点g为祖父节点u为叔叔节点 2.4.1 情况一
cur为红p为红g为黑u存在且为红 面对这种情况我们只需要将p,u改为黑g改为红然后把g当成cur继续向上调整。在向上调调整的过程中我们可能会遇到这两种情况 1.cur为红色p为黑色——满足红黑树的性质调整完毕 2.一直调整至根节点即g为nullptr——无需继续向上调整将根节点即p节点调整为黑色调整完毕 示意图及代码如下 //情况一uncle存在且为红-变色//父亲是祖父的左节点if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//变色后继续向上传递cur grandfather;parent cur-_parent;}}//父亲是祖父的右节点else if (parent grandfather-_right){Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//变色后继续向上传递cur grandfather;parent cur-_parent;}}
2.4.2 情况二
cur为红p为红g为黑u不存在 面对这种情况情况操作起来就不像情况一那么简单情况一无需考虑curpg三节点之间的相对位置而情况二则需要根据三者之间的相对位置来进行不同的旋转大致有四种旋转情况左单旋右单旋左右双旋和右左双旋 具体旋转和变色如下 2.4.3 情况三 cur为红p为红g为黑u存在且为黑 面对这种情况与情况二的操作类似都是旋转加变色 具体旋转和变色见下 虽然情况二和情况三中一种是存在u节点且为黑一种不存在u节点但我们发现在旋转和变色的过程u节点几乎没有参与其中因此我们在实现的时候其实可以将这两种情况归为一种。 具体代码如下 //旋转加变色while (parent parent-_col RED){Node* grandfather parent-_parent;//父亲是祖父的左节点if (parent grandfather-_left){Node* uncle grandfather-_right;//情况二\三:uncle不存在或者uncle存在但颜色为黑-旋转加变色else if (uncle nullptr || uncle-_col BLACK){//孩子在父亲的左边-右单旋加变色// g // p //c if (cur parent-_left){RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;break;}//孩子在父亲的右边-左右单旋加变色// g // p // c else if (cur parent-_right){RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}//父亲是祖父的右节点else if (parent grandfather-_right){Node* uncle grandfather-_left;//情况二\三:uncle不存在或者uncle存在但颜色为黑-旋转加变色else if (uncle nullptr || uncle-_col BLACK){//孩子在父亲的右边-左单旋加变色// g // p // c if (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;break;}//孩子在父亲的左边-右左单旋加变色// g // p // c else if (cur parent-_left){RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}} 在红黑树的节点插入之后为了方便建立起对插入过程的直观理解下面为大家呈现两种节点插入方式所带来的效果。 方式一升序降序插入 插入构建红黑树 方式二随机插入构建红黑树 2.5 红黑树的验证 当我们按照代码所写构建完一颗红黑树之后下一步就是对我们所搭建的红黑树进行验证才能保证我们的代码无误。对于红黑树来说验证主要分为两步 1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)对于这一步来说与前面AVL的验证是相同的笔者就不在这里做过多赘述有需求的小伙伴可以移步到博主的上一篇文章【C】——AVL树-CSDN博客 2. 检测其是否满足红黑树的性质 ①根节点是否为黑色 ②红色节点的左右子树是否都为黑色节点 ③每条路径的黑色节点数相同 具体代码如下 // 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){//空树if (_root nullptr) return true;//根结点为黑色if (_root-_col RED) return false;//每条路径的黑色结点数相同int benmarch 0;Node* root _root; //基准值while (root){if (root-_col BLACK) benmarch;root root-_left;}_IsValidRBTRee(_root, 0, benmarch);}bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack){if (pRoot nullptr blackCount ! pathBlack){return false;}else if (pRoot nullptr blackCount pathBlack){return true;}if(pRoot-_colBLACK){blackCount;}if (pRoot-_col RED pRoot-_parent pRoot-_parent-_col RED){cout pRoot-_kv.first 出现连续的红节点 endl;return false;}return _IsValidRBTRee(pRoot-_left,blackCount,pathBlack) _IsValidRBTRee(pRoot-_right,blackCount,pathBlack);} 三、全部代码
#pragma once//枚举红色和黑色
enum Color
{RED,BLACK
};//红黑树节点的定义
template class K,class V
struct RBTreeNode
{//采取三叉链的方式方便树的旋转平衡RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;pairK, V _kv;RBTreeNode(const pairK ,V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv){}
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:RBTree() {}bool Insert(const pairK, V kv){//空树if (_root nullptr){_root new Node(kv);}//树不为空else{//寻找父亲结点Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else return false;}//插入新节点cur new Node(kv);if (cur-_kv.first parent-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//旋转while (parent parent-_col RED){Node* grandfather parent-_parent;//父亲是祖父的左节点if (parent grandfather-_left){Node* uncle grandfather-_right;//情况一uncle存在且为红-变色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//变色后继续向上传递cur grandfather;parent cur-_parent;}//情况二:uncle不存在或者uncle存在但颜色为黑-旋转加变色else if (uncle nullptr || uncle-_col BLACK){//孩子在父亲的左边-右单旋加变色// g // p //c if (cur parent-_left){RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;break;}//孩子在父亲的右边-左右单旋加变色// g // p // c else if (cur parent-_right){RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}//父亲是祖父的右节点else if (parent grandfather-_right){Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//变色后继续向上传递cur grandfather;parent cur-_parent;}//情况二\三:uncle不存在或者uncle存在但颜色为黑-旋转加变色else if (uncle nullptr || uncle-_col BLACK){//孩子在父亲的右边-左单旋加变色// g // p // c if (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;break;}//孩子在父亲的左边-右左单旋加变色// g // p // c else if (cur parent-_left){RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;break;}}}}}//无论进行怎样的处理 根结点都为黑_root-_col BLACK;return true;}// 检测红黑树中是否存在值为k的节点存在返回该节点的地址否则返回nullptrNode* Find(const K k){_Find(_root);}// 获取红黑树最左侧节点Node* LeftMost(){_LeftMost(_root);}// 获取红黑树最右侧节点Node* RightMost(){_RightMost(_root);}// 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){//空树if (_root nullptr) return true;//根结点为黑色if (_root-_col RED) return false;//每条路径的黑色结点数相同int benmarch 0;Node* root _root; //基准值while (root){if (root-_col BLACK) benmarch;root root-_left;}_IsValidRBTRee(_root, 0, benmarch);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack){if (pRoot nullptr blackCount ! pathBlack){return false;}else if (pRoot nullptr blackCount pathBlack){return true;}if(pRoot-_colBLACK){blackCount;}if (pRoot-_col RED pRoot-_parent pRoot-_parent-_col RED){cout pRoot-_kv.first 出现连续的红节点 endl;return false;}return _IsValidRBTRee(pRoot-_left,blackCount,pathBlack) _IsValidRBTRee(pRoot-_right,blackCount,pathBlack);}// 左单旋void RotateL(Node * pParent){Node* grandparent pParent-_parent;Node* cur pParent-_right;Node* cur_left cur-_left;//旋转相关结点if (cur_left) cur_left-_parent pParent; //不为空pParent-_right cur_left;cur-_left pParent;pParent-_parent cur;if (this-_root pParent){this-_root cur;cur-_parent nullptr;}else if (grandparent-_left pParent){grandparent-_left cur;cur-_parent grandparent;}else if (grandparent-_right pParent){grandparent-_right cur;cur-_parent grandparent;}}// 右单旋void RotateR(Node * pParent){Node* grandparent pParent-_parent;Node* cur pParent-_left;Node* cur_right cur-_right;//旋转相关节点pParent-_left cur_right;if (cur_right) cur_right-_parent pParent; //不为空cur-_right pParent;pParent-_parent cur;if (grandparent nullptr){this-_root cur;cur-_parent nullptr;}else if (grandparent-_left pParent){grandparent-_left cur;cur-_parent grandparent;}else if (grandparent-_right pParent){grandparent-_right cur;cur-_parent grandparent;}}Node* _Find(Node* root,const K k){if (root nullptr) return nullptr;if (root-_kv.first k) _Find(root-_left, k);else if (root-_kv.first k) _Find(root-_right, k);else return root;}Node* _LeftMost(Node* root){if (root _root) return root;else if (root-_left nullptr) return root;else return _LeftMost(root-_left);}Node* _RightMost(Node* root){if (root _root) return root;else if (root-_right nullptr) return root;else return _RightMost(root-_right);}Node* _rootnullptr;
};void text()
{const int N 10000;vectorpairint,int v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(pairint,int(i,i));}RBTreeint, int RBTree;for (const auto e : v){RBTree.Insert(e);cout e.first : RBTree.IsValidRBTRee()endl;}
} 四、结语 到此为止关于红黑树树的讲解就告一段落了至于其他的内容小伙伴们敬请期待呀 关注我 _麦麦_分享更多干货_麦麦_-CSDN博客 大家的「关注❤️ 点赞 收藏⭐」就是我创作的最大动力谢谢大家的支持我们下期见
