鄂尔多斯市东胜区城市建设局网站,提供医疗网站建设,重庆建设网站公司哪家好,wordpress后台添加友情链接✨✨ 欢迎大家来到贝蒂大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;数据结构与算法 贝蒂的主页#xff1a;Betty’s blog 1. 红黑树的介绍
1.1. 红黑树的引入
我们前面学习了AVL树#xff0c;… ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏数据结构与算法 贝蒂的主页Betty’s blog 1. 红黑树的介绍
1.1. 红黑树的引入
我们前面学习了AVL树知道其本质是通过旋转操作来确保每个节点的左右子树高度差不超过 1以此解决数据有序或接近有序时二叉搜索树退化为单边树而导致查找效率低下的问题。然而当插入数据量过大时频繁的旋转操作同样会使效率降低。为应对这一问题就有人提出了一种更为特殊的树——红黑树。
红黑树是一种自平衡的二叉查找树查找效率高。它由Rudolf Bayer于 1978 年发明当时被称为平衡二叉B树。后来在 1978 年Leo J. Guibas 和 Robert Sedgewick对其进行了修改形成了如今的红黑树。
1.2. 红黑树的特点
首先红黑树属于二叉搜索树其特点是在每个节点额外增加了一个存储位用于记录节点的颜色该颜色可以是 RED也可以是 BLACK。 并且红黑树通过对任意一条从根到叶子的简单路径上颜色的约束能够保证最长路径不会超过最短路径的二倍从而实现近似平衡减少旋转的效果。其具体特点如下 节点颜色只有黑色与红色两种颜色。根节点一定是黑色。空节点null一定为黑色并且在红黑树中认为null节点才是叶子节点。红色节点的子节点和父节点一定为黑色。从任一节点到叶子节点的所有路径都包含相同数目的黑色节点。 为什么上述规则能保证红黑树最长路径不超过最短路径的两倍
具体来说根据上述规则可以得出最短路径即为全是黑节点的路径最长路径则是一个红节点接着一个黑节点。当从根节点到叶子节点的路径上黑色节点数量相同时最长路径恰好是最短路径的两倍。
2. 红黑树的功能
以下是红黑树常见的功能 红黑树的插入。红黑树的查找。红黑树的删除。 3. 红黑树的结构
3.1. 红黑树的节点
红黑树的节点本质与二叉搜索树的节点差不多所以肯定有三个成员变量左子树_left右子树_right键值_kv并且键值我们采用KV模型的形式。并且还有一个表示节点颜色的变量_col以及一个父节点_parent。并且为了增加代码的可读性我们可以定义一个枚举来表示颜色。当然为了适配不同的类型我们同样需要定义一个模版.。
templateclass K,class V
struct RBTreeNode
{RBTreeNode(const pairK,V kv pairK,V(), Color col RED):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(col)//默认为红节点{}RBTreeNodeK, V* _left;//左子树RBTreeNodeK, V* _right;//右子树RBTreeNodeK, V* _parent;//父节点pairK, V _kv;//键值Color _col;//颜色
};为什么插入新节点的颜色默认是红色而不是黑色呢
若插入的是黑色节点会导致插入路径的黑色节点数量增加破坏原每条路径黑色节点数量相同的平衡特性需要对所有路径进行调整非常麻烦。若插入节点为红色则需分情况讨论。当插入节点的父节点为黑色时不会违反红黑树规则无需处理。而当插入节点的父节点为红色时由于红黑树不能有连续的红色节点此时就需要进行调整。但是因为只需调整该路径所以明显更简单。
综上所述红黑树插入节点默认设为红色能在一定程度上减少违反规则的情况同时降低调整树结构的复杂性。
3.2. 红黑树
然后我们就可以通过节点来定义红黑树并将根节点初始化为空。
templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public://...具体功能
private:Node* _root nullptr;//根节点
};4. 红黑树的初始化与销毁
4.1. 构造函数/拷贝构造/赋值重载
首先我们直接定义一个无参的构造函数因为我们在定义拷贝构造之后编译器就不会在生成默认的构造函数了。
RBTree()
{}之后我们可以利用递归来实现一个拷贝构造函数。
RBTree(const RBTreeK, Vt)
{_root copy(t._root);
}
Node* copy(Node* root)
{// 如果原始节点为空直接返回空指针if (root nullptr){return nullptr;}// 为新节点分配内存并拷贝原始节点的值Node* newnode new Node(root-_kv);// 递归拷贝左子树newnode-_left copy(root-_left);// 递归拷贝右子树newnode-_right copy(root-_right);// 将新节点的父节点指针置为空newnode-_parent nullptr;// 拷贝原始节点的颜色信息newnode-_col root-_col;// 如果新节点的左子节点存在设置其父节点为新节点if (newnode-_left){newnode-_left-_parent newnode;}// 如果新节点的右子节点存在设置其父节点为新节点if (newnode-_right){newnode-_right-_parent newnode;}
}最后我们通过一个简单的方式实现赋值重载——通过形参调用拷贝构造出一个临时变量然后交换this所指向的变量这样原本this所指向的对象出了作用域就会销毁间接实现了实现赋值重载。
RBTreeK, V operator (const RBTreeK, V t)
{this-swap(_root, t._root);return *this;
}4.2. 析构函数
析构函数需要借助递归释放所有节点而为了方便我们传参我们可以定义子函数来帮助我们解决。
~RBTree()
{Destroy(_root);
}
void Destroy(Node* root)
{if (root nullptr){return;}//递归销毁左子树Destroy(root-_left);//递归销毁右子树Destroy(root-_right);//销毁根节点delete root;root nullptr;
}5. 红黑树的功能实现
不论是红黑树的插入还是删除操作都需要用到旋转操作如果你还不知道旋转操作的具体内容可以先看看这篇文章——AVL树。当然具体的旋转操作也看到也有细微的区别因为红黑树并不存在平衡因子但是主体思路肯定不会改变。
5.1. 红黑树的插入
向红黑树进行插入首先是先找到需要插入的位置这个逻辑与二叉搜索树类似这里就不在赘述。找到之后插入默认的红节点此时就可以分为五种情况来讨论
为了方便叙述我们首先假设插入节点为cur其父节点为parent其父节点的兄弟节点为uncle其父节点的父节点为grandfather。
其中下面图示抽象的情况可能是红黑树整体也可能是红黑树的某个子树。
5.1.1. 情况一
第一种情况就是第一次插入也就是插入根节点此时根据性质1我们只需要将对应颜色从RED改为BLACK即可。
5.1.2. 情况二
第二种情况就是插入节点的父节点是黑节点符合红黑树的定义所以此时也不需要做任何调整直接插入即可。
5.1.3. 情况三
第三种情况就是插入节点的父节点parent是红节点其父节点的兄弟节点uncle也为红节点并且祖父节点grandfather是黑节点。如下图
并且为了方便我们之后的null节点不画出默认存在。其中abcde五颗子树中黑色节点数量都相同。 这种情况的调整方法也很简单直接将parent与uncle变为黑色grandfather变为红色即可。 当然镜像对称后调整方式也是同理所以这里就不在赘述。
注意祖父节点grandfather可能不是根节点当祖父节点parent变为红色节点时可能会引起上面节点的冲突(祖父节点的父节点也为红色)这时就需要循环调整。并且如果祖父节点grandfather是根节点该调整方法会将根节点变为红节点所以这时需要将根节点改回黑节点。 5.1.4. 情况四
第四种情况严格来说又可以分为两种情况一种是cur为红色parent也为红色grandfather也为黑色但是uncle不存在。如下图
其中abc三颗子树中除了null外没有黑色节点。 还有一种是cur为红色parent也为红色grandfather也为黑色uncle存在且为黑色·。如下图
其中abc三颗子树中黑色节点的数量比de两棵子树黑色节点的数量多1。 当然这种情况肯定不是新插入红色节点造成的因为一旦cur是新插入节点那么ab两棵子树高度为0没有任何节点肯定无法满足黑色节点数量比cde多1这个条件。所以这种情况肯定是子树从情况三变换得来的。
针对以上两种情况我们都先右单旋再将parent变为黑色grandfather变为红色。当然镜像对称后调整方式也是同理将旋转改为左单旋转即可所以这里就不在赘述。 并且调整完毕后该子树的根节点是黑节点所以也并不需要往上调整。
5.1.5. 情况五
最后一种情况与第四种情况条件相同就是cur为红色parent也为红色grandfather也为黑色uncle不存在/存在且为黑色。只不过插入节点位置有所区别。
其中abc三颗子树中除了null外没有黑色节点。 其中abc三颗子树中黑色节点的数量比de两棵子树黑色节点的数量多1。同样与情况四相同这种情况不可能是插入造成的一定是由情况三变化而来。 针对以上两种情况我们都先左右双旋最后将cur变为黑色grandfather变为红色。当然镜像对称后调整方式也是同理将旋转改为右左双旋即可所以这里就不在赘述。 并且调整完毕后该子树的根节点是黑节点所以也并不需要往上调整。
默认插入节点为红色最后我们对插入操作总结如下 情况一新插入的节点为根节点将其颜色设置为黑色。情况二新插入节点的父节点为黑色无需调整。情况三父节点和叔父节点均为红色将父节点和叔父节点改为黑色祖父节点改为红色然后以祖父节点为当前节点继续进行调整如果祖父节点是根节点则停止调整并将其改为黑色。情况四父节点为红色叔父节点不存在/存在为黑色当前节点是父节点的左子节点且父节点又是祖父节点的左子节点/当前节点是父节点的右子节点且父节点又是祖父节点的右子节点。先进行左单旋/右单旋然后将父节点改为黑色祖父节点改为红色。情况五父节点为红色叔父节点不存在/存在为黑色当前节点是父节点的左子节点且父节点又是祖父节点的右子节点/当前节点是父节点的右子节点且父节点又是祖父节点的左子节点。先进行左右双旋/右左双旋然后将当前节点改为黑色祖父改为红色。 bool Insert(const pairK, V kv)
{//情况一如果是根节点if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _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;}}//找到插入位置cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;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{//情况四叔叔不存在/存在且为黑且cur在parent的左侧if (cur parent-_left){// g // p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况五叔叔不存在 / 存在且为黑cur在parent的右侧{// g// p u// cRotateLR(grandfather);cur-_col BLACK;grandfather-_col RED;}//这时该子树的根节点变为黑色不需要继续调整break;}}else{Node* uncle grandfather-_left;//情况三如果叔叔存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续调整cur grandfather;parent cur-_parent;}else{//情况四叔叔不存在/存在且为黑且cur在parent的左侧if (cur parent-_right){// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 情况五叔叔不存在 / 存在且为黑cur在parent的右侧{// g// u p// cRotateRL(grandfather);cur-_col BLACK;grandfather-_col RED;}//这时该子树的根节点变为黑色不需要继续调整break;}}}//防止情况三改到根节点变为红色_root-_col BLACK;return true;
}
void RotateR(Node* parent)
{Node* cur 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;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}
}
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;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}
}
void RotateLR(Node* parent)
{RotateL(parent-_left);RotateR(parent);
}
void RotateRL(Node* parent)
{RotateR(parent-_right);RotateL(parent);
}5.2. 红黑树的查找
红黑树的查找的逻辑本质与二叉搜索树的查找逻辑相同所以这里就不在赘述。
Node* Find(const K val)
{Node* cur _root;while (cur){if (cur-_kv.first val){//左子树中查找cur cur-_left;}else if (cur-_kv.first val){//右子树中查找cur cur-_right;}else{//找到了return cur;}}return nullptr;
}5.3. 红黑树的删除
删除红黑树的逻辑明显比插入逻辑更加复杂但是总体逻辑又与AVL树与二叉搜索树类似首先第一步找到待删除节点如果待删除节点的左右子树都不为空可以采用伪删除法即寻找到左子树的最右节点(左子树的最大值)或者是右子树的最左节点(右子树的最小值)然后赋值转换为在其左子树或者右子树删除节点保证待删除节点的左右子树至少有一个为空。第二步进行调整删除该节点可能会破坏红黑树的性质所以这时需要调整。第三步删除节点并重新链接。
第一步与第三步都非常简单我们接下来重点讨论第三步。
为了方便描述我们将待删除节点称为delete其父节点称为parent其兄弟节点称为brother其兄弟节点的左右节点分别称为broLeft与broRight。
看图需知 如果parent为蓝色表示parent可能为黑色也可能为红色。如果broLeft或broRight为蓝色表示broLeft或broRight可能为黑色也可能为红色也可能为null节点。如果broLeft或broRight为黑色表示broLeft或broRight可能为黑色也可能为null节点。绿色长方形表示高度未知的子树也可以为null节点。 下面图示我们将按照delete节点在parent节点左侧的形式讨论根据镜像对称delete节点在parent节点右侧只需对称操作即可所以这里就不在赘述。
首先如果delete节点为红色因为至少有一个空节点那么另一个子节点既不能为红色也不可能为黑色此时直接删除即可。
其次如果delete节点为黑色且有一个孩子节点那么这个孩子节点一定为红色(parent与brother不都为红色)否则会破坏性质5。这种情况也只需重新链接不需要调整然后将该孩子节点改为黑色。 接下来我们将讨论delete节点为黑色且没有孩子节点的情况。
情况一兄弟节点为红色。
因为兄弟节点为红色其父节点一定为黑色所以对于这种情况我们只需要对parent节点进行一次左旋转再将brother变为黑色parent变为红色。再重新更新brother节点继续分析原删除节点delete将情况一转换为情况二三四。 情况二兄弟节点为黑色且其左右孩子为空或者都为黑色。
对于这种情况我们需要将brother变为红色然后根据parent节点颜色继续分析如果parent节点为红色只需要将其变为黑色即可调整结束如果parent节点为黑色那么delete节点被删除后原来该子树有两个黑色节点变为一个性质5被破坏将parent节点当做删除节点往上更新或者遇见根节点直接停止将情况二转换为情况一二三四。 情况三兄弟节点为黑色且其左孩子是红色结点右孩子是黑色结点或为空。
这种情况一定不是第一次调整因为如果是第一次调整此时根本不平衡。对应这种情况我们需要对brother节点进行一次右单旋然后再将brother结点变为红色broLeft变为黑色最后更新brother节点再对delete节点进行调整情况三就转换成了情况四。 情况四兄弟节点为黑色且其右孩子是红色结点。
对于这种情况我们先将parent节点进行一次左单旋然后将parent的颜色赋值给brother再将parent的颜色变为黑色最后将broRight变为黑色此时红黑树的调整一定结束。 最后删除节点如果是根节点直接删除再将左子树或者右子树的根节点变黑当做新的根节点。如果没有左右子树都为空那就将根节点_root置为空。
最后我们来总结 如果删除节点为红色直接删除。如果删除节点为黑色且有一个子节点直接删除再链接并将该子节点改为黑色。如果删除节点为黑色且没有子节点可以分为以下四种情况 情况一兄弟节点为红色。先对parent左单旋再将brother变为黑色将parent变为红色再对待删除结点delete进行情况分析情况一就转换成了情况二、三或四。情况二兄弟节点为黑色且其左右孩子为空或者都为黑色。我们直接将brother变成红色若parent是红色将parent变为黑色后调整结束若parent是黑色则需将parent结点当作下一次调整时的结点进行分析直至根节点情况二就转换成了情况一二、三或四。情况三兄弟节点为黑色且其左孩子是红色结点右孩子是黑色结点或为空。先将brother右单旋再将brother变为红色broLeft变为黑色再对待删除结点delete进行情况分析将情况三转换成情况四。情况四兄弟节点为黑色且其右孩子是红色结点。先将parent左单旋然后将parent的颜色赋值给brother再将parent变为黑色最后将brotRight变为黑色此时红黑树的调整一定结束。 思考题为什么删除节点为黑色且没有子节点的四种情况的调整方法一定能使红黑树调整成功
我们知道这四种调整方法一共有三个出口分别为(1)情况二调整后parent为红色(2)情况二parent为黑色调整到根节点(3)调整完情况四。所以问题就成功转换为经过任意三个出口结束之后为什么红黑树一定调整成功。 如果从1号出口结束一个子节点被删除后因为使parent变为黑色另一个子节点变为红色所以此时这颗子树的路径上的黑色节点数没减少调整成功。如果从2号出口结束一定是只经过情况二因为如果是从情况一转换过来的情况二那parent一定是红色就会从1号出口结束。如果只经过情况二那么每次操作都会使上层的一颗子树(非父节点所在子树)黑色节点数减一最后更新到根节点整颗红黑树根节点到叶子节点的黑色节点数比原来少1调整成功。如果从3号出口结束经过第四种调整方式被删除一侧的黑色节点数增一无论是从第一二三删除节点后都会使被删除一侧减一所以经过情况四调整成功。 思考题为什么删除节点为黑色且没有子节点的四种情况的调整方法不会造成死循环 因为情况三一定会被转换为情况四情况四一定会调整成功所以情况三与情况四一定不会死循环。而情况一与情况二也可能转换为情况三与情况四这时也不会死循环。但会不会出现情况一与情况二一直互相循环的情况呢其实不会的因为一旦从情况一转换为情况二此时父节点parent为红色一定会结束。 //删除函数
bool Erase(const K key)
{//(一)找到删除节点Node* cur Find(key);//未找到返回falseif (cur nullptr){return false;}//记录父节点Node* parent cur-_parent;//用于标记实际的待删除结点及其父结点Node* delParent nullptr;Node* delCur nullptr;if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent parent; //标记实际删除结点的父结点delCur cur; //标记实际删除的结点}}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent parent; //标记实际删除结点的父结点delCur cur; //标记实际删除的结点}}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv minRight-_kv; //将待删除结点的键值改为minRight的键值delParent minParent; //标记实际删除的父节点delCur minRight; //标记实际删除的结点}//记录待删除结点及其父结点便于后面删除Node* del delCur;Node* delP delParent;//(二)调整红黑树AdjustRBTree(delCur, delParent);//(三)进行实际删除DeleteNode(del, delP);return true;
}
void DeleteNode(Node* del, Node* delP)
{if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;//指向父节点if (del-_right)del-_right-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent delP;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent delP;}}delete del; //实际删除结点
}
void AdjustRBTree(Node* delCur, Node* delParent)
{if (delCur-_col BLACK) //删除的是黑色结点{if (delCur-_left) //待删除结点有一个红色的左孩子不可能是黑色{delCur-_left-_col BLACK; //将这个红色的左孩子变黑即可}else if (delCur-_right) //待删除结点有一个红色的右孩子不可能是黑色{delCur-_right-_col BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delCur ! _root) //可能一直调整到根结点{if (delCur delParent-_left) //待删除结点是其父结点的左孩子{Node* brother delParent-_right; //兄弟结点是其父结点的右孩子//情况一brother为红色if (brother-_col RED){delParent-_col RED;brother-_col BLACK;RotateL(delParent);//需要继续处理brother delParent-_right; //更新brother}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParent-_col RED){delParent-_col BLACK;break;}//需要继续处理delCur delParent;delParent delCur-_parent;}else{//情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RotateR(brother);//需要继续处理brother delParent-_right; //更新brother}//情况四brother为黑色且其右孩子是红色结点brother-_col delParent-_col;delParent-_col BLACK;brother-_right-_col BLACK;RotateL(delParent);break; //情况四执行完毕后调整一定结束}}else //delCur delParent-_right //待删除结点是其父结点的右孩子{Node* brother delParent-_left; //兄弟结点是其父结点的左孩子//情况一brother为红色if (brother-_col RED) //brother为红色{delParent-_col RED;brother-_col BLACK;RotateR(delParent);//需要继续处理brother delParent-_left; //更新brother}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParent-_col RED){delParent-_col BLACK;break;}//需要继续处理delCur delParent;delParent delCur-_parent;}else{//情况三brother为黑色且其右孩子是红色结点左孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RotateL(brother);//需要继续处理brother delParent-_left; //更新brother}//情况四brother为黑色且其左孩子是红色结点brother-_col delParent-_col;delParent-_col BLACK;brother-_left-_col BLACK;RotateR(delParent);break; //情况四执行完毕后调整一定结束}}}}}
}6. 判断是否为红黑树
判断是否为红黑树首先得判断是否为二叉搜索树然后判断是否满足红黑树的性质。
判断是否满足红黑树的性质首先判断根节点是否为黑色。然后统计一条路径的节点个数最后通过递归判断是否有连续的红色节点以及每条路径的黑色节点是否相同。
bool IsRBTree()
{if (_root-_col RED){cout 根节点为红节点 endl;return false;}//从根节点到叶节点的黑色节点数int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK){refNum;}cur cur-_left;}return Check(_root, 0, refNum) isValidBST();
}
//判断是否为二叉搜索树
bool isValidBST()
{return _isValidBST(_root, LONG_MIN, LONG_MAX);
}
bool _isValidBST(Node* root, long long lower, long long upper)
{if (root nullptr){return true;}if (root-_kv.first lower || root-_kv.first upper){return false;}bool left _isValidBST(root-_left, lower, root-_kv.first);bool right _isValidBST(root-_right, root-_kv.first, upper);return left right;
}
bool Check(Node* root, int blackNum, int refNum)
{if (root nullptr){//判断黑色节点数是否相同if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}//判断是否存在连续的红色节点if (root-_parent root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);
}7. 复杂度分析
对于红黑树的插入、查找和删除操作其时间复杂度和空间复杂度分析如下 时间复杂度 Insert操作平均和最坏情况下的时间复杂度均为 O ( log n ) O(\log n) O(logn)。插入过程中需要调整红黑树的性质可能涉及到旋转操作但这些操作的时间是常数级而查找插入位置的过程类似于二叉搜索树时间复杂度为 O ( log n ) O(\log n) O(logn)。Find操作平均和最坏情况下的时间复杂度均为 O ( log n ) O(\log n) O(logn)。与二叉搜索树的查找过程类似通过比较键值逐渐缩小搜索范围每次比较都能将范围缩小一半。Erase操作平均和最坏情况下的时间复杂度均为 O ( log n ) O(\log n) O(logn)。删除节点时需要查找节点位置然后根据红黑树的性质进行调整和可能的旋转操作这些操作的时间复杂度与插入操作相似。 空间复杂度 Insert操作空间复杂度为 O ( 1 ) O(1) O(1)。在插入过程中主要的额外空间消耗在于创建新节点以及存储一些临时变量如指针等这些空间消耗是常数级的。Find操作空间复杂度为 O ( 1 ) O(1) O(1)。寻找过程中仅使用了少量的固定数量的指针和临时变量没有额外的大规模空间分配。Erase操作空间复杂度为 O ( 1 ) O(1) O(1)。删除操作中的主要空间消耗在于存储临时变量和指针不会动态分配大规模的额外空间。 8.源码
#pragma once
#includeutility
enum _col
{RED,//红色BLACK//黑色
};
templateclass K,class V
struct RBNode
{RBNode(const pairK,V kv pairK,V(), _col col RED):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(col)//默认为红节点{}RBNodeK, V* _left;//左子树RBNodeK, V* _right;//右子树RBNodeK, V* _parent;//父节点pairK, V _kv;//键值_col _col;//颜色
};
templateclass K, class V
class RBTree
{typedef RBNodeK, V Node;
public:RBTree(){}RBTree(const RBTreeK, Vt){_root copy(t._root);}RBTreeK, V operator (const RBTreeK, V t){this-swap(_root, t._root);return *this;}bool Insert(const pairK, V kv){//情况一如果是根节点if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _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;}}//找到插入位置cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;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{//情况四叔叔不存在/存在且为黑且cur在parent的左侧if (cur parent-_left){// g // p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况五叔叔不存在 / 存在且为黑cur在parent的右侧{// g// p u// cRotateLR(grandfather);cur-_col BLACK;grandfather-_col RED;}//这时该子树的根节点变为黑色不需要继续调整break;}}else{Node* uncle grandfather-_left;//情况三如果叔叔存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续调整cur grandfather;parent cur-_parent;}else{//情况四叔叔不存在/存在且为黑且cur在parent的左侧if (cur parent-_right){// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 情况五叔叔不存在 / 存在且为黑cur在parent的右侧{// g// u p// cRotateRL(grandfather);cur-_col BLACK;grandfather-_col RED;}//这时该子树的根节点变为黑色不需要继续调整break;}}}//防止情况三改到根节点变为红色_root-_col BLACK;return true;}void RotateR(Node* parent){Node* cur 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;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}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;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}}void RotateLR(Node* parent){RotateL(parent-_left);RotateR(parent);}void RotateRL(Node* parent){RotateR(parent-_right);RotateL(parent);}Node* Find(const K val){Node* cur _root;while (cur){if (cur-_kv.first val){//左子树中查找cur cur-_left;}else if (cur-_kv.first val){//右子树中查找cur cur-_right;}else{//找到了return cur;}}return nullptr;}//删除函数bool Erase(const K key){//(一)找到删除节点Node* cur Find(key);//未找到返回falseif (cur nullptr){return false;}//记录父节点Node* parent cur-_parent;//用于标记实际的待删除结点及其父结点Node* delParent nullptr;Node* delCur nullptr;if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent parent; //标记实际删除结点的父结点delCur cur; //标记实际删除的结点}}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParent parent; //标记实际删除结点的父结点delCur cur; //标记实际删除的结点}}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv minRight-_kv; //将待删除结点的键值改为minRight的键值delParent minParent; //标记实际删除的父节点delCur minRight; //标记实际删除的结点}//记录待删除结点及其父结点便于后面删除Node* del delCur;Node* delP delParent;//(二)调整红黑树AdjustRBTree(delCur, delParent);//(三)进行实际删除DeleteNode(del, delP);return true;}void DeleteNode(Node* del, Node* delP){if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;//指向父节点if (del-_right)del-_right-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent delP;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent delP;}}delete del; //实际删除结点}void AdjustRBTree(Node* delCur, Node* delParent){if (delCur-_col BLACK) //删除的是黑色结点{if (delCur-_left) //待删除结点有一个红色的左孩子不可能是黑色{delCur-_left-_col BLACK; //将这个红色的左孩子变黑即可}else if (delCur-_right) //待删除结点有一个红色的右孩子不可能是黑色{delCur-_right-_col BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delCur ! _root) //可能一直调整到根结点{if (delCur delParent-_left) //待删除结点是其父结点的左孩子{Node* brother delParent-_right; //兄弟结点是其父结点的右孩子//情况一brother为红色if (brother-_col RED){delParent-_col RED;brother-_col BLACK;RotateL(delParent);//需要继续处理brother delParent-_right; //更新brother}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParent-_col RED){delParent-_col BLACK;break;}//需要继续处理delCur delParent;delParent delCur-_parent;}else{//情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RotateR(brother);//需要继续处理brother delParent-_right; //更新brother}//情况四brother为黑色且其右孩子是红色结点brother-_col delParent-_col;delParent-_col BLACK;brother-_right-_col BLACK;RotateL(delParent);break; //情况四执行完毕后调整一定结束}}else //delCur delParent-_right //待删除结点是其父结点的右孩子{Node* brother delParent-_left; //兄弟结点是其父结点的左孩子//情况一brother为红色if (brother-_col RED) //brother为红色{delParent-_col RED;brother-_col BLACK;RotateR(delParent);//需要继续处理brother delParent-_left; //更新brother}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParent-_col RED){delParent-_col BLACK;break;}//需要继续处理delCur delParent;delParent delCur-_parent;}else{//情况三brother为黑色且其右孩子是红色结点左孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RotateL(brother);//需要继续处理brother delParent-_left; //更新brother}//情况四brother为黑色且其左孩子是红色结点brother-_col delParent-_col;delParent-_col BLACK;brother-_left-_col BLACK;RotateR(delParent);break; //情况四执行完毕后调整一定结束}}}}}}~RBTree(){Destroy(_root);}bool IsRBTree(){if (_root-_col RED){cout 根节点为红节点 endl;return false;}//从根节点到叶节点的黑色节点数int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK){refNum;}cur cur-_left;}return Check(_root, 0, refNum) isValidBST();}//判断是否为二叉搜索树bool isValidBST(){return _isValidBST(_root, LONG_MIN, LONG_MAX);}private:bool _isValidBST(Node* root, long long lower, long long upper){if (root nullptr){return true;}if (root-_kv.first lower || root-_kv.first upper){return false;}bool left _isValidBST(root-_left, lower, root-_kv.first);bool right _isValidBST(root-_right, root-_kv.first, upper);return left right;}bool Check(Node* root, int blackNum, int refNum){if (root nullptr){if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}if (root-_parent root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);}void Destroy(Node* root){if (root nullptr){return;}//递归销毁左子树Destroy(root-_left);//递归销毁右子树Destroy(root-_right);//销毁根节点delete root;root nullptr;}Node* copy(Node* root){// 如果原始节点为空直接返回空指针if (root nullptr){return nullptr;}// 为新节点分配内存并拷贝原始节点的值Node* newnode new Node(root-_kv);// 递归拷贝左子树newnode-_left copy(root-_left);// 递归拷贝右子树newnode-_right copy(root-_right);// 将新节点的父节点指针置为空newnode-_parent nullptr;// 拷贝原始节点的颜色信息newnode-_col root-_col;// 如果新节点的左子节点存在设置其父节点为新节点if (newnode-_left){newnode-_left-_parent newnode;}// 如果新节点的右子节点存在设置其父节点为新节点if (newnode-_right){newnode-_right-_parent newnode;}}Node* _root nullptr;
};
