医疗类网站前置审批,沈阳计算机培训短期速成班,淘宝刷单的网站建设,国家免费职业技能培训数据结构/C#xff1a;红黑树 概念实现基本结构插入uncle为红色节点uncle为黑色节点 总代码展示 概念
红黑树是一种二叉搜索树#xff0c;一般的二叉搜索会发生不平衡现象#xff0c;导致搜索效率下降#xff0c;于是学者们开始探索如何让二叉搜索树保持平衡#xff0c;这… 数据结构/C红黑树 概念实现基本结构插入uncle为红色节点uncle为黑色节点 总代码展示 概念
红黑树是一种二叉搜索树一般的二叉搜索会发生不平衡现象导致搜索效率下降于是学者们开始探索如何让二叉搜索树保持平衡这种树叫做自平衡二叉搜索树。起初学者发明了AVL树其通过一定算法保持了二叉搜索树的严格平衡不久后Rudolf Bayer发明了红黑树红黑树的平衡是较为宽泛的为了保持平衡红黑树付出的代价比AVL树更小。因此红黑树被更为广泛的使用比如JavaCpython中使用的自平衡二叉搜索树都是红黑树而不是AVL树。
如果想了解AVL树可以看这篇博客[数据结构/CAVL树]
红黑树的要求如下 红黑树中最长路径的长度不会超过最短路径的两倍 先解释一下路径的概念从根走到nullptr。 有不少人认为路径是从根走到叶子节点这是不正确的。
红黑树用了五条规则来限制一棵树从而达到以上要求 每个节点不是红色就是黑色根节点一定是黑色不可以出现连续的红色节点黑色可以连续出现 每一条路径都包含相同数目的黑色节点nullptr视为黑色节点 只要满足以上五个条件那么这棵树就是一颗红黑树而且满足最长路径的长度不会超过最短路径的两倍。为什么呢
五条规则中我标红了34两条规则 不可以出现连续的红色节点黑色可以连续出现 每一条路径都包含相同数目的黑色节点 由于每一条路径都必须包含相同数目的黑色节点现在我们假设一棵红黑树所有路径的黑色节点数目都是x那么最短的路径长度就是全为黑色节点长度为x。 如果想让一条路径变长那么就只能插入更多的红色节点因为黑色节点数目相同但是红色节点又不能连续出现所以只能是黑红黑红黑红黑红黑红......这样排列一个黑节点匹配一个红节点因此最长路径的长度就是黑色节点的两倍2x。 可以发现红黑树通过这两条核心规则保证了二叉搜索树的平衡。
比如以下就是一颗红黑树
其最短路径为最左侧的路径长度为2即两个黑节点。 其最长路径为最右侧的路径长度为4即一红一黑排列。
要注意的是不是所有的红黑树都会出现以上的全黑路径或者一红一黑路径的这只是极端情况。
接下来我们通过实现红黑树来了解红黑树是如何自平衡的 实现
基本结构
首先我们要在节点中加入一个成员来表示节点的颜色颜色有红黑和黑色两种状态这里我使用枚举来区分两者
enum Colour
{RED,BLACK
};在某些红黑树的实现中使用bool值来表示红黑颜色这也是可以的但是本博客以枚举来表示颜色。
节点类
templateclass K, class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Colour _col;
};_left左子树 _right右子树 _parent父节点 _kv节点存储的值 _col该节点的颜色 节点类还需要一个构造函数进行初始化现在的问题就是新的节点要初始化为什么颜色 先来考虑一下插入红色节点和插入黑色节点谁对红黑树影响大 对于一棵红黑树其所有路径的黑色节点数目都相同如果我们在某一条路径末尾插入了黑色节点那么整棵树的所有其它路径都会少一个黑节点。而插入红色节点只影响当前路径所以新节点应该是红色节点。
构造函数
RBTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//初始化为红节点
{}接着就是红黑树本体类中只存储一个根节点_root
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
private:Node* _root nullptr;
}现在我们有了红黑树的基本结构接下来就实现它的插入操作 插入
那么我们先写出当基本的二叉搜索树的插入代码逻辑既然要插入那么就要先找到合适的位置插入代码如下
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;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-_left cur;elseparent-_right cur;cur-_parent parent;//调整红黑树//......//......//......return true;
}接下来我先解析以上代码的逻辑 if (_root nullptr)
{_root new Node(kv);_root-_col BLACK;//保持根为黑节点
}如果我们插入节点时根节点_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;}
}以上代码是在找到合适的插入位置当key大于当前节点cur-_kv.first kv.first那么cur就向左寻找反之向右寻找。如果当前节点值等于key那么说明该节点已经存在返回false代表插入失败。当我们的cur为空指针说明已经找到了插入的节点此时跳出循环进行插入。 cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;
elseparent-_right cur;cur-_parent parent;到达此处说明前面已经找到插入的位置了而parent节点就是插入位置的父亲节点。根据key的大小来判断插入到左边还是右边插入完成后再让新节点的_parent指向parent。 至此我们就完成了插入操作接下来就要根据不同情况对红黑树进行调整。 对于红黑树的插入我们需要关注新节点的父亲parent祖父grandfather叔叔uncle三个节点 先根据父亲节点的颜色来判断是否需要调整 父亲节点为黑色 新插入的节点默认为红色所以新插入节点不会影响路径上黑色节点的数目而parent是黑节点我们也没有出现连续的红色节点所以这种情况无需任何调整直接插入就可以。 父亲节点为红色 如果父亲节点为红色我们就会出现连续的红色节点这时我们就需要进行调整了 以上两种情况总结为 当parent为黑色直接插入 当parent为红色插入后需要进行调整 当parent为红色我们就需要再根据uncle的颜色将插入分类两类uncle为红色以及uncle为黑色。 值得注意的是由于parent是红色节点此时的grandfather一定是黑色节点因为不能出现连续红色节点 这两种情况的操作不同我们先看到uncle为红色的情况 uncle为红色节点 当uncle节点为红色此时需要进行变色 变色如下
由于新插入了红色的cur节点此时parent与cur出现了连续的红色节点于是我们将parent改为黑色。但是此时以parent为根的所有路径就会多出一个黑节点于是把grandfather变为红色来抵消这个新增的黑节点。但是此时以uncle为根的路径又会少一个黑节点于是把uncle变黑。
但是我们将grandfather变为了红色这有可能会影响到上一层节点比如这样 我们把grandfather变红之后又出现了两个红色节点相连的情况所以我们要写一个while循环来反复向上检查。
当前代码如下
while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在)
{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;}else//uncle为黑节点 {//其它处理}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle为黑节点 {//其它处理}}
}_root-_col BLACK;//在循环内部不判断root情况统一处理代码解析 while (parent parent-_col RED)该代码用于检测cur的parent的颜色通过我们前面的推导如果parent为红色才需要调整因此进入循环的条件之一是parent为红色。另外的parent有可能为nullptr此时我们要避免访问空指针所以空指针也不能进循环 if (parent grandfather-_left)
{ }
else
{ }这一段代码是在检测parent 节点是grandfather的左子树还是右子树这将涉及到我们如何找uncle以及下一种情况的调整此时我们要分类讨论。当parent grandfather-_left成立那么uncle就是grandfather的右子树Node* uncle grandfather-_right;反之就是左子树 if (uncle uncle-_col RED)
{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;
} 我们找到uncle后如果uncle是红色那么直接进行变色操作把parent和uncle的颜色变为黑色grandfather变为红色。 随后由于我们的变色操作可能会影响上一层此时调整节点进入下一次while循环 在整个while循环外侧还有一句代码 _root-_col BLACK;这是因为我们在先前的while循环中有可能出现对_root节点的操作导致_root的颜色改变而_root需要保持黑色。如果我们在循环内部每一次都检测_root有点麻烦了于是我们直接在每一次调整完节点后把_root强行矫正为黑色 至此我们就讨论完了uncle为红色节点的情况接下来我们就讨论uncle为黑色节点 uncle为黑色节点
由于红黑树中nullptr也算作黑色节点所以uncle为黑色分为以下两种情况 uncle为空指针uncle不为空指针 图示如下 如果 uncle为空指针那么cur一定是新插入的节点。 因为如果cur不是新插入的节点那么cur和parent一定有一个原先是黑色节点不然会出现连续的红色节点。但是如果cur和parent有一个是黑色节点那么grandfather的左子树就比右子树多出一个黑节点这就违背了红黑树规则。无论怎样原先的树都不可能符合规则所以cur一定是新插入的节点破坏了规则。 如果 uncle不为空指针那么cur一定是从黑色节点变成的红色节点不是新插入的。 因为如果uncle存在那么grandfather的右子树就存在一个黑节点而parent是红节点所以cur和parent的右子树中都至少有一个黑节点才能保证每一条路径黑节点数目相同。因此cur原先一定是黑节点是因为cur下层插入了新节点然后通过while循环向上走影响到了当前层。
对于这种uncle为黑色的情况我们需要通过旋转变色来维持红黑树。
旋转又分为单旋和双旋 当cur与parent的关系和parent与grandfather的关系一致时需要进行单旋 比如我们刚刚的情况 cur是parent的左子树parent是grandfather的左子树关系一致。 我们需要对其进行右单旋变色 这个旋转的算法在此我就不过多讲解了可以去AVL树的博客中了解。我重点讲解一下变色和旋转的合理性 一次插入过程中走到这一步说明前面一定经过了uncle为红色的情况而对uncle为红色的情况进行变色并不会对任何路径的黑色节点数目造成影响因此目前还是符合黑色节点数目相同规则的。 同为parent的子树以cur和C为根的路径黑节点数目相同 同为grandfather的子树以parent和uncle为根的路径黑节点数目相同 而parent是红色节点所以curC以及uncle为根的路径黑节点数目都相同 进行单旋会把c树交给grandfather做子树而c与uncle为根的路径黑节点数目相同不违背规则旋转的合理性 旋转后parent作新根grandfather与cur作为左右子树grandfather为根的路径整体上就会比以cur为根的路径多出一个黑节点(即grandfather本身) 因此将grandfather改为红节点来平衡parent左右子树的黑节点 而红色节点不能连续出现再把parent改为黑节点 当cur与parent的关系和parent与grandfather的关系不一致时需要进行双旋 以上结构中cur是parent的左子树parent是grandfather的右子树关系不一致要进行双旋。 同样的讲解一下变色和旋转的合理性 一次插入过程中走到这一步说明前面一定经过了uncle为红色的情况而对uncle为红色的情况进行变色并不会对任何路径的黑色节点数目造成影响因此目前还是符合黑色节点数目相同规则的。 同为parent的子树以cur和A为根的路径黑节点数目相同 同为cur的子树以B和C为根的路径黑节点数目相同 由于cur是红节点所以以ABC为根的路径黑节点数目相同 相同的手段由于parent是红节点所以A与uncle为根的路径的黑节点数目相同 因此ABCuncle为根的路径黑节点数目都相同 进行双旋会把C子树交给grandfather做子树而C与uncle黑节点数目相同不违背规则也会把B交给parent做子树 A与B黑节点数目相同不违背规则 旋转后cur作新根grandfather与parent作为左右子树grandfather为根的路径整体上就会比以parent为根的路径多出一个黑节点(grandfather本身) 因此将grandfather改为红节点来平衡cur左右子树的黑节点而红色节点不能连续出现再把cur改为黑节点 以上单旋和双旋的变色看似复杂其实最后都是把新根的颜色变为黑色新根的左右子树变为红色。由于我们旋转后新根都是黑节点所以不会影响上层可以直接跳出循环。
代码如下
当parent grandfather-_left
else//uncle为黑节点 (旋转)
{if (cur parent-_left){RotateR(grandfather);//右单旋parent-_col BLACK;//变色grandfather-_col RED;//变色}else{RotateL(parent);//左右双旋 - 左单旋RotateR(grandfather);//左右双旋 - 右单旋cur-_col BLACK;//变色grandfather-_col RED;//变色}break;//旋转后一定平衡
}当parent grandfather-_right
else//uncle为黑节点 (旋转)
{if (cur parent-_right){RotateL(grandfather);//左单旋parent-_col BLACK;//变色grandfather-_col RED;//变色}else{RotateR(parent);//右左双旋 - 右单旋RotateL(grandfather);//右左双旋 - 左单旋cur-_col BLACK;//变色grandfather-_col RED;//变色}break;//旋转后一定平衡
}insert总代码
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;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-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在){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;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){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;//在循环内部不判断root情况统一处理return true;
}总代码展示
红黑树总代码 RBTree.h
#pragma once
#include iostream
#include assert.h
using namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;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-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在){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;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){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;//在循环内部不判断root情况统一处理return true;}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root nullptr)return 0;;return _Size(root-_left) _Size(root-_right) 1;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}//中序void InOrder(){_InOrder(_root);cout end endl;}int Height(){return _Height(_root);}private://中序void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first - ;_InOrder(root-_right);}//求高度int _Height(Node* root){if (root nullptr)return 0;return max(Height(root-_left), Height(root-_right)) 1;}Node* _root nullptr;
};
