南联网站建设公司,站酷网如何接单,长沙网络推广只选智投未来,手机端竞价恶意点击 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 上一篇博客#xff1a;【数据… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 上一篇博客【数据结构】AVL树(C实现) 文章目录 红黑树的概念红黑树的性质红黑树结点的定义红黑树的插入红黑树的验证红黑树的查找红黑树的删除红黑树与AVL树的比较总结 红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加了一个存储位用于表示结点的颜色这个颜色可以是红色的也可以是黑色的因此我们称之为红黑树。 红黑树通过对任何一条从根到叶子的路径上各个结点着色方式的限制确保没有一条路径会比其他路径长出两倍因此红黑树是近似平衡的。
红黑树的性质
红黑树有以下五点性质 每个结点不是红色就是黑色。 根结点是黑色的。 如果一个结点是红色的则它的两个孩子结点是黑色的。 对于每个结点从该结点到其所有后代叶子结点的简单路径上均包含相同数目的黑色结点。 每个叶子结点都是黑色的此处的叶子结点指定是空结点。 红黑树如何确保从根到叶子的最长可能路径不会超过最短可能路径的两倍
根据红黑树的性质3可以得出红黑树当中不会出现连续的红色结点而根据性质4又可以得出从某一结点到其后代叶子结点的所有路径上包含的黑色结点的数目是相同的。
我们假设在红黑树中从根到叶子的所有路径上包含的黑色结点的个数都是N个那么最短路径就是全部由黑色结点构成的路径即长度为N。
而最长可能路径就是由一黑一红结点构成的路径该路径当中黑色结点与红色结点的数目相同即长度为2N。
因此红黑树从根到叶子的最长可能路径不会超过最短可能路径的两倍。
红黑树结点的定义
我们这里直接实现KV模型的红黑树为了方便后序的旋转操作将红黑树的结点定义为三叉链结构除此之外还新加入了一个成员变量用于表示结点的颜色。
templateclass K, class V
struct RBTreeNode
{//三叉链RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;//存储的键值对pairK, V _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};在这里我们可以使用枚举来定义结点的颜色这样可以增加代码的可读性和可维护性并且便于后序的调试操作。
//枚举定义结点的颜色
enum Colour
{RED,BLACK
};为什么构造结点时默认将结点的颜色设置为红色 当我们向红黑树插入结点时若我们插入的是黑色结点那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个即破坏了红黑树的性质4此时我们就需要对红黑树进行调整。
若我们插入红黑树的结点是红色的此时如果其父结点也是红色的那么表明出现了连续的红色结点即破坏了红黑树的性质3此时我们需要对红黑树进行调整但如果其父结点是黑色的那我们就无需对红黑树进行调整插入后仍满足红黑树的要求。
总结一下 插入黑色结点一定破坏红黑树的性质4必须对红黑树进行调整。 插入红色结点可能破坏红黑树的性质3可能对红黑树进行调整。 权衡利弊后我们在构造结点进行插入时默认将结点的颜色设置为红色。
红黑树的插入
红黑树插入结点的逻辑分为三步 按二叉搜索树的插入方法找到待插入位置。 将待插入结点插入到树中。 若插入结点的父结点是红色的则需要对红黑树进行调整。 其中前两步与二叉搜索树插入结点时的逻辑相同红黑树的关键在于第三步对红黑树的调整。 红黑树在插入结点后是如何调整的 实际上在插入结点后并不是一定会对红黑树进行调整若插入结点的父结点是黑色的那么我们就不用对红黑树进行调整因为本次结点的插入并没有破坏红黑树的五点性质。
只有当插入结点的父结点是红色时才需要对红黑树进行调整因为我们默认插入的结点就是红色的如果插入结点的父结点也是红色的那么此时就出现了连续的红色结点因此需要对红黑树进行调整。
因为插入结点的父结点是红色的说明父结点不是根结点根结点是黑色的因此插入结点的祖父结点父结点的父结点就一定存在。
红黑树调整时具体应该如何调整主要是看插入结点的叔叔插入结点的父结点的兄弟结点根据插入结点叔叔的不同可将红黑树的调整分为三种情况。 情况一插入结点的叔叔存在且叔叔的颜色是红色。 此时为了避免出现连续的红色结点我们可以将父结点变黑但为了保持每条路径黑色结点的数目不变因此我们还需要将祖父结点变红再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变也解决了连续红色结点的问题。 但调整还没有结束因为此时祖父结点变成了红色如果祖父结点是根结点那我们直接再将祖父结点变成黑色即可此时相当于每条路径黑色结点的数目都增加了一个。
但如果祖父结点不是根结点的话我们就需要将祖父结点当作新插入的结点再判断其父结点是否为红色若其父结点也是红色那么又需要根据其叔叔的不同进而进行不同的调整操作。
因此情况一的抽象图表示如下
注意 叔叔存在且为红时cur结点是parent的左孩子还是右孩子调整方法都是一样的。 情况二插入结点的叔叔存在且叔叔的颜色是黑色。 这种情况一定是在情况一继续往上调整的过程中出现的即这种情况下的cur结点一定不是新插入的结点而是上一次情况一调整过程中的祖父结点如下图 我们将路径中祖父结点之上黑色结点的数目设为x xx将叔叔结点之下黑色结点的数目设为y yy则在插入结点前图示两条路径黑色结点的数目分别为x1 和x2y很明显x2y 是一定大于 x1的因此在插入结点前就不满足红黑树的要求了所以说叔叔结点存在且为黑这种情况一定是由情况一往上调整过程中才会出现的一种情况。
需要注意 从根结点一直走到空位置就算一条路径而不是从根结点走到左右结点均为空的叶子结点时才算一条路径。 情况二和情况三均需要进行旋转处理旋转处理后无需继续往上进行调整所以说情况二一定是由情况一往上调整的过程中出现的。 出现叔叔存在且为黑时单纯使用变色已经无法处理了这时我们需要进行旋转处理。若祖孙三代的关系是直线cur、parent、grandfather这三个结点为一条直线则我们需要先进行单旋操作再进行颜色调整颜色调整后这棵被旋转子树的根结点是黑色的因此无需继续往上进行处理。
抽象图表示如下 说明一下 当直线关系为parent是grandfather的右孩子cur是parent的右孩子时就需要先进行左单旋操作再进行颜色调整。
若祖孙三代的关系是折现cur、parent、grandfather这三个结点为一条折现则我们需要先进行双旋操作再进行颜色调整颜色调整后这棵被旋转子树的根是黑色的因此无需继续往上进行处理。
抽象图表示如下
说明一下 当折现关系为parent是grandfather的右孩子cur是parent的左孩子时就需要先进行右左双旋操作再进行颜色调整。 情况三插入结点的叔叔不存在。 在这种情况下的cur结点一定是新插入的结点而不可能是由情况一变化而来的因为叔叔不存在说明在parent的下面不可能再挂黑色结点了如下图
如果插入前parent下面再挂黑色结点就会导致图中两条路径黑色结点的数目不相同而parent是红色的因此parent下面自然也不能挂红色结点所以说这种情况下的cur结点一定是新插入的结点。
和情况二一样若祖孙三代的关系是直线cur、parent、grandfather这三个结点为一条直线则我们需要先进行单旋操作再进行颜色调整颜色调整后这棵被旋转子树的根结点是黑色的因此无需继续往上进行处理。
抽象图表示如下
说明一下 当直线关系为parent是grandfather的右孩子cur是parent的右孩子时就需要先进行左单旋操作再进行颜色调整。
若祖孙三代的关系是折现cur、parent、grandfather这三个结点为一条折现则我们需要先进行双旋操作再进行颜色调整颜色调整后这棵被旋转子树的根是黑色的因此无需继续往上进行处理。
抽象图表示如下
说明一下 当折现关系为parent是grandfather的右孩子cur是parent的左孩子时就需要先进行右左双旋操作再进行颜色调整。
代码如下
//插入函数
pairNode*, bool Insert(const pairK, V kv)
{if (_root nullptr) //若红黑树为空树则插入结点直接作为根结点{_root new Node(kv);_root-_col BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索树的插入方法找到待插入位置Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //待插入结点的key值等于当前结点的key值{return make_pair(cur, false); //插入失败}}//2、将待插入结点插入到树中cur new Node(kv); //根据所给值构造一个结点Node* newnode cur; //记录新插入的结点便于后序返回if (kv.first parent-_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent-_left cur;cur-_parent parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent-_right cur;cur-_parent parent;}//3、若插入结点的父结点是红色的则需要对红黑树进行调整while (parentparent-_col RED){Node* grandfather parent-_parent; //parent是红色则其父结点一定存在if (parent grandfather-_left) //parent是grandfather的左孩子{Node* uncle grandfather-_right; //uncle是grandfather的右孩子if (uncleuncle-_col RED) //情况1uncle存在且为红{//颜色调整parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else //情况2情况3uncle不存在 uncle存在且为黑{if (cur parent-_left){RotateR(grandfather); //右单旋//颜色调整grandfather-_col RED;parent-_col BLACK;}else //cur parent-_right{RotateLR(grandfather); //左右双旋//颜色调整grandfather-_col RED;cur-_col BLACK;}break; //子树旋转后该子树的根变成了黑色无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle grandfather-_left; //uncle是grandfather的左孩子if (uncleuncle-_col RED) //情况1uncle存在且为红{//颜色调整uncle-_col parent-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else //情况2情况3uncle不存在 uncle存在且为黑{if (cur parent-_left){RotateRL(grandfather); //右左双旋//颜色调整cur-_col BLACK;grandfather-_col RED;}else //cur parent-_right{RotateL(grandfather); //左单旋//颜色调整grandfather-_col RED;parent-_col BLACK;}break; //子树旋转后该子树的根变成了黑色无需继续往上进行处理}}}_root-_col BLACK; //根结点的颜色为黑色可能被情况一变成了红色需要变回黑色return make_pair(newnode, true); //插入成功
}//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;//建立subRL与parent之间的联系parent-_right subRL;if (subRL)subRL-_parent parent;//建立parent与subR之间的联系subR-_left parent;parent-_parent subR;//建立subR与parentParent之间的联系if (parentParent nullptr){_root subR;_root-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}
}//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;//建立subLR与parent之间的联系parent-_left subLR;if (subLR)subLR-_parent parent;//建立parent与subL之间的联系subL-_right parent;parent-_parent subL;//建立subL与parentParent之间的联系if (parentParent nullptr){_root subL;_root-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}
}//左右双旋
void RotateLR(Node* parent)
{RotateL(parent-_left);RotateR(parent);
}//右左双旋
void RotateRL(Node* parent)
{RotateR(parent-_right);RotateL(parent);
}注意 在红黑树调整后需要将根结点的颜色变为黑色因为红黑树的根结点可能在情况一的调整过程中被变成了红色。
红黑树的验证
红黑树也是一种特殊的二叉搜索树因此我们可以先获取二叉树的中序遍历序列来判断该二叉树是否满足二叉搜索树的性质。
代码如下
//中序遍历
void Inorder()
{_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);
}但中序有序只能证明是二叉搜索树要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。
代码如下
//判断是否为红黑树
bool ISRBTree()
{if (_root nullptr) //空树是红黑树{return true;}if (_root-_col RED){cout error根结点为红色 endl;return false;}//找最左路径作为黑色结点数目的参考值Node* cur _root;int BlackCount 0;while (cur){if (cur-_col BLACK)BlackCount;cur cur-_left;}int count 0;return _ISRBTree(_root, count, BlackCount);
}
//判断是否为红黑树的子函数
bool _ISRBTree(Node* root, int count, int BlackCount)
{if (root nullptr) //该路径已经走完了{if (count ! BlackCount){cout error黑色结点的数目不相等 endl;return false;}return true;}if (root-_col REDroot-_parent-_col RED){cout error存在连续的红色结点 endl;return false;}if (root-_col BLACK){count;}return _ISRBTree(root-_left, count, BlackCount) _ISRBTree(root-_right, count, BlackCount);
}红黑树的查找
红黑树的查找函数与二叉搜索树的查找方式一模一样逻辑如下 若树为空树则查找失败返回nullptr。 若key值小于当前结点的值则应该在该结点的左子树当中进行查找。 若key值大于当前结点的值则应该在该结点的右子树当中进行查找。 若key值等于当前结点的值则查找成功返回对应结点。 代码如下
//查找函数
Node* Find(const K key)
{Node* cur _root;while (cur){if (key cur-_kv.first) //key值小于该结点的值{cur cur-_left; //在该结点的左子树当中查找}else if (key cur-_kv.first) //key值大于该结点的值{cur cur-_right; //在该结点的右子树当中查找}else //找到了目标结点{return cur; //返回该结点}}return nullptr; //查找失败
}
红黑树的删除
红黑树的删除要比插入更加难以理解但是只要仔细一点也还行。 第一步找到实际待删除的结点 找结点的过程与二叉搜索树寻找待删除结点的方法一样若找到的待删除结点的左右子树均不为空则需要使用替换法进行删除。因此我们最终需要删除的都是左右子树至少有一个为空的结点。
找到实际待删除结点后先不删除该结点否则调整红黑树时不容易控制找到实际待删除结点后立即进行红黑树的调整。 第二步调整红黑树 调整红黑树之前我们先判断一下本次结点的删除是否会破坏了红黑树的性质若破坏了我们才需要对红黑树进行调整。
若实际删除的结点是红色结点那么本次删除操作不会破坏红黑树的性质因此我们不需要对红黑树进行调整。反之若删除的结点是黑色结点我们就需要对红黑树进行调整因为黑色结点的删除将会使得一些路径中黑色结点的数目减少此时便破坏了红黑树的性质四。 我们先来说最简单的一种情况即待删除结点只有一个孩子为空的情况。 在这种情况下待删除结点要么是只有左孩子要么是有只右孩子但不管是左孩子还是右孩子这个孩子一定是红色的因为若这个孩子是黑色的那么此时图示长蓝色路径的黑色结点数目比短蓝色路径的黑色结点数目多不符合红黑树的性质。
又因为红黑树当中不允许出现连续的红色结点因此在这种情况下实际上就只有图示两种实际情况这时我们直接将待删除结点的那个红孩子变成黑色就行了因为在后面实际删除结点时会将这个孩子连接到删除结点的父结点下面连接后相当于我们删除的是一个红色结点红黑树调整完成。 下面再来说比较复杂的情况即待删除结点的左右孩子均为空。 我们以待删除结点是其父结点的左孩子为例分为以下四种情况
图示说明 若parent结点为白色表明parent结点可能是红色结点也可能是黑色结点。 若bL或bR结点为白色表明其可能是红色结点或黑色结点甚至该结点不存在。 bL和bR结点为黑色时表明他们可能是黑色结点或该结点不存在。 情况一brother为红色。
当待删除结点的brother为红色时我们先以parent为旋转点进行一次左单旋再将brother的颜色变为黑色将parent的颜色变为红色此时我们再对待删除结点cur进行情况分析情况一就转换成了情况二、三或四。
情况二brother为黑色且其左右孩子都是黑色结点或为空。
在该情况下我们直接将brother的颜色变成红色此时根据parent的颜色决定红黑树的调整是否结束若parent的颜色是红色则我们将parent变为黑色后即可结束红黑树的调整若parent的颜色原本就是黑色则我们需要将parent结点当作下一次调整时的cur结点进行情况分析并且情况二在下一次调整时可能会是情况一、二、三、四当中的任何一种。
情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空。
出现该情况时我们先以brother为旋转点进行一次右单旋再将brother结点变为红色将brotherLeft变为黑色此时我们再对待删除结点cur进行情况分析情况三就转换成了情况四。
情况四brother为黑色且其右孩子是红色结点。
经过情况四的处理后红黑树就一定调整结束了。在情况四当中我们先以parent为旋转点进行一次左单旋然后将parent的颜色赋值给brother再将parent的颜色变为黑色最后将brotherRight变为黑色此时红黑树的调整便结束了。
说明一下 待删除结点是其父结点的右孩子时的四种情况与上面四种情况类似这里就不列举出来了。 若待删除结点没有父结点即待删除结点是根结点时在找到该结点时就进行了删除这里不用考虑具体看代码。 这里有必要对各种情况的切换进行说明你可能会担心调整红黑树时在这四种情况当中一直来回切换而不能跳出下面我们来对此进行分析
首先进入情况四后红黑树就一定调整结束了。其次进入情况三后下次也一定会进入情况四红黑树的调整也会结束。所以情况三和情况四是没有问题的你们最纠结的只能是情况一和情况二了。
情况一又会切换为情况二、三、四因此只要情况二能够有办法退出那么所有情况就都能退出了。
在情况二当中我们说如果parent的颜色是红色那么我们将parent变为黑色后就可以结束红黑树的调整那会不会每次进入情况二时parent的颜色都不是红色而一直是黑色的呢
当然有可能但是我们若一直往上进行调整时那么总会调整到红黑树的根结点当调整到根结点后我们便不用进行调整了此时根结点虽然是黑色的但是不影响这仅仅意味着每条从根到叶子的路径上包含的黑色结点的个数都减少了一个此时也没有破坏红黑树的性质也就完成了红黑树的调整因此在调整过程中不会出现一直在这四种情况来回切换而不能跳出的问题。 第三步进行结点的实际删除 在红黑树调整完毕后我们就可以进行结点的删除了删除结点的方式很简单若待删除结点有左孩子或右孩子我们将其左孩子或右孩子连接到待删除结点父结点的下面即可之后便可以将待删除结点删除了。
代码如下
//删除函数
bool Erase(const K key)
{//用于遍历二叉树Node* parent nullptr;Node* cur _root;//用于标记实际的待删除结点及其父结点Node* delParentPos nullptr;Node* delPos nullptr;while (cur){if (key cur-_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key cur-_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv.first minRight-_kv.first; //将待删除结点的key改为minRight的keycur-_kv.second minRight-_kv.second; //将待删除结点的value改为minRight的valuedelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //进行红黑树的调整以及结点的实际删除}}}if (delPos nullptr) //delPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//调整红黑树if (delPos-_col BLACK) //删除的是黑色结点{if (delPos-_left) //待删除结点有一个红色的左孩子不可能是黑色{delPos-_left-_col BLACK; //将这个红色的左孩子变黑即可}else if (delPos-_right) //待删除结点有一个红色的右孩子不可能是黑色{delPos-_right-_col BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delPos ! _root) //可能一直调整到根结点{if (delPos delParentPos-_left) //待删除结点是其父结点的左孩子{Node* brother delParentPos-_right; //兄弟结点是其父结点的右孩子//情况一brother为红色if (brother-_col RED){delParentPos-_col RED;brother-_col BLACK;RotateL(delParentPos);//需要继续处理brother delParentPos-_right; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RotateR(brother);//需要继续处理brother delParentPos-_right; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其右孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_right-_col BLACK;RotateL(delParentPos);break; //情况四执行完毕后调整一定结束}}else //delPos delParentPos-_right //待删除结点是其父结点的左孩子{Node* brother delParentPos-_left; //兄弟结点是其父结点的左孩子//情况一brother为红色if (brother-_col RED) //brother为红色{delParentPos-_col RED;brother-_col BLACK;RotateR(delParentPos);//需要继续处理brother delParentPos-_left; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其右孩子是红色结点左孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RotateL(brother);//需要继续处理brother delParentPos-_left; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其左孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_left-_col BLACK;RotateR(delParentPos);break; //情况四执行完毕后调整一定结束}}}}}//进行实际删除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; //实际删除结点return true;
}红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删查改的时间复杂度都是O(logN)但红黑树和AVL树控制二叉树平衡的方式不同
AVL树是通过控制左右高度差不超过1来实现二叉树平衡的实现的是二叉树的严格平衡。 红黑树是通过控制结点的颜色从而使得红黑树当中最长可能路径不超过最短可能路径的2倍实现的是近似平衡。 相对于AVL树来说红黑树降低了插入结点时需要进行的旋转的次数所以在经常进行增删的结构中性能比AVL树更优实际运用时也大多用的是红黑树。
总结
今天我们比较详细地完成了红黑树的C实现了解了一些有关的底层原理。接下来我们将进行STL中 set、map、multiset、multimap类的学习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
