做网站图片要求,微信小程序组件库,建设网站需要买什么手续,做门窗的建网站怎么赚钱文章目录 红黑树概念红黑树的性质#xff1a; 红黑树的插入操作情况一情况二情况三 小总结红黑树的验证红黑树的删除一.删除单孩子节点1. 删除节点颜色为黑色2. 删除颜色为红色 二. 删除叶子节点1. 删除节点为红色2.删除节点为黑色2.1兄弟节点为黑色#xff0c;有孩子节点性质 红黑树的插入操作情况一情况二情况三 小总结红黑树的验证红黑树的删除一.删除单孩子节点1. 删除节点颜色为黑色2. 删除颜色为红色 二. 删除叶子节点1. 删除节点为红色2.删除节点为黑色2.1兄弟节点为黑色有孩子节点并且孩子节点再兄弟节点的同一侧2.2. 兄弟节点为黑色有孩子节点并且孩子节点再兄弟节点的另一侧2.3 兄弟节点为黑色无孩子节点或者孩子节点都为黑色。2.4 兄弟节点为红色 代码实现 红黑树概念
先来回顾一下AVL树在我们讲解AVL树的时候我们会设置一个平衡因子来控制我们树的高度通过右子树-左子树这种方式来表示我们平衡因子的大小如果bf的绝对值大于·1那就说明不平衡此时需要旋转处理从而让树达到平衡。绝对平衡
而红黑树是设置一个颜色并通过一些性质来是红黑树达到近似平衡。每个节点不是红色的就是黑色的
红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的 重点不能有连续的红色节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点重点每条路径黑色节点数量相同每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
这里对第三点做个解释不能存在连续的红色节点。同时有了上面的性质限制我们就可以保证二叉树最长路径不超过最短路径的两倍。为什么呢 红黑树中我们可以吧每一个空节点代表为一条路径所以上图我们一共就有11条路径那么每一条路径中我们黑色节点的数量都为两个虽然空节点代表黑色这里不加入计算那么最短路径就是全为黑色节点的路径最长路径就是一黑一红交错的路径。所以由于我们第四条性质限定了我们每条路径的黑色节点数量必须相同所以才会有最长路径不超过最短路径的两倍这样一个结论。
为了方便以后实现map和set的封装代买实现都是添加了一个头节点。
红黑树的插入操作
在了解插入操作的时候我们要明确新增的节点一定为红色。 由于根节点一定为黑色又要保证第四条性质的黑数同所以当我们新增的节点一定为黑色。 同时为了方便描述我们把新增节点命名为ccur新增节点的父节点为pparent父节点的兄弟节点命名为uuncleggrandfather爷爷节点
情况一
当我们了解了上面的知识过后我们来分析一下我们左边插入和右边插入都没有问题。 看下面的情况 如果我们这样插入呢由于性质三规定了不能存在连续的红色节点所以此时我们需要调整那如何调整呢
情况一c为新增u为红p为红g为黑也只能是黑色不可能有连续的红色节点
解决方案此时我们只需要让u和p变黑然后g变红把g赋值给c继续向上调整。
我们先来看一个简单的栗子 上图是我们g节点为根的情况还有可能为一棵树的子树所以我们还需要继续向上调整。如图 情况二
c为新增u存在且为黑/u不存在p为红g为黑 解决方法旋转完之后只需要让g变红色p变为黑色即可。同时我们的情况二是由情况一变过来的。 情况三
c为新增但是p的另一侧u存在且为黑/u不存在p为红g为黑 解决方法双旋完之后让g变为红色c变为黑色。双旋逻辑和AVL树一样只不过这里我们并不需要维护平衡因子了。
小总结
插入过程种当我们c为红色p为红色的时候违反了性质三所以我们需要进行处理所以处理的结束条件就是当我们p为黑色的时候就不需要处理了。情况二和情况三旋转完之后已经不需要处理了。
原因
旋转的时候g有两种情况1.根 2. 子树 作为根的话旋转完毕就结束了 作为子树它的父节点一定为黑色节点所以当我们旋转完之后把c变为g的位置的时候p的指向为黑色节点所以也不需要继续调整了。
由于我们新增节点必须为红色旋转的条件是一黑一红而且旋转只能由情况一转化为情况二才进行旋转那么既然有红色节点那么g肯定为黑色那么g-_parent节点也一定为黑色如果g-_parent是红色的话那我们不就相当于新增了一个黑色节点了吗这样是不行的。所以旋转完之后没有必要继续调整。
代码实现
bool insert(const K key){//只有一个头节点if (pHead-_parent pHead){pHead-_parent new Node(key);pHead-_parent-_parent pHead;pHead-_parent-_col BLACK;return true;}Node* cur pHead-_parent;Node* parent cur-_parent;while (cur){if (key cur-_data){parent cur;cur cur-_left;}else if (key cur-_data){parent cur;cur cur-_right;}elsereturn false;}cur new Node(key);cur-_parent parent;//连接新增节点与父节点的关系if (parent-_data key)parent-_left cur;elseparent-_right cur;Node* grandfather parent-_parent;Node* uncle nullptr;//满足parent的颜色是红色节点 并且 parent不是哨兵节点。while (parent-_col RED parent ! pHead){if (grandfather-_left parent)uncle grandfather-_right;elseuncle grandfather-_left;if (uncle uncle-_col RED) //p红色u红色{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent grandfather-_parent;grandfather parent-_parent;}else if ((uncle uncle-_col BLACK) || uncle nullptr){//右单旋if (grandfather-_left parent parent-_left cur){RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;}else if (grandfather-_right parent parent-_right cur){//左单旋RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else if (grandfather-_left parent parent-_right cur){//左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}else if (grandfather-_right parent parent-_left cur){//右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}else{assert(false);}}pHead-_parent-_col BLACK;return true;}红黑树的验证
我们只需要根据性质进行验证即可
根节点为黑色不能存在连续的红色节点每条路径中黑色数量相同
那如何求每一条路径的黑色节点数量呢每次遍历到空节点其实就是一条路径完全走完了。
代码实现 bool IsRBTree(){return _isRBTree(pHead-_parent);}
int Height(){return TreeHigh(pHead-_parent);}
private:int TreeHigh(Node* root){if (root nullptr || root-_parent root)return 0;return max(TreeHigh(root-_left),TreeHigh(root-_right)) 1;}bool _isRBTree(Node* root){//只有一个头节点if (root-_parent root)return true;Node* LeftMost root;if (root-_col ! BLACK){cout 违反性质二根节点为黑色 endl;return false;}int k 0;while (LeftMost){if (LeftMost-_col BLACK)k;LeftMost LeftMost-_left;}return IsSameBlack(root-_left,1,k) IsSameBlack(root-_right, 1, k);}bool IsSameBlack(Node* root, size_t cnt, int k){if (root nullptr){cout 当前路径黑色节点数量 cnt endl;if (cnt ! k){cout 违反性质四每条路径中的黑色节点数量不一样 endl;return false;}return true;}if (root-_col BLACK)cnt;Node* parent root-_parent;if (parent ! pHead parent-_col RED root-_col RED){cout 违反性质三不能有连续的红色节点 endl;return false;}return IsSameBlack(root-_left, cnt, k) IsSameBlack(root-_right, cnt, k);}红黑树的删除
红黑树的删除和二叉搜索树的删除类似都有三种情况
删除叶子节点删除单孩子节点删除双孩子节点
我们先来回忆以下双孩子节点如何删除我们需要去找一个替换节点来替换此时的删除节点那么这个替换节点需要满足
比要删除的左子树大比要删除的右子树小
所以我们有两种选择1. 左子树的最大节点 2. 右子树的最小节点。接下来我实现的都是找右子树的最小节点。
那么当我们找到这个可替换节点的时候无非就是两种情况 1. 可替换节点为叶子节点 2. 可替换节点为单孩子节点。
那么其实我们删除两个孩子节点的操作当我们把可替换节点的值赋值给要删除节点的时候其实就变为了删除叶子节点或者删除单孩子节点。
有了上面的理解我们可以值需要梳理删除叶子节点和删除单孩子节点的思路即可。
这里我们先来说删除单孩子节点。
一.删除单孩子节点
这里分为两种情况
删除节点颜色为黑色删除节点为红色
1. 删除节点颜色为黑色
此时我们那个孩子节点的颜色只有一种情况那就是红色节点那么由于我们删除过后会少一个黑色节点所以当我们连接新的节点过后要把这个红色节点变为黑色。 2. 删除颜色为红色
那它的孩子节点一定为黑色直接连接孩子节点与父节点的关系然后直接删除即可。
二. 删除叶子节点
1. 删除节点为红色
直接删除即可然后需要把父节点对应的左右孩子置空不然后面会访问野指针O.0!
2.删除节点为黑色 如上图如果我们把节点6删除过后那最左边的路径黑色节点就会少一个这样就违反了第四条性质。这时候我们就要分类讨论它的兄弟节点的颜色了。
2.1兄弟节点为黑色有孩子节点并且孩子节点再兄弟节点的同一侧
这里我们都以s称为兄弟节点sr就是兄弟节点的右子树。 如上图进行单选的时候我们需要把颜色依次赋值sr-_col s-_cols-_col p-_colp-_col BLACK。
同理进行右单旋也是如此这里就不再赘述了。
2.2. 兄弟节点为黑色有孩子节点并且孩子节点再兄弟节点的另一侧
这个时候就是双旋了。 双旋唯一不一样的就是颜色的变换这个时候我们直接让 sl-_col p-_colp-_col BLACK这时候直接让兄弟节点的孩子节点复制父亲节点的颜色然后父亲节点变黑最后进行双旋操作即可。
2.3 兄弟节点为黑色无孩子节点或者孩子节点都为黑色。
这个时候需要先把兄弟节点变红然后再观察现在的parent父亲节点
如果父亲节点为红色或者为根直接让父亲节点变为黑色最后删除节点即可。如果父亲节点为黑色并且不是根节点的话就要继续观察然后重复我们删除节点为黑色的这个操作 2.4 兄弟节点为红色
此时直接交换兄弟节点与父亲节点的颜色然后对p父亲节点进行向着删除节点的方向进行旋转如果删除节点再p左侧就进行左旋如果删除节点再p右侧就进行右旋。然后继续观察当前的删除节点继续重复删除节点为黑色的操作 代码实现
//进来的都是叶子节点为黑色的情况那么如果叶子节点为黑色的话一定有兄弟节点。不然违反了性质4.
void ChangeColor(Node* cur, Node* parent)
{Node* uncle nullptr;//1. 如果uncle是黑色节点并且它有红色的孩子节点旋转的状态//2. 如果uncle是黑色节点并且他的孩子都是黑色节点NULL也算那么就把兄弟节点变为红色同时向上遍历双重黑色节点//3. 如果uncle是红色节点交换兄弟和parent的颜色然后向删除节点的方向旋转然后继续观察兄弟节点while (parent ! pHead){if (parent-_left cur){uncle parent-_right;}else{uncle parent-_left;}if (uncle-_col BLACK){//进行右单旋if (parent-_left uncle uncle-_left uncle-_left-_col RED){Node* uncle_left uncle-_left;//变色uncle_left-_col uncle-_col;uncle-_col parent-_col;parent-_col BLACK;//旋转RotateR(parent);break;}else if (parent-_right uncle uncle-_right uncle-_right-_col RED){//进行左单旋Node* uncle_right uncle-_right;//变色uncle_right-_col uncle-_col;uncle-_col parent-_col;parent-_col BLACK;RotateL(parent);break;}else if (parent-_left uncle uncle-_right uncle-_right-_col RED){//进行左右双旋Node* uncle_right uncle-_right;//变色uncle_right-_col parent-_col;parent-_col BLACK;RotateL(uncle);RotateR(parent);break;}else if (parent-_right uncle uncle-_left uncle-_left-_col RED){//进行右左双旋Node* uncle_left uncle-_left;//变色uncle_left-_col parent-_col;parent-_col BLACK;RotateR(uncle);RotateL(parent);break;}else if ((uncle-_left nullptr uncle-_right nullptr) || (uncle-_left uncle-_right uncle-_left-_col BLACK uncle-_right-_col BLACK)){//兄弟节点的孩子全为黑色节点//把兄弟节点变为红色然后双重黑色节点往上调继续遍历uncle-_col RED;//遍历到根节点或者红色节点把节点变为黑色退出即可。if ((uncle-_parent ! pHead-_parent uncle-_parent-_col RED) || (uncle-_parent pHead-_parent)){uncle-_parent-_col BLACK;break;}else{cur uncle-_parent;parent cur-_parent;}}}else if (uncle-_col RED){//交换uncle和parent的颜色,Parent变为黑色然后向删除节点方向旋转再看双重黑节点uncle-_col parent-_col;parent-_col RED;if (parent-_left cur){RotateL(parent);}else{RotateR(parent);}cur cur;parent cur-_parent;}}}bool erase(const K key)
{//只有一个哨兵节点无法删除。if (pHead-_parent pHead)return false;Node* cur pHead-_parent;Node* parent pHead;while (cur){if (key cur-_data){parent cur;cur cur-_left;}else if (key cur-_data){parent cur;cur cur-_right;}else{//叶子节点if (cur-_left nullptr cur-_right nullptr){//如果删除的是根节点直接让哨兵的parent指针指向自己。if (parent pHead){pHead-_parent pHead;delete cur;return true;}else if (cur-_col RED)//红色的话直接删除{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}delete cur;return true;}else if (cur-_col BLACK) //如果删除的节点为黑色节点{ChangeColor(cur,parent);if (parent-_left cur)parent-_left nullptr;elseparent-_right nullptr;delete cur;return true;}}else if (cur-_left nullptr) //左边为空{//删除的为根节点直接改变pHead的指向即可。if (parent pHead){pHead-_parent cur-_right;if (cur-_right){cur-_right-_col BLACK;cur-_right-_parent pHead;}delete cur;return true;}else if (cur-_col BLACK){//判断为父亲节点的哪一边if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}//如果删除的单孩子节点为黑色就需要把删除节点的右孩子变为黑色。如果有右孩子的话if (cur-_right){cur-_right-_col BLACK;cur-_right-_parent parent; //如果有的话别忘了连接父节点}delete cur;return true;}else if (cur-_col RED){//判断为父亲节点的哪一边if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}//如果删除的单孩子节点为红色直接删除delete cur;return true;}}else if (cur-_right nullptr){//删除的为根节点直接改变pHead的指向即可。if (parent pHead){pHead-_parent cur-_left;if (cur-_left){cur-_left-_col BLACK;cur-_left-_parent pHead;}delete cur;cur nullptr;return true;}else if (cur-_col BLACK){//判断为父亲节点的哪一边if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}//如果删除的单孩子节点为黑色就需要把删除节点的左孩子变为黑色如果有左孩子的话if (cur-_left){cur-_left-_col BLACK;cur-_left-_parent parent;}delete cur;cur nullptr;return true;}else if (cur-_col RED){//判断为父亲节点的哪一边if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}//如果删除的单孩子节点为红色直接删除delete cur;cur nullptr;return true;}}else //双孩子节点{//如果删除节点为红色if (cur-_col RED){Node* RightMinP cur;Node* RightMin cur-_right;while (RightMin RightMin-_left){RightMinP RightMin;RightMin RightMin-_left;}cur-_data RightMin-_data;//如果RightMin的颜色为黑色if (RightMin-_col BLACK){//如果RightMin有右孩子那么一定为红色的删除RightMin之后要把他的右孩子变为黑色。if (RightMin-_right){RightMin-_right-_col BLACK;RightMin-_right-_parent RightMinP;// 如果有红色节点的uha直接连接并且赋值为黑色if (RightMinP-_left RightMin){RightMinP-_left RightMin-_right;}else{RightMinP-_right RightMin-_right;}delete RightMin;}else //如果没有的话那么转化为删除黑色叶子节点{ChangeColor(RightMin, RightMinP);if (RightMinP-_left RightMin){RightMinP-_left nullptr;}else{RightMinP-_right nullptr;}delete RightMin;}return true;}else//如果RightMin的颜色为红色直接删除连接右孩子{if (RightMinP-_left RightMin){RightMinP-_left RightMin-_right;}else{RightMinP-_right RightMin-_right;}if (RightMin-_right){RightMin-_right-_parent RightMinP;}delete RightMin;return true;}}else//如果删除节点为黑色{Node* RightMinP cur;Node* RightMin cur-_right;while (RightMin RightMin-_left){RightMinP RightMin;RightMin RightMin-_left;}cur-_data RightMin-_data;//如果RightMin的颜色为黑色if (RightMin-_col BLACK){if (RightMin-_right){//如果RightMin有右孩子那么一定为红色的删除RightMin之后要把他的右孩子变为黑色。RightMin-_right-_col BLACK;RightMin-_right-_parent RightMinP;if (RightMinP-_left RightMin){RightMinP-_left RightMin-_right;}else{RightMinP-_right RightMin-_right;}delete RightMin;return true;}else //如果没有的话那么转化为删除黑色叶子节点{ChangeColor(RightMin, RightMinP);if (RightMinP-_left RightMin){RightMinP-_left nullptr;}else{RightMinP-_right nullptr;}delete RightMin;}return true;}else//如果RightMin的颜色为红色直接删除连接右孩子{if (RightMinP-_left RightMin){RightMinP-_left RightMin-_right;}else{RightMinP-_right RightMin-_right;}if (RightMin-_right){RightMin-_right-_parent RightMinP;}delete RightMin;return true;}}}}}return false;
}
