linux 什么做网站好,如何设计和建立一个公司的网站,张店网站建设价,品牌策划公司推荐文章目录 一、基本概念1.时代背景2. 基本概念3.基本性质 二、实现原理1. 插入1.1变色1.2旋转变色①左旋②右旋③右左双旋④左右双旋 2.验证 源码总结 一、基本概念
1.时代背景
1972年鲁道夫拜尔(Rudolf Bayer)发明了一种数据结构#xff0c;这是一种特殊的B树4阶情况。这些树… 文章目录 一、基本概念1.时代背景2. 基本概念3.基本性质 二、实现原理1. 插入1.1变色1.2旋转变色①左旋②右旋③右左双旋④左右双旋 2.验证 源码总结 一、基本概念
1.时代背景
1972年鲁道夫·拜尔(Rudolf Bayer)发明了一种数据结构这是一种特殊的B树4阶情况。这些树保持了从根到叶的所有路径节点数量相同创造了完美平衡的树。但是它们不是二叉搜索树。拜耳在他的论文中称它们为“对称二元B树”。这是红黑树的起源。 在1978年的一篇论文“平衡树的二色框架”中列奥尼达斯·吉巴斯Leonidas J. Guibas 和罗伯特·塞奇威克Robert Sedgewick从对称的二元B树中推导出了红黑树。选择“红色”是因为它是作者在施乐PARC工作时可用的彩色激光打印机产生的最好看的颜色。吉巴斯的另一个回应说这是因为他们可以使用红色和黑色的笔来画树。 第一张为——列奥尼达斯·吉巴斯第二张为——罗伯特·塞奇威克。 1993年Arne Andersson引入了右倾树的想法以简化插入和删除操作。 1999年Chris Okasaki展示了如何使插入操作纯粹功能化。它的平衡功能只需要处理 4 个不平衡情况和一个默认平衡情况。 详细请看维基百科 2. 基本概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍因而是接近平衡的。
实现平衡的关键最长路径小于等于最短路径的两倍。
3.基本性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的(如果一个结点是黑色的则其两个孩子可以是红的也可以是黑的。)对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点
强调234点是有关联的且是最关键的3点。
假设根节点如果是红的那么插入的结点就是只能是黑的3那么就违背了4。对于3分析孩子结点为空但空节点也被理解成黑色(5)因此(5)是用来辅助(3)的。对于4分析可推理出两个结论—— 1 . 插入结点必须为红色的。 2 . 满足最长路径小于最短路径的两倍(概念)。对此点可以看做间隔问题即n个数之间不算头一个数有n个间隔即n个黑结点不算根节点之间最多有n个红结点。
二、实现原理
1. 插入
1.1变色
根本逻辑基于每条路径的黑色结点不变。
第一种变色方式 这样变是不是每条路径的黑色结点数没变呢
那这样变的前提是什么呢
黑色结点的左右孩子为红且不为空。
那什么时候发生变色呢
基于性质3红色结点的两个孩子必须为黑但由4我们可以推出每次插入结点必须为红那这时候我们按照4的原则进行处理使处理结果符合3即可怎么处理就是进行变色。 此时parent的右边进行插入新节点且parent在grandfather的左边。 此时在parent的右边进行插入且parent为grandfather的左节点。
总结
变色的前提是每条路径的黑色结点不变uncle非空且为红且parent为红变grandfather为红parent与uncle为黑。
继续分析如果grandfather为红其父节点是否可能为红呢
答案是可能的。
因此我们需要继续往上更新
更新cur为grandfatherparent为cur的parent
接着分析如果grandfather为根节点呢
由于性质2我们需要再次修改根节点的颜色为黑。
1.2旋转变色
前面我们分析了一种简单的只需变色的情况我们下面接着分析另外一种情况。
第二种变色需要在旋转的基础上进行分类讨论具体情况有四种。
①左旋 补充当uncle为黑结点时parent的左子树不为空且根节点为黑色cur的左右子树同理这里不过多分析了因为具体情况过多分析容易提高理解难度。
开始时parent在grandfather右边且cur在parent的右边
②右旋 对uncle的补充同左旋
开始时parent在grandfather左边且cur在parent的左边
③右左双旋 对uncle的补充同左旋
开始时parent在grandfather的右边且cur在parent的左边
④左右双旋 对uncle的补充同左旋 开始时parent在grandfather的左边且cur在parent的右边 总结 根据parent的位置我们可以大致分为两种情况 parent在grandfather的左边 parent在grand的右边 其实不难看出AVL和红黑树都会进行旋转只是AVL树旋转后处理的是平衡因子红黑树旋转后处理的是变色归根结底终究都是为了让树达到平衡。
核心代码 //判断是否要进行旋转变色
//当父节点为红色说明要进行判断
while (parent parent-_col RED)
{//爷爷结点Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED)//如果uncle存在且为红色{//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上迭代进行分析cur grandfather;parent cur-_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent-_left cur){RotateR(grandfather);parent-_col BLACK;cur-_col grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;parent-_col grandfather-_col RED;}break;}}else//grandfather-_right parent{Node* uncle grandfather-_left;if (uncle uncle-_col RED){//变色grandfather-_col RED;parent-_col uncle-_col BLACK;//往上更新cur grandfather;parent cur-_parent;}else{if (parent-_right cur){//旋转RotateL(grandfather);//变色parent-_col BLACK;grandfather-_col cur-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col parent-_col RED;}break;}}
}插入代码
bool insert(const pairKey, Val val)
{//第一步插入操作//如果根节点为空if (_root nullptr){_root new Node(val);_root-_col BLACK;return true;}else{Node* cur _root, * parent _root;while (cur){if (cur-_key val.first){parent cur;cur cur-_left;}else if (cur-_key val.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (parent-_key val.first){parent-_left cur;}else{parent-_right cur;}//更新新增结点的_parentcur-_parent parent;//判断是否要进行旋转变色//当父节点为红色说明要进行判断while (parent parent-_col RED){//爷爷结点Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED)//如果uncle存在且为红色{//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上迭代进行分析cur grandfather;parent cur-_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent-_left cur){RotateR(grandfather);parent-_col BLACK;cur-_col grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;parent-_col grandfather-_col RED;}break;}}else//grandfather-_right parent{Node* uncle grandfather-_left;if (uncle uncle-_col RED){//变色grandfather-_col RED;parent-_col uncle-_col BLACK;//往上更新cur grandfather;parent cur-_parent;}else{if (parent-_right cur){//旋转RotateL(grandfather);//变色parent-_col BLACK;grandfather-_col cur-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col parent-_col RED;}break;}}}//根节点可能为红色,不管红色还是黑色都弄成黑色_root-_col BLACK;return true;}
}2.验证
原理
根节点不能为红每条路径的黑色结点数相同每条路径不能出现连续的红色结点。
代码
bool _IsRBTree(Node* root)
{if (root nullptr)return true;//根节点是黑色的if (root-_col RED)return false;//各个路径的黑色结点数是相同的因此设立一个基准进行比较合适//再对树进行遍历求每个路径的黑色结点的数量最后比较即可。int benchmark 0;Node* cur root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return Check(root);
}
bool Check(Node* root, int BCount,int benchmark)
{if (root nullptr){//验证基准值是否等于黑色结点数//只要有一个不是即不是红黑树。if (BCount ! benchmark)return false;return true;}//求每条黑色结点的个数if (root-_col BLACK)BCount;//验证性质3即不能有连续的红色结点。if (root-_col RED root-_parent root-_parent-_col RED){return false;}return Check(root-_left,BCount,benchmark) Check(root-_right, BCount, benchmark);
}源码
#pragma once
#includeiostream
using namespace std;
namespace MY_STL
{enum Color{RED 0,BLACK 1};templateclass Key,class Valstruct RBTreeNode{typedef RBTreeNodeKey, Val Node;RBTreeNode(const pairKey,Val key):_key(key.first),_val(key.second),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED){}Node* _right;Node* _left;Node* _parent;Key _key;Val _val;Color _col;};templateclass Key,class Valclass RBTree{typedef RBTreeNodeKey, Val Node;public:bool insert(const pairKey, Val val){//第一步插入操作//如果根节点为空if (_root nullptr){_root new Node(val);_root-_col BLACK;return true;}else{Node* cur _root, * parent _root;while (cur){if (cur-_key val.first){parent cur;cur cur-_left;}else if (cur-_key val.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (parent-_key val.first){parent-_left cur;}else{parent-_right cur;}//更新新增结点的_parentcur-_parent parent;//判断是否要进行旋转变色//当父节点为红色说明要进行判断while (parent parent-_col RED){//爷爷结点Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED)//如果uncle存在且为红色{//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上迭代进行分析cur grandfather;parent cur-_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent-_left cur){RotateR(grandfather);RotateCount;parent-_col BLACK;cur-_col grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);RotateCount2;cur-_col BLACK;parent-_col grandfather-_col RED;}break;}}else//grandfather-_right parent{Node* uncle grandfather-_left;if (uncle uncle-_col RED){//变色grandfather-_col RED;parent-_col uncle-_col BLACK;//往上更新cur grandfather;parent cur-_parent;}else{if (parent-_right cur){//旋转RotateL(grandfather);RotateCount;//变色parent-_col BLACK;grandfather-_col cur-_col RED;}else{RotateR(parent);RotateL(grandfather);RotateCount 2;cur-_col BLACK;grandfather-_col parent-_col RED;}break;}}}//根节点可能为红色,不管红色还是黑色都弄成黑色_root-_col BLACK;return true;}}bool IsRBTree(){return _IsRBTree(_root);}size_t Height(){return Height(_root);}private:size_t Height(Node* root){if (root nullptr){return 0;}int LHeight Height(root-_left);int RHeight Height(root-_right);return max(LHeight, RHeight) 1;}bool _IsRBTree(Node* root){if (root nullptr)return true;//根节点是黑色的if (root-_col RED)return false;//各个路径的黑色结点数是相同的因此设立一个基准进行比较int benchmark 0;Node* cur root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return Check(root,0,benchmark);}bool Check(Node* root, int BCount,int benchmark){if (root nullptr){//验证基准值是否等于黑色结点数//只要有一个不是即不是红黑树。if (BCount ! benchmark)return false;return true;}//求每条黑色结点的个数if (root-_col BLACK)BCount;//验证性质3即不能有连续的红色结点。if (root-_col RED root-_parent root-_parent-_col RED){return false;}return Check(root-_left,BCount,benchmark) Check(root-_right, BCount, benchmark);}void RotateL(Node* parent){//画图分析//操作的结点有cur,cur_left,ppnodeNode* cur parent-_right;Node* cur_left cur-_left;//将parent的右节点改为cur_leftparent-_right cur_left;//改变cur_left父节点的转向//cur_left可能为空if (cur_left ! nullptr){cur_left-_parent parent;}//将parent链接在cur的左边//为了更新cur的parent需要保存parent的父节点Node* ppnode parent-_parent;cur-_left parent;parent-_parent cur;//ppnode可能为空if (ppnode nullptr){//需要修改根节点_root cur;cur-_parent nullptr;}else{//改变ppnode的指向if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){//操作的结点Node* cur parent-_left;Node* cur_right cur-_right;//第一步将cur_right链接到parent的leftparent-_left cur_right;//更改cur_right的父节点//注意cur_right可能为空if (cur_right ! nullptr){cur_right-_parent parent;}//第二步将parent链接到cur的右结点。//先保存一下parent的父节点Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;//ppnode为空说明需要修改根节点if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}Node* _root nullptr;public:size_t RotateCount 0;};
};总结 红黑树的理解较AVL树抽象需要画图分析不过有了AVL树旋转的基础这里的难度要下降不少。还是与之前一样只要图画的好代码跑不了所以这里的关键就在于画图。 总之今天的分享到这里就结束了如果感觉有所帮助不妨点个赞鼓励一下吧
