自己做的网站怎样链接数据库,贵阳市做网站公司,太原做网页软件,山东济南建设网【C笔记】红黑树的简易实现 一、什么是红黑树以及红黑树好在哪里1.1、什么是红黑树1.2、红黑树比AVL树好在哪里#xff1f; 二、红黑树的模拟实现2.1、红黑树的插入2.2、仅变色调整2.3、变色单旋调整2.4、变色双旋调整 一、什么是红黑树以及红黑树好在哪里
1.1、什么是红黑树… 【C笔记】红黑树的简易实现 一、什么是红黑树以及红黑树好在哪里1.1、什么是红黑树1.2、红黑树比AVL树好在哪里 二、红黑树的模拟实现2.1、红黑树的插入2.2、仅变色调整2.3、变色单旋调整2.4、变色双旋调整 一、什么是红黑树以及红黑树好在哪里
1.1、什么是红黑树
红黑树本质上也是一颗搜索二叉树但它在搜索二叉树的规则上有新添了一些额外的规则使得它比普通的搜索二叉树甚至是AVL树的性能更好。
简单来说红黑树是这样一棵树红黑树是一棵搜索二叉树它的每个节点上增加了一个存储位来表示每个节点的颜色颜色要么是红色要么是黑色。并且树中没有连续的红色节点且红黑树中确保没有任何一条路径长度会大于其他路径的两倍。
红黑树有以下几个主要特性 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的(即没有连续的红节点) 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 大家可能看完会感到疑惑上面的特性中好像并没有与路径长度相关的啊那怎么保证上面说到的确保没有任何一条路径长度会大于其他路径的两倍呢
其实这个条件我们并不需要特意的去关注因为只要满足了特性3和特性4这个条件自然就满足了。
我们先来看特性4中所说的任意路径的黑色节点数量都一样这个其实已经在一定程度上限制了每条路径的长度了因为如果某棵红黑树中都是黑色节点的话那么每一条路径的长度都是一样的比如说下面这棵树 想想就知道上面这棵树一定是满足红黑树的条件的。
那么在每条路径的黑节点数量都相同的情况下要加入红节点来使路径变长应该怎么加才能使路径最长呢
由于特性3的限制即不能有连续的红节点并且根节点一定是黑节点我们要使一条路径最长的唯一添加方式就只有像下面这样 只能这样一直红黑相间的加并且到最后红黑节点的数量一定是相同的即最长的路径是每条路径黑色节点的两倍。 而每条路径的黑色节点数量都是相同的所以若是存在最短路径(这里的最短路径不是针对某一棵红黑树而是在合法范围内能达到的最短路径)那么这条路径上的节点一定是全黑的。
所以这也就满足了最长路径不超过最短路径的二倍的条件了。
最后还有一点是需要特别注意的 红黑树的路径定义其实和其他树的路径的定义不一样其他树的路径定义都是由根节点到叶子结点而红黑树的路径定义则是由根节点到空。
我这里先说原因也就是为什么需要这样然后再说如果不这样的话会导致的一个问题。
原因 因为红黑树并不像AVL树一样使用一个平衡因子来控制整棵树的高度所以如果红黑树的路径定义和其他树一样就会出现下面这种极端情况 如果路径定义的时由根节点到叶子结点那么这棵树的高度就有可能向上面一样变得很高但是节点的数量并不多并且只要路径中的黑色节点相同它有可能一直延伸下去 如果树的高度变得很高我们的查找效率就会变低这时候如果将路径定义成由根节点到空的话就能很好的规避这种情况了 这样的话上图红线标出来的这条路径就不合法了就需要调整。
同时这样定义其实也是怕我们判断错误如果路径的定义还是像其他二叉树一样那我们就会认为上图的这棵树并没有出错的地方就判断错了。
1.2、红黑树比AVL树好在哪里
但是红黑树到底比AVL树好在哪里呢
我们知道AVL树是是通过平衡因子来控制右子树与左子树的高度差不超过1的既然高度差不超过1那说明AVL树是一棵近似完全二叉树甚至是满二叉树的树是一个严格平衡的树 虽然它的高度控制的很好但是我们在控制高度的时候需要进行各种旋转操作在旋转的过程中还需要进行很多的判断这相对于查找的判断确实多了很多。
因为AVL树对于高度的严格控制在一些极端情况下我们可能没插入一个节点就需要旋转一次这其实是很费时间的。
而红黑树对于高度的控制没有AVL树一样严格这其实就省去了很多旋转的开销虽然它的高度差较与AVL树更大但也只是查找的层数多一点而已相对于AVL树需要进行繁琐的旋转旋转中还有很多的判断显然查找更多层其实也并不赖。
所以总体而言红黑树较于AVL树还是有一点优势的虽然优势并不是很大但好过没有。
二、红黑树的模拟实现
红黑树节点
// 颜色我们用枚举来定义比较形象一点
enum Color {RED,BLACK
};// 红黑树节点
template class T
struct RBTreeNode {RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _val;Color _col;// 构造RBTreeNode(const T val):_left(nullptr), _right(nullptr), _parent(nullptr), _val(val), _col(RED) // 新增节点要给红色{}
};因为红黑树也是要旋转的所以和AVL树一样也需要用到三叉链。
然后我们同样只需要在红黑树类里面封装一个根节点即可
template class T
calss RBTree{
public :typedef RBTreeNodeT Node;// …………
private :Node* _root;}因为红黑树的删除操作实在太过繁琐而且也在考察范围所以我们这里就只实现红黑树的插入操作即可。
2.1、红黑树的插入
红黑树的本质是一颗二叉排序树所以和普通的二叉排序树一样还是需要先找到插入的位置。
但是红黑树有红色和黑色两种颜色我们在插入新节点的时候新节点是选择红色还是黑色呢
其实这个问题好好想一下就知道了因为红黑树最主要的特性就是每条路径的黑色节点数量相同如果新增节点选择黑色那么这就会导致有一条路径的黑色节点数量不同了这影响到的棵树整棵树啊这样的话需要再次调整的话就需要对整棵树进行调整了非常麻烦。
所以我们新增的节点一律选择红色如果后面需要调整的话调整的幅度也不会太大。
先给出查找插入位置和插入逻辑的代码这和普通的搜索二叉树一样
// 插入
bool insert(const T val) {if (nullptr _root) {_root new Node(val);// 根节点一定要给黑色_root-_col BLACK;cout insert- val endl;return true;}// 先插入新节点Node* cur _root;Node* parent nullptr;while (cur) {if (val cur-_val) {parent cur;cur cur-_left;}else if (val cur-_val) {parent cur;cur cur-_right;}else {return false;}}cur new Node(val);if (val parent-_val) {parent-_left cur;}else {parent-_right cur;}cur-_parent parent;
}在插入新节点后我们还需要检查一下是否需要进行调整也就是检查一下红黑树的结构是否被破坏了。
有一种情况是最轻松的也就是结构没有被破坏当我们插入的新节点的父亲是黑色的时候 这时候其实并不用管新节点插入在父亲的左边还是右边因为都是一样的我们直接返回即可。
// 检查是否需要调整Node* grandfather parent-_parent;Node* uncle nullptr;if (parent-_col BLACK) {// 如果父亲是黑色则不用调整直接返回return true;}2.2、仅变色调整
还有些情况是需要进行变色或旋转调整的当新插入节点的父亲节点是红色的时候我们是无论如何都需要调整的但有些调整比较轻松有些调整就比较复杂有可能是只需要变色即可有可能是需要变色加上旋转调整。
我们这里还是先从轻松地说起即仅需要变色的情况。 如上图当新节点的父亲是红色且叔叔节点(uncle)即父亲的兄弟节点“存在”且为红的时候grandfather为黑(此时的grandfather已定位黑)我们就仅需要变色处理即可。 具体的变色方案是 将parent和uncle都变黑将grandfather变红 这时候
但是我们还不能直接结束因为上面所画的只是一个情况也有可能当我们将grandfather变红之后发现grandfather的父亲也是一个红节点(因为当前的祖父节点不一定是根)这时候就有违反规则了。
所以我们还需要继续向上调整我们画出个抽象图可能更好理解 如上图当cur的父亲节点§为红色并且父亲节§点和叔叔节点(u)都为红色时就需要进行上述变色调整调整完当前层的时候还需要检查上一层。
只需要将g当成新的cur然后一直迭代的进行判断。
但是这样调整为什么就能解决问题了呢 这是因为节点g其实是p和u所在的这两条路径“共用”的 所以这样调整后看似是减少了两个黑色节点只增加了一个黑色节点好像是少了一个黑色节点但是从路径中的黑色节点数量来看其实是并没有减少的。
注意再向上层迭代的过程中也有可能出现其他的情况有可能他还是只需要变色有可能是需要变色旋转调整所以还需要结合下面讲到的调整方式相结合。
2.3、变色单旋调整
当cur为红p为红g为黑u不存在/u存在且为黑时我们就不仅仅需要变色了还需要进行旋转调整具体是单旋还是双旋还需要看情况。
首先先把原理讲清楚就是为什么这样的情况需要旋转。 首先当u节点不存在时此时的cur必定是新增节点 并且p节点在增加cur节点之前也一定是没有孩子的因为p已经是红色了而红节点的孩子必须是黑节点所以如果p有孩子节点就破坏了红黑树的规则了。
此时无论怎样变色都不不能解决问题的因为现在的最长路径已经超过了最短路径的两倍了只能通过调整高度来解决问题了。
如果p是g的左孩子并且cur也是p的左孩子就要进行右单旋
调整完后变色的方案是p变黑g变红。
而如果p是g的右孩子且cur是p的右孩子就要进行左单旋。
但为什么当u节点存在且为黑的时候也需要进行旋转呢 首先可以确定的是当存在且为黑的时候cur一定不是新增节点因为如果cur实现增节点的话那在新增cur之前整棵树就不符合红黑树的规则了 所以cur原来一定是黑节点是下层调整上来的时候变红的本质是少了一个黑节点。 并且子树abcde也一定是不为空的不然就不符合规则了 那我们就来细细分析一下首先cur是从下面调整上来变成的红色所以cur这可子树一定是符合规则的所以cur就不能再变色了再变色的话不就是走回头路了吗。 同时p节点也是不能变色的因为如果p变为黑色看似是不上了之前少了的那个黑节点但是子树c的每条路径上又多出了一个黑节点也是不符合要求了。 同时u更是不能变色的啦及解决不了问题还会使g的右子树都少了一个黑色节点同理g也不能变色。
所以我们就只能通过旋转来解决问题了 然后我们观察发现ab子树所在的路径都少了一个黑节点c子树的黑色节点是不变的所以变色方案也是和上面一样p变黑g变红 同样左单选的情况也是类似的分析。
先给出左单旋和右单选的代码
// 左单旋
void RotateL(Node* parent) {Node* subRight parent-_right;Node* subRightL subRight-_left;Node* parent_parent parent-_parent;parent-_right subRightL;if (subRightL) {subRightL-_parent parent;}subRight-_left parent;parent-_parent subRight;if (parent _root) { // 如果当前的parent是根_root subRight;subRight-_parent nullptr;}else {// 如果当前的parent还不是根if (parent parent_parent-_left) {parent_parent-_left subRight;}else {parent_parent-_right subRight;}subRight-_parent parent_parent;}}// 右单旋
void RotateR(Node* parent) {Node* subLeft parent-_left;Node* subLeftR subLeft-_right;Node* parent_parent parent-_parent;parent-_left subLeftR;if (subLeftR) {subLeftR-_parent parent;}subLeft-_right parent;parent-_parent subLeft;if (parent _root) { // 如果当前的parent为根_root subLeft;subLeft-_parent nullptr;}else {// 如果当前的parent不为根if (parent parent_parent-_left) {parent_parent-_left subLeft;}else {parent_parent-_right subLeft;}subLeft-_parent parent_parent;}
}
其实就是复制AVL树的左单旋和右单旋。
2.4、变色双旋调整
然后就到了双旋的情况了其实红黑树的双旋和AVL树的双旋是差不多的只是多了变色这一步而已。 如下图当p为g的左孩子并且cur为p的右孩子时我们使用单旋是解决不了问题的 此时我们可以像AVL树一样先对p进行左单旋将其转化成一个单纯的右单旋的情况 此时我们将cur和p调换位置不就变成了和上面单旋处理一样的情况了吗 所以我们再针对g做一次右单旋不就解决高度不平衡的问题了吗
完整过程 此时的变色方案就和单选的有所不同了是将cur变为黑色g变为红色 为什么不同其实也很好理解 如上图我们在对g进行左单旋后是变成了上图左端的形式我们其实是将p“看作”是cur来对g进行单旋的所以我们可以认为是p和cur调换了位置。
所以在单选和双旋中g都变成了红色但是变黑色的却分别是p和cur带着这样的理解我们其实会发现单选和双旋其实本质也是一样的。
最后给出完整的插入代码
// 插入
bool insert(const T val) {if (nullptr _root) {_root new Node(val);// 根节点一定要给黑色_root-_col BLACK;cout insert- val endl;return true;}// 先插入新节点Node* cur _root;Node* parent nullptr;while (cur) {if (val cur-_val) {parent cur;cur cur-_left;}else if (val cur-_val) {parent cur;cur cur-_right;}else {return false;}}cur new Node(val);if (val parent-_val) {parent-_left cur;}else {parent-_right cur;}cur-_parent parent;// 检查是否需要调整Node* grandfather parent-_parent;Node* uncle nullptr;if (parent-_col BLACK) {// 如果父亲是黑色则不用调整直接返回return true;}else {while (parent parent-_col RED) {grandfather parent-_parent;if (parent grandfather-_left) {uncle grandfather-_right;}else {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 (parent grandfather-_left) {if (cur parent-_left) { // 右单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else { // 左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}}else {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;
}
