单位做网站,叫人做国外公司网站让老外做好还是国内人做好,广告设计制作方案,wordpress微信主题下载文章目录 1.红黑树的概述2.红黑树的性质3.红黑树的代码实现3.1.红黑树的节点定义3.2.红黑树的插入操作3.3.红黑树是否平衡 黑红树是一颗特殊的搜索二叉树#xff0c;本文在前文的基础上#xff0c;图解红黑树插入#xff1a;前文
链接#xff0c;完整对部分关键代码展示本文在前文的基础上图解红黑树插入前文
链接完整对部分关键代码展示完整的代码在gitee仓库中
链接 文章中有错误的地方欢迎大家指正如果有帮助到你也请多多点赞支持 1.红黑树的概述
平衡二叉树要求左右子树的高度差的绝对值不超过1所以平衡二叉树是高度平衡的正是因为它要求严格控制高度差在频繁的插入的删除的时候导致旋转次数过多带来了一定的性能消耗
红黑树也是一颗特殊的搜索二叉树任何一条从根到叶子的路径上各个结点由颜色红黑方式的限制红黑树确保没有一条路径会比其他路径长出两倍最长路径不会超过最短路径的两倍它而是接近平衡的。红黑树没有严格要求高度的平衡所以红黑树在总体的性能上会略优于平衡二叉树AVL树。
在现实的各种应用中都是使用红黑树的来充当数据结构如Java集合中的TreeMapCSTL中Set、Map等都是使用红黑树而不是AVL树。可能在查找方面AVL树会由于红黑树但是几十次的常数差别在现代CPU大概每秒几十亿次来说完全不受影响AVL树和红黑树查找的时间复杂度都是在一个等级上O(log_2(N))红黑树在插入和删除会优于AVL树
2.红黑树的性质
每个结点不是红色就是黑色根节点必须是黑色的如果一个节点是红色的则它的两个孩子结点必须是是黑色的即不会有两个连续的红节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点即每条路径上黑色的节点相同每个叶子结点都是黑色的(此处的叶子结点指的是空结点即下图的NIL) 关于路径问题 上图有11条路径 为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 最短路径全黑的路径 最长路径一黑一红相间的路径
上面的图情况就是最大的4个节点/2个节点 2倍的情况
3.红黑树的代码实现
3.1.红黑树的节点定义
enum color
{RED,BLACK
};templateclass K, class V
struct RBNode
{std::pairK, V _kv;RBNodeK, V* _left;RBNodeK, V* _right;RBNodeK, V* _parent;color _color;RBNode(const std::pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED){}
};3.2.红黑树的插入操作
第一大类情况cur、parent为红grandfather为黑uncle存在且为红 将parent和uncle都变为黑grandfather变为红但是grandfather如果是根节点直接将其设为黑即可如果grandfather不为红如下图则将cur grandfather继续重复步骤1和步骤2 **第二大类情况**cur为红parent为红grandfather为黑uncle不存在或uncle存在且为黑
单旋的情况
下图是uncle不存在或uncle存在且为黑单旋的情况通过节点的位置判断单旋如条件是grandfather -left parent; parent-left cur; 直线说明是单旋都是左边说明右边高要右单旋变色grandfather变为红parent变为黑色可以看到调整后的根据原来的grandfather是黑色无论往上的祖先是何种颜色都不会出现两个红色连一起的情况,不用往上调整了 双旋的情况
通过上面的例子可以知道存在uncle且为黑和不存在uncle的处理结果是一样的通过下图的判断是折线grandfather -left parntparent-right cur通过平衡二叉树的插入操作的学习可以知道这种情况先左单旋再右单旋变色grandfather变为红cur变为黑可以看到调整后的根据原来的grandfather是黑色无论往上的祖先是何种颜色都不会出现两个红色连一起的情况,不用往上调整了 上面就是红黑树的**左子树的插入操作右子树的插入99%是一样的**可能没有99%哈哈哈但是是类似的操作简单画个图
第一大类情况 第二大类情况
单旋情况 双旋情况 bool insert(const std::pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_color 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-_color RED){Node* grandfather parent-_parent;// parent是左子树if (parent grandfather-_left){Node* uncle grandfather-_right;// 第一大类uncle存在且为红if (uncle uncle-_color RED){// 改变颜色parent-_color uncle-_color BLACK;grandfather-_color RED;// 修改条件继续往上执行cur grandfather;parent cur-_parent;}else // 第二大类uncle不存在或uncle存在且为黑{// 单旋情况if (cur parent-_left){// 右单旋RotateRight(grandfather);// 改变颜色parent-_color BLACK;grandfather-_color RED;}else // 双旋情况{RotateLeft(parent);RotateRight(grandfather);cur-_color BLACK;grandfather-_color RED;}// 这种情况就不用重复调整直接跳出循环break;}}else // parent是右子树{Node* uncle grandfather-_left;if (uncle uncle-_color RED){parent-_color uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent cur-_parent;}else{if (cur parent-_right){RotateLeft(grandfather);parent-_color BLACK;grandfather-_color RED;}else{RotateRight(parent);RotateLeft(grandfather);cur-_color BLACK;grandfather-_color RED;}break;}}}// 根绝对为黑色_root-_color BLACK;return true;
}3.3.红黑树是否平衡
根据每条路径的黑节点的个数相同判断
bool isBanlan()
{// 如何判断是否为红黑树// 1.高度行不行 不行 2.能不能根据节点的个数不操作2倍的关系 也不行// 3.那有什么是确定的所有路径黑节点的个数相等根据这个性质Node* cur _root;int checkNum 0;while (cur){if(cur-_color BLACK)checkNum;cur cur-_left;}return isBanlan(_root,checkNum,0);
}bool isBanlan(Node* root,int checkNum,int blackNum)
{if (root nullptr)return true;if (root-_color BLACK){blackNum;}if (root-_left nullptr root-_right nullptr){return blackNum checkNum ? true : false;}bool left isBanlan(root-_left, checkNum, blackNum);bool right isBanlan(root-_right, checkNum, blackNum);return left right;
}
