qq建设网站首页,固安网站建设,用discuz做行业网站,灵犀科技 高端网站建设文章目录 一、红黑树的特点与性质二、红黑树的实现1、实现红黑树的插入操作2、红黑树的验证方法a. Check 函数b. IsBalance 函数 红黑树作为一种自平衡的二叉搜索树#xff0c;在计算机科学领域中占据着重要的地位。它的设计旨在在维持树的平衡性的同时#xff0c;保证各种操… 文章目录 一、红黑树的特点与性质二、红黑树的实现1、实现红黑树的插入操作2、红黑树的验证方法a. Check 函数b. IsBalance 函数 红黑树作为一种自平衡的二叉搜索树在计算机科学领域中占据着重要的地位。它的设计旨在在维持树的平衡性的同时保证各种操作的时间复杂度始终稳定在较低水平。红黑树的灵活性和高效性使得它成为众多编程语言和系统实现中不可或缺的数据结构之一。本文将带领读者深入探究红黑树的结构与原理。c实现 一、红黑树的特点与性质
红黑树的定义与性质
红黑树是一种特殊的自平衡二叉查找树它通过颜色和一系列性质来确保树的平衡从而实现高效的查找、插入和删除操作。在红黑树中每个节点都被赋予红色或黑色的颜色并且这些颜色与树的五个基本性质一起工作共同维持树的平衡。
红黑树是具有着色性质的二叉搜索树
每个节点要么是红色要么是黑色。根节点是黑色。每个叶子节点通常称为NIL或空节点是黑色。在大多数实现中叶子节点不实际存储而是用NIL或空指针表示。如果一个节点是红色的则它的两个子节点都是黑色的即不能有两个相邻的红色节点。对于每个节点从该节点到其所有后代叶子节点的简单路径上均包含相同数目的黑色节点。
这些性质共同确保了红黑树的平衡性。特别是性质5它树确保没有一条路 径会比其他路径长出两倍。这种平衡性保证了红黑树在查找、插入和删除操作中的时间复杂度都是O(log n)其中n是树中节点的数量。着色法则的一个推论是红黑树的高度最多是 2log(n1) 。因此查找保证是一种对数级别的操作。 有 n 个节点的红黑树的高度最多是 2log(n1)这是为什么呢 首先我们来我们考虑一个问题根节点为黑高为 h 的红黑树内部节点个数至少有多少个黑高从某节点出发不含该节点到达任意一叶节点的路径上黑节点的总数。
内部节点上最少的情况就是总共 h 层黑节点的满树形态。若根节点黑高为 h内部节点数最少有 2h-1 个。因此若红黑树总高度为 h 则根节点的黑高肯定是大于等于 h/2 的因此内部节点数 n 2h/2-1由此推出 h 2log(n1) 。
红黑树与AVL树的对比
红黑树同AVL树类似也是一种自平衡的二叉搜索树它通过颜色和一系列性质来维护树的平衡性。与AVL树不同的是红黑树并不追求完全的平衡而是允许局部的不平衡这使得红黑树在插入或删除节点时的旋转操作次数较少降低了操作的复杂性。同时红黑树的查找、插入和删除操作的时间复杂度也能保持在O(log n)。由于红黑树的这种特性它在需要频繁进行插入和删除操作的应用场景中表现得更好。
总的来说红黑树在平衡性、操作复杂性和性能之间找到了一个较好的平衡点使得它在许多实际应用中成为了一个优秀的选择。而AVL树虽然具有严格的平衡性但由于其操作的复杂性以及在实际应用中的效率问题使得它的使用范围相对较小。普通二叉搜索树虽然简单但在数据动态变化的情况下其性能可能会受到影响。因此在选择使用哪种树形结构时需要根据具体的应用场景和需求进行权衡。 关于AVL树的内容大家可以点击这里。 二、红黑树的实现
定义红黑树节点的结构体
在此我们定义一个模板结构体RBTreeNode它是红黑树中的一个节点。红黑树是一种自平衡的二叉搜索树其中每个节点都带有颜色属性红色或黑色。Colour的枚举类型它有两个值RED和BLACK。这个枚举类型用于表示红黑树中节点的颜色
enum Colour { RED, BLACK };// 节点的颜色templateclass K, class V
struct RBTreeNode{RBTreeNodeK, V* _left; // 节点的左孩子RBTreeNodeK, V* _right; // 节点的右孩子RBTreeNodeK, V* _parent; // 节点的父节点pairK, V _kv; // 节点的键值对Colour _col; // 节点的颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};_left、_right和_parent都初始化为nullptr表示新节点最初没有子节点或父节点。 _kv初始化为传入的键值对kv。 _col初始化为RED表示新创建的节点默认是红色的。 为什么要默认是红色呢 红黑树的困难在于将一个新的值插入到树中通常把新的值作为树叶放到树中。如果插入时把该节点作为黑色那么一定违反性质5因为会建立一条更长的黑节点的路径。因此该节点必须涂成红色。因此我们在构造函数里将其颜色初始化为红色。
templateclass K,class V
class RBTree {typedef RBTreeNodeK, V Node;
public://...
private:Node* _root nullptr;
};1、实现红黑树的插入操作
在找到插入位置时如果父节点是黑的插入完成因为插入红色节点不会违反性质5。如果它的父节点已经是红色的那么我们得到连续红色节点这就违反性质4。在这种情况下我们必须调整该树以确保性质4满足且不引起性质5被破坏。因此我们在插入时需要的基本操作是节点颜色的改变以及树的旋转
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;}elsereturn false;
}cur new Node(kv);
if (parent-_kv.first kv.first)parent-_right cur;
elseparent-_left cur;
cur-_parent parent;修复红黑树性质插入新节点后红黑树可能不再满足其性质。因此我们需要进行一系列操作来修复这些性质。这主要包括检查新节点的父节点和叔叔节点的颜色并根据需要执行旋转和重新着色操作。关于旋转操作我们在AVL树中已进行描述若仍存疑可以点击此处或给我留言。 检查父节点颜色如果新节点的父节点是黑色那么插入操作不会破坏红黑树的任何性质因此无需进行任何修复操作。如下图插入10或20不会破坏红黑树性质 父节点和叔叔节点均为红色如果新节点的父节点是红色并且其叔叔节点父节点的兄弟节点也是红色那么我们需要将父节点和叔叔节点都重新着色为黑色并将祖父节点父节点的父节点着色为红色。然后我们将祖父节点作为新的当前节点继续向上检查直到根节点或遇到黑色父节点为止。如图所示 分为两种对称情况图示为插入30。若插入3同理即可。代码实现如下 while (parent parent-_col RED) { if (parent grandparent-_left) {Node* uncle grandparent-_right;if (uncle uncle-_col RED) {parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else {//....}}else {Node* uncle grandparent-_left;if (uncle uncle-_col RED) {parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else {//...}}
} 此段代码用于处理父节点和叔叔节点都为红色的情况 parent 是新插入节点的父节点grandparent 是 parent 的父节点_col 是节点的颜色RED 或 BLACK的属性_left 和 _right 是指向左右子节点的指针。 这段代码的逻辑是这样的 while (parent parent-_col RED)这个循环会持续进行直到 parent 为空即已经到达根节点或者 parent 的颜色为黑色。if (parent grandparent-_left)判断 parent 是否是 grandparent 的左子节点。Node* uncle grandparent-_right;如果是左子节点则叔叔节点uncle是 grandparent 的右子节点。if (uncle uncle-_col RED)如果叔叔节点存在且为红色那么执行以下操作 parent-_col uncle-_col BLACK;将父节点和叔叔节点的颜色都改为黑色。grandparent-_col RED;将祖父节点的颜色改为红色。cur grandparent; 和 parent cur-_parent;更新 cur 为祖父节点并将 parent 更新为 cur 的父节点以便在下一次循环中继续向上检查。 如果叔叔节点不存在或者不是红色代码进入 else 块这里通常包含一些旋转和颜色调整的逻辑我们将在下面继续讨论。 我们给出抽象图注意对称情况我们不在赘述 如果这次更新完后祖父节点作为了新节点。它的父节点为红则继续向上更新。 父节点为红色叔叔节点不存在或为黑色在这种情况下我的当前的节点称为新节点下文统一称其为新节点因此该节点可能是由其子树变化得来也有可能是新插入的节点。我们需要进行旋转操作。具体的旋转方式取决于新节点是父节点的左孩子还是右孩子。如果新节点是父节点的左孩子并且父节点是其祖父节点的左孩子则对祖父节点进行右旋如果新节点是父节点的右孩子并且父节点是其祖父节点的右孩子则对祖父节点进行左旋。旋转后我们将原父节点的颜色更改为黑色并将祖父节点的颜色更改为红色。如图所示 分为两种对称情况图示为插入2。若插入55同理即可。 如果新节点是父节点的右孩子并且父节点是其祖父节点的左孩子则先对父亲节点进行右旋再最祖父节点进行左旋。如果新节点是父节点的左孩子并且父节点是其祖父节点的右孩子则先对父亲节点进行左旋再最祖父节点进行右旋。旋转后我们将原祖父节点的颜色更改为红色并将新节点的颜色更改为黑色。如图所示 同样分为两种对称情况图示为插入4。若插45先右单旋父节点再左单旋祖父节点。 ⚠️需要注意的是 如果叔叔节点如果不存在那么新节点一定是新插入的节点。 因为如果新节点不是新插入节点那么父亲节点和新节点一定由一个节点的颜色是黑色的不满足性质5每条路径黑色节点个数相同。 如果叔叔节点存在根据判断条件叔叔是黑色的。那么新节点原来的颜色肯定是黑色。变为红色的原因是因为新节点的子树在调整过程中改变了新节点的颜色。 代码实现如下 while (parent parent-_col RED) {Node* grandparent parent-_parent;if (parent grandparent-_left) {Node* uncle grandparent-_right;if (uncle uncle-_col RED) {//... 叔叔存在且为红}else {//情况二叔叔不存在 或者 存在但为黑色//旋转变色if (cur parent-_left) {// g// p u// cRotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else {// g// p u// cRotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}else {Node* uncle grandparent-_left;if (uncle uncle-_col RED) {//... 情况一叔叔存在且为红}else {// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right) {RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else {// g// u p// cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}
} 如果当前节点cur是其父节点的左孩子并且父节点是祖父节点的左孩子则执行右旋操作RotateR(grandparent)。这会将父节点移动到祖父节点的右子树并相应地更新子节点的父节点指针。旋转后将父节点变为黑色祖父节点变为红色。 如果当前节点cur是其父节点的右孩子并且父节点是祖父节点的左孩子则首先执行左旋操作RotateL(parent)将当前节点cur移动到父节点的左子树。接着执行右旋操作RotateR(grandparent)将父节点移动到祖父节点的右子树。旋转后将当前节点cur变为黑色祖父节点变为红色。
类似地当父节点是祖父节点的右孩子时执行相反的操作
如果当前节点cur是其父节点的右孩子并且父节点是祖父节点的右孩子则执行左旋操作RotateL(grandparent)。如果当前节点cur是其父节点的左孩子并且父节点是祖父节点的右孩子则首先执行右旋操作RotateR(parent)接着执行左旋操作RotateL(grandparent)。
我们分别给出新节点与父亲在不同方向的抽象图和相同方向的抽象图注意对称情况 如果新节点是父节点的右孩子并且父节点是其祖父节点的左孩子则先对父亲节点进行右旋再最祖父节点进行左旋。如果新节点是父节点的左孩子并且父节点是其祖父节点的右孩子则先对父亲节点进行左旋再最祖父节点进行右旋。 如果新节点是父节点的左孩子并且父节点是其祖父节点的左孩子则对祖父节点进行右旋如果新节点是父节点的右孩子并且父节点是其祖父节点的右孩子则对祖父节点进行左旋。 此次旋转完后我们就结束循环此时可以确保树仍然满足红黑树的定义。 确保根节点为黑色在所有修复操作完成后我们还需要确保根节点是黑色的。如果根节点在修复过程中被着色为红色我们需要将其重新着色为黑色。在找到插入位置时如果父节点是黑的插入完成因为插入红色节点不会违反性质5。如果它的父节点已经是红色的那么我们得到连续红色节点这就违反性质4。在这种情况下我们必须调整该树以确保性质4满足且不引起性质5被破坏。因此我们在插入时需要的基本操作是节点颜色的改变以及树的旋转 _root-_col BLACK;通过执行上述步骤我们可以确保在插入新节点后红黑树仍然保持其平衡性质并且能够有效地支持查找、删除等后续操作。红黑树的插入操作在平均情况下的时间复杂度为O(log n)其中n为树中节点的数量。
插入的完整代码如下
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;}elsereturn false;}cur new Node(kv);if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_parent parent;while (parent parent-_col RED) {Node* grandparent parent-_parent;if (parent grandparent-_left) {Node* uncle grandparent-_right;//情况一 叔叔存在且为红if (uncle uncle-_col RED) {//先变色 后向上处理parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else {//情况二叔叔不存在 或者 存在但为黑色//旋转变色if (cur parent-_left) {// g// p u// cRotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else {// g// p u// cRotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}else {Node* uncle grandparent-_left;// 情况一叔叔存在且为红if (uncle uncle-_col RED) {// 变色parent-_col uncle-_col BLACK;grandparent-_col RED;// 继续往上处理cur grandparent;parent cur-_parent;}else {// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right) {RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else {// g// u p// cRotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}_root-_col BLACK;return true;
}2、红黑树的验证方法
红黑树也是一种特殊的二叉搜索树因此我们可以先获取二叉树的中序遍历序列来判断该二叉树是否满足二叉搜索树的性质
void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first endl;_InOrder(root-_right);
}
void InOrder() { _InOrder(_root); } 我们也要检测其是否满足红黑树的性质我们需要两个函数
a. Check 函数
Check 函数用于递归地检查红黑树的性质是否得到满足。它接受三个参数当前节点 cur、从根节点到当前节点路径上的黑色节点数 blackNum 和从根节点到最左侧路径上的黑色节点数 refBlackNum。
空节点检查如果当前节点为空cur nullptr则检查从根节点到该路径的黑色节点数 blackNum 是否与最左侧路径的黑色节点数 refBlackNum 相等。如果不相等则输出错误信息并返回 false。连续红色节点检查如果当前节点为红色且其父节点也为红色则违反了红黑树的性质性质 4输出错误信息并返回 false。黑色节点计数如果当前节点为黑色则增加 blackNum 的计数。递归检查子节点递归调用 Check 函数检查当前节点的左子树和右子树只有当左右子树都返回 true 时当前节点才返回 true。
bool Check(Node* cur, int blackNum, int refBlackNum) {if (cur nullptr) {if (refBlackNum ! blackNum) {cout 黑色节点的数量不相等 endl;return false;}cout 黑色节点的数量: blackNum endl;return true;}if (cur-_col RED cur-_parent-_col RED) {cout cur-_kv.first 存在连续的红色节点 endl;return false;}if (cur-_col BLACK)blackNum;return Check(cur-_left, blackNum, refBlackNum) Check(cur-_right, blackNum, refBlackNum);
}b. IsBalance 函数
IsBalance 函数用于检查整棵红黑树是否平衡。
根节点颜色检查如果根节点存在且为红色则直接返回 false因为根节点必须是黑色性质 2。计算最左侧路径黑色节点数从根节点开始沿着最左侧路径遍历树计算遇到的黑色节点数存储在 refBlackNum 中。调用 Check 函数从根节点开始调用 Check 函数递归地检查整棵树是否满足红黑树的性质。传递的初始黑色节点数 blackNum 为 0参考黑色节点数 refBlackNum 为之前计算得到的值。
bool IsBalance(){if (_root _root-_col RED)return false;int refBlackNum 0;Node* cur _root;while (cur){if (cur-_col BLACK)refBlackNum;cur cur-_left;}return Check(_root, 0, refBlackNum);
}如果 Check 函数返回 true则说明红黑树平衡IsBalance 函数也返回 true否则返回 false。
本文代码置于RBtree · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)
