html5彩票网站模板,运营笔记wordpress,网络设备具体有哪些,丝足网站的建设文章目录 前言#x1f680;一、红黑树的介绍1.1 红黑树的概念1.2 红黑树的特点1.3 红黑树的性质 #x1f680;二、红黑树结点的定义#x1f680;三、红黑树的框架#x1f680;四、旋转操作#x1f680;五、红黑树的插入操作5.1 uncle结点存在且为红5.2 uncle结点不存在或者… 文章目录 前言一、红黑树的介绍1.1 红黑树的概念1.2 红黑树的特点1.3 红黑树的性质 二、红黑树结点的定义三、红黑树的框架四、旋转操作五、红黑树的插入操作5.1 uncle结点存在且为红5.2 uncle结点不存在或者存在且为黑5.3 插入操作的全部代码5.4 测试插入 六、AVL树和红黑树的性能比较6.1 平衡性6.2 查找操作6.3 插入和删除操作6.4 内存使用6.5 使用场景 结语 前言
继上篇在平衡中追寻高度探秘AVL树的自我调节之美我们继续讨论红黑树的相关知识。 在计算机科学的广阔天地中数据结构如同乐器各具特色共同奏响高效算法的乐章。在众多自平衡树中红黑树以其独特的结构与高效的性能成为了实现平衡的典范。本博文将深入探讨红黑树的原理、特点及其在实际应用中的表现揭示这一数据结构如何在动态数据操作中保持高效与稳定。 一、红黑树的介绍
1.1 红黑树的概念
红黑树是一种自平衡的二叉搜索树其中每个节点都被标记为红色或黑色。通过这些颜色标记以及特定的规则红黑树能够在插入和删除节点时保持平衡从而确保基本操作的效率。
1.2 红黑树的特点
节点颜色每个节点可以是红色或黑色。根节点树的根节点始终是黑色。叶子节点所有叶子节点空节点都是黑色。红色节点限制任何红色节点的子节点必须是黑色避免连续的红色节点。黑色高度从任何节点到其每个叶子节点的所有路径都必须包含相同数量的黑色节点。
1.3 红黑树的性质
接近平衡红黑树保证了从根到叶子节点的最长路径不会超过最短路径的两倍因此树是接近平衡的。时间复杂度 查找O(log n)插入O(log n)删除O(log n) 自平衡在插入和删除操作后红黑树通过旋转和重新着色来保持上述性质从而确保树的高度尽量低。
这些特性使得红黑树在需要动态数据存储和高效查找的应用中非常有用比如标准库中的std::map和std::set。
二、红黑树结点的定义
templateclass K, class V
class RBTreeNode {
public:RBTreeNodeK, V* left;RBTreeNodeK, V* right;RBTreeNodeK, V* _parent;pairK, V _kv; //结点中存的键值对color _col; //结点的颜色RBTreeNode(const pairK, V kv pairK, V(), Color color RED):_kv(kv),left(nullptr),right(nullptr),_parent(nullptr),_col(color){}};新节点默认颜色是RED。这是因为如果新插入结点的颜色是BLACK那意味着当前路径上新增了一个黑色结点为了保证红黑树的第5条性质我们要对这颗红黑树其他的所有路径进行检查可见新插入结点如果默认是BLACK会存在着牵一发而动全身的影响。而让新插入结点默认是RED则不会出现这样的结果。假如新插入结点的 parent 恰好是 BLACK那这次插入就没有什么问题。如果新插入结点是 parent 是 RED此时需要对这颗红黑树稍作调整。
三、红黑树的框架
templateclass K, class V
class RBTree {typedef RBTreeNodeK, V Node;
public:// 成员函数...
private:Node* _root;
};四、旋转操作
这里我们只举例2种情况一种是左单旋另一种是右单旋另外两种双旋可以观看我的前文。
// 左单旋
void RotateL(Node* parent) {Node* cur parent-right;Node* curleft cur-left;parent-right curleft; cur-left parent;if (curleft) curleft-_parent parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root) {_root cur;cur-_parent nullptr; }else {if (ppnode-left parent) ppnode-left cur;else ppnode-right cur;cur-_parent ppnode;}
}// 右单旋
void RotateR(Node* parent) {Node* cur parent-left;Node* curright cur-right;parent-left curright;cur-right parent;if (curright) curright-_parent parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root) {_root cur;cur-_parent nullptr;}else {if (ppnode-left parent) ppnode-left cur;else ppnode-right cur;cur-_parent ppnode;}
}五、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上平衡限制条件因此红黑树的插入可以分为两步 按照二叉搜索树的规则插入结点。 检测新节点插入后红黑树的性质是否遭到破坏。
因为新结点的默认颜色是 RED因此如果其双亲结点的颜色是 BLACK没有违反红黑树任何性质则不需要调整但是当新插入节点的双亲结点颜色为 RED 时就违反了性质四不能有连在一起的红色结点此时需要对红黑树分情况来讨论
约定cur为当前结点parent 为父结点grandfather 为祖父结点uncle 为叔叔结点。如果 parent 为红那 grandfather 一定为黑。所以当前唯一不确定的就是 uncle主要分以下三种情况
5.1 uncle结点存在且为红
由于每条路径上的黑色结点的时候连带着uncle和grandfather结点也要一起更新。根据规则红色结点不能连续故需要往上继续更新。 5.2 uncle结点不存在或者存在且为黑 5.3 插入操作的全部代码
bool insert(const pr kv) {if (!_root) {_root new Node(kv);_root-_col BLACK;return true;}// 定义当前节点curNode* cur _root;Node* parent nullptr;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; // 不可能出现相等的情况插入}// 创建新的Node实例cur并将它插入到适当的位置cur new Node(kv);cur-_col RED;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 (grandfather-left parent) {// 叔叔存在且为红if (uncle uncle-_col RED) {parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}// 叔叔不存在或者存在且为黑else {if (cur parent-left) {RotateR(grandparent);parent-_col BLACK;grandfather-_col RED;}else {RotateL(cur);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}}}// 父亲是祖父的右孩子else {// 叔叔存在且为红if (uncle uncle-_col RED) {parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}// 叔叔不存在或者存在且为黑else {if (cur parent-right) {RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else {RotateR(cur);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}}}}return true;
}5.4 测试插入
红黑树的检测分为两步
检测其是否满足二叉搜索树中序遍历是否为有序序列。检测其是否满足红黑树的性质主要是性质四和性质五。
成员函数
// 调用判断平衡的函数
bool IsBalance() {return IsBalance(_root);
}// 判断平衡
bool IsBalance(Node* root) {if (!root) return true;if (root-_col ! BLACK) return false;// 随便找一条路径这里我们选择最左路径int benchmark 0;Node* cur _root;while (cur) {if (cur-_col BLACK) {benchmark;}cur cur-left;}return CheckColor(root, 0, benchmark);
}// 主要检查有无连续的红色结点
bool CheckColor(Node* root, int blacknum, int benchmark) {if (!root) {if (blacknum ! benchmark) {return false;}return true;}if (root-_col BLACK) blacknum;if (root-_col RED root-_parent root-_parent-_col RED) {cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColor(root-left, blacknum, benchmark) CheckColor(root-right, blacknum, benchmark);
}// 调用中序遍历
void InOrder() {return InOrder(_root);
}// 中序遍历
void InOrder(Node* root) {if (!root) return;InOrder(root-left);cout root-_kv.first ;InOrder(root-right);
}测试代码
#include RBTree.hint main() {int a[] { 1, 5, 7, 16, 25, 36, 44, 55,6, 32, 9 };RBTreeint, int rbt;for (auto e : a) {rbt.insert(make_pair(e,e));rbt.InOrder();cout endl;if (rbt.IsBalance()) {cout 插入成功 endl;}else {cout 插入失败 endl;}}return 0;
}六、AVL树和红黑树的性能比较
AVL树和红黑树是两种常用的自平衡二叉搜索树各有优缺点。以下是它们在性能方面的比较
6.1 平衡性
AVL树始终保持严格平衡任何节点的两个子树高度差不超过1。这使得AVL树在查找操作时的高度更小查找速度较快。红黑树相对宽松的平衡条件通过颜色属性和旋转操作维护平衡。虽然高度比AVL树大但仍然保持在O(log n)的范围内。
6.2 查找操作
AVL树查找操作效率更高时间复杂度为O(log n)因为树的高度较小。红黑树查找操作的时间复杂度同样为O(log n)但由于可能较高的树高度平均查找速度稍慢。
6.3 插入和删除操作
AVL树插入和删除后树可能需要更多的旋转来恢复平衡因此插入和删除的时间复杂度为O(log n)但常数因子较高。红黑树插入和删除操作相对简单所需的旋转次数较少性能上通常更快时间复杂度为O(log n)。
6.4 内存使用
AVL树每个节点需要存储额外的平衡因子内存开销相对较大。红黑树每个节点需要存储颜色信息内存开销相对较小。
6.5 使用场景
AVL树适用于需要频繁查找操作的场景如数据库索引等。红黑树适用于插入和删除操作较为频繁的场景如 STL 中的 std::map 和 std::set 实现。
总结
AVL树更适合查找频繁的场合提供较快的查找速度。红黑树则在插入和删除性能上表现更好适合对这些操作有较高频率的场景。 结语
红黑树不仅是一种数据结构更是一种智慧的象征。它巧妙地平衡了插入、删除与查找操作之间的矛盾为开发者在处理复杂数据时提供了强大的支持。通过对红黑树的深入理解我们不仅能提升自身的编程能力更能在数据处理的艺术中找到更为优雅的解决方案。希望本篇博文能够为你在数据结构的探索之路上带来新的启发与思考。
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下17的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是17前进的动力
