网站建设用图,网站建设的公司价格,php网站开发环境配置,wordpress目录分类了解红黑树并将其模拟实现 红黑树的概念和性质1. 概念2. 性质 红黑树的结构红黑树的节点定义及红黑树结构成员定义红黑树的插入1. 按照二叉搜索的树规则插入新节点2. 检测新节点插入后#xff0c;红黑树的性质是否造到破坏情况一: cur为红#xff0c;p为红#xff0c;g为黑红黑树的性质是否造到破坏情况一: cur为红p为红g为黑u存在且为红情况二: cur为红p为红g为黑u不存在/u存在且为黑情况三: cur为红p为红g为黑u不存在/u存在且为黑 3. 插入代码解析4. 插入动态效果1. 以升序插入构建红黑树2. 以降序插入构建红黑树3. 随机插入构建红黑树 红黑树的验证红黑树的遍历输出和左旋右旋1. 遍历输出2. 左单旋3. 右单旋 红黑树模拟实现全部代码红黑树的应用红黑树与AVL树的比较 红黑树的概念和性质
1. 概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的 2. 性质
每个节点要么是红色要么是黑色。根节点是黑色的。如果一个节点是红色的那么它的两个子节点都是黑色的。从任意节点到其每个叶子节点的每条路径都包含相同数量的黑色节点这被称为“黑高相等性”。每个叶子节点NIL节点通常表示为空节点是黑色的。
红黑树的这些性质确保了树的平衡性从而保证了树的高度在对数范围内使得基本操作的时间复杂度保持在O(log n)级别
红黑树的结构
为了后续实现关联式容器简单红黑树的实现中增加一个头结点因为跟节点必须为黑色为了与根节点进行区分将头结点给成黑色并且让头结点的 pParent 域指向红黑树的根节点pLeft域指向红黑树中最小的节点_pRight域指向红黑树中最大的节点。
当在红黑树的实现中增加一个头结点时目的是为了简化操作和处理边界情况而不必为特殊情况单独编写代码。这个头结点通常是一个黑色节点位于红黑树的根节点之上其pParent指向红黑树的根节点pLeft指向红黑树中最小的节点pRight指向红黑树中最大的节点。
以下是对头结点的作用和实现细节的解释
简化边界条件处理头结点的存在使得根节点始终是黑色的因为根节点是头结点的右子节点。这样在插入和删除等操作中不需要特殊情况处理根节点的颜色和父节点是否存在的问题。快速访问最小和最大节点头结点的pLeft指向红黑树中最小的节点pRight指向最大的节点。这意味着你可以在O(1)时间内找到树中的最小和最大节点而无需进行遍历。统一根节点访问无论是插入、删除还是其他操作都可以始终从头结点开始进行操作因为头结点的pParent指向了真正的根节点。这简化了代码逻辑因为你不必特殊处理根节点的情况。
下面是一个头结点的示例实现
struct Node {int data;Color color;Node* left;Node* right;Node* parent;
};class RedBlackTree {
private:Node* root; // 实际的根节点Node* header; // 头结点// ...其他成员函数和辅助函数...public:RedBlackTree() : root(nullptr), header(new Node) {header-color BLACK;header-left nullptr;header-right nullptr;header-parent nullptr;}// ...其他公共成员函数...
};在这个示例中我们添加了一个名为header的成员变量它是一个指向头结点的指针。头结点的初始化在构造函数中完成并确保它始终是黑色的根节点则位于头结点的pParent中。头结点的存在将简化红黑树的操作和边界情况处理。
这是一种实现方式,但在后面我们实现不是采用的这种方式,当然你也可以选择这种方式实现,更为简易,红黑树的实现过程只是为了让我们更熟悉它的底层,现实中需要我们实现的场景很少。
红黑树的节点定义及红黑树结构成员定义
这里我们的实现采用了三叉链的形式,后面我们会提到这种写法的好处
我们这里使用键值对的模板是为了方便后期模拟实现map和set
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){}
};templateclass K, class V
struct RBTree
{typedef RBTreeNodeK,V Node;
private:Node* _root nullptr;
};枚举类型 Colour这里定义了一个枚举类型包括两个成员 RED 和 BLACK。这个枚举类型用于表示红黑树中节点的颜色。在红黑树中节点可以是红色或黑色用这个枚举类型来表示节点颜色是一种常见的做法。 结构体 RBTreeNodeK, V这个结构体定义了红黑树的节点结构其中包含以下成员变量 _left 和 _right分别指向节点的左子节点和右子节点的指针。_parent指向节点的父节点的指针。_kv用于存储键值对Key-Value Pair的成员变量。这个键值对通常用于存储节点的数据。_col表示节点的颜色可以是 RED 或 BLACK。 构造函数 RBTreeNode(const pairK, V kv) 用于初始化节点对象将各个成员变量赋初值包括键值对 _kv 和颜色 _col。 结构体 RBTreeK, V这个结构体定义了整个红黑树的结构其中包含以下成员变量和一个别名 _root指向红黑树的根节点的指针。根节点是红黑树的起始点所有操作都从根节点开始。 typedef RBTreeNodeK,V Node; 定义了一个别名 Node用于表示红黑树节点的类型。这样做可以简化代码使得在代码中引用节点类型更加方便。
红黑树的插入
1. 按照二叉搜索的树规则插入新节点
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);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* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);if (parent grandfater-_left)//具体看下面讲解{Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色if (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三左右单旋变色RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色if (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三右左单旋变色RotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;
}其实前面的代码和我们上一篇讲到的AVL树的插入类似,只不过这里的红黑树没有了平衡因子,而变为了颜色
接下来我们看每种情况的解析
2. 检测新节点插入后红黑树的性质是否造到破坏
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
情况一: cur为红p为红g为黑u存在且为红 cur和p均为红解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整
情况二: cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转,p、g变色–p变黑g变红
情况三: cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2
3. 插入代码解析
如果 _root 是空的表示红黑树为空那么将创建一个新的节点 _root并将其颜色设置为黑色。这是根节点并且遵循红黑树规则的规定根节点必须为黑色。如果 _root 不为空那么代码会在树中查找正确的位置来插入新节点。通过遍历树的方式找到正确的父节点 parent以及新节点要插入的位置 cur。如果要插入的键已经存在于树中就返回 false因为不允许键重复。创建新节点 cur 并将其颜色设置为红色。新节点的颜色一开始设置为红色这是为了满足红黑树的性质。然后代码进入一个循环循环的目的是确保插入新节点后仍然满足红黑树的性质。这是红黑树插入操作的关键部分。 在循环中首先查看 parent 节点的颜色如果 parent 是红色那么需要进一步处理来保持红黑树性质。然后代码会检查 uncle 节点的颜色即 parent 的兄弟节点。根据 uncle 的颜色分为情况一、情况二和情况三。最后退出循环后将根节点的颜色设置为黑色以确保根节点满足红黑树的性质。
4. 插入动态效果
1. 以升序插入构建红黑树 2. 以降序插入构建红黑树 3. 随机插入构建红黑树 红黑树的验证
bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED)//检查根节点是否为黑{cout 根节点不是黑色 endl;return false;}// 黑色节点数量基准值int benchmark 0;return PrevCheck(_root, 0, benchmark);}返回值函数PrevCheck的实现
bool PrevCheck(Node* root, int blackNum, int benchmark)
{if (root nullptr){if (benchmark 0){benchmark blackNum;return true;}if (blackNum ! benchmark){cout 某条黑色节点的数量不相等 endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return PrevCheck(root-_left, blackNum, benchmark) PrevCheck(root-_right, blackNum, benchmark);
}黑高度相同性质检查函数使用递归方式遍历树中的节点并维护一个 blackNum 变量用于跟踪从根节点到当前节点经过的黑色节点数。在遍历过程中它会检查每条从根到叶子节点的路径上的黑色节点数是否相同。如果路径上的黑色节点数不相同说明违反了红黑树的性质。连续红色节点检查在遍历的过程中代码还检查是否存在连续的红色节点。在红黑树中不允许存在相邻的两个红色节点。如果存在连续的红色节点也违反了红黑树的性质。返回值函数返回一个布尔值用于指示红黑树是否满足性质。如果在遍历过程中发现任何性质被破坏函数将返回 false否则返回 true。
这个函数是用于验证红黑树的一种常见方法用于检查树是否保持了红黑树的性质包括黑高度相同和不连续的红色节点。如果该函数返回 true则表示树是一个有效的红黑树否则表示树的结构违反了红黑树的性质。
红黑树的遍历输出和左旋右旋
1. 遍历输出
void _InOrder(Node* root)
{if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);
}这里的遍历是一种按照节点值的大小顺序遍历二叉搜索树BST的方法。在这里红黑树也是一种BST因此中序遍历可以用来按键的顺序输出树中的节点。
函数的主要逻辑包括
如果输入的 root 节点为空即树为空则直接返回不执行任何操作。否则函数会递归地执行以下操作 先递归调用 _InOrder 函数来遍历左子树左子节点。输出当前节点的键值对这里假设键是整数值是整数根据需要调整输出格式。最后递归调用 _InOrder 函数来遍历右子树右子节点。
2. 左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (_root parent){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}首先将 parent 节点的右子节点 subR 和 subR 的左子节点 subRL 分别保存起来。subR 将会成为新的根节点而 subRL 将成为 parent 节点的右子节点。接下来将 parent 节点的右子节点指针 _right 指向 subRL同时确保 subRL 的父指针 _parent 指向 parent。这一步是将 subRL 与 parent 连接起来。将 parent 节点的父节点指针 ppNode 保存起来。这是为了在旋转后更新 ppNode 的左子节点或右子节点指向 subR以确保树的连接正确。将 subR 的左子节点指针 _left 指向 parent同时将 parent 的父节点指针 _parent 指向 subR。这一步是将 parent 旋转到 subR 的位置上。接下来处理根节点的情况。如果 _root 指向 parent那么现在 _root 应该指向 subR因此将 _root 更新为 subR并将 subR 的父指针设置为 nullptr。如果 _root 不指向 parent则需要根据 ppNode 的情况来更新 ppNode 的左子节点或右子节点指向 subR以确保整棵树的连接正确。
左单旋和右单旋和我们之前的AVL树实现基本一致若不能理解请看上一篇文章
3. 右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}首先将 parent 节点的左子节点 subL 和 subL 的右子节点 subLR 分别保存起来。subL 将会成为新的根节点而 subLR 将成为 parent 节点的左子节点。接下来将 parent 节点的左子节点指针 _left 指向 subLR同时确保 subLR 的父指针 _parent 指向 parent。这一步是将 subLR 与 parent 连接起来。将 parent 节点的父节点指针 ppNode 保存起来。这是为了在旋转后更新 ppNode 的左子节点或右子节点指向 subL以确保树的连接正确。将 subL 的右子节点指针 _right 指向 parent同时将 parent 的父节点指针 _parent 指向 subL。这一步是将 parent 旋转到 subL 的位置上。接下来处理根节点的情况。如果 _root 指向 parent那么现在 _root 应该指向 subL因此将 _root 更新为 subL并将 subL 的父指针设置为 nullptr。如果 _root 不指向 parent则需要根据 ppNode 的情况来更新 ppNode 的左子节点或右子节点指向 subL以确保整棵树的连接正确。
红黑树模拟实现全部代码
#pragma once
#includeiostream
#includeassert.h
#includetime.h
using namespace std;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){}
};templateclass K, class V
struct RBTree
{typedef RBTreeNodeK,V Node;
public: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);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* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色if (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三左右单旋变色RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色if (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三右左单旋变色RotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED){cout 根节点不是黑色 endl;return false;}// 黑色节点数量基准值int benchmark 0;return PrevCheck(_root, 0, benchmark);}private:bool PrevCheck(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark 0){benchmark blackNum;return true;}if (blackNum ! benchmark){cout 某条黑色节点的数量不相等 endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return PrevCheck(root-_left, blackNum, benchmark) PrevCheck(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (_root parent){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}private:Node* _root nullptr;
};红黑树的应用
红黑树是一种自平衡的二叉搜索树由于其平衡性和高效性能广泛用于各种计算机科学和软件工程领域。以下是一些红黑树的常见应用
C STL中的std::map和std::setC标准模板库STL中的std::map和std::set通常使用红黑树实现。它们用于实现有序的关联容器其中键值对被自动排序并保持平衡以支持高效的查找、插入和删除操作。数据库系统红黑树常用于数据库系统中的索引结构如B树的实现中。数据库中的索引需要高效地支持查找、范围查询和排序等操作而红黑树是一种性能良好的选择。操作系统红黑树在操作系统中用于进程调度、虚拟内存管理和文件系统的实现。在这些场景中需要高效的数据结构来管理和操作各种系统资源。网络路由表红黑树被广泛用于路由表的实现以支持网络路由器和交换机等网络设备的高效路由查找。编译器编译器可以使用红黑树来管理符号表以便进行语法分析、类型检查和代码生成。计算机图形学在计算机图形学中红黑树可用于空间分割数据结构如八叉树和四叉树的实现以支持高效的图形渲染和碰撞检测。高性能库和框架红黑树常被用作高性能库和框架中的核心数据结构以提供高效的数据管理和操作功能。实时系统实时系统需要高效的数据结构来管理任务和事件红黑树可以用于实现定时器和调度器。
总的来说红黑树是一种多功能的数据结构适用于需要高效的自平衡二叉搜索树的任何领域特别是需要高效的插入、删除和查找操作的场景。其平衡性和性能使其成为各种应用中的重要工具。
红黑树与AVL树的比较
红黑树Red-Black Tree和AVL树Adelson-Velsky and Landis Tree都是自平衡二叉搜索树它们在维护平衡性和支持高效的插入、删除和查找操作方面有很多相似之处但也有一些关键的区别。以下是红黑树和AVL树之间的比较
平衡性要求 红黑树红黑树放宽了平衡性要求它保证了树的高度最多是其2倍。AVL树AVL树要求更为严格它保证树的高度差不超过1因此AVL树的平衡性更强。 性能 红黑树由于平衡性要求相对较低插入和删除操作在平均情况下可能比AVL树更快因此在那些需要频繁插入和删除操作的场景中红黑树可能更适合。AVL树AVL树在查找操作上可能稍微快一些因为它的平衡性更严格但它的插入和删除操作可能更慢因为它需要更频繁地执行旋转操作来保持平衡。 旋转操作 红黑树红黑树的旋转操作相对较少因为它放宽了平衡性要求。通常红黑树的旋转操作较少但需要更多的颜色变换操作来保持平衡。AVL树AVL树的旋转操作更频繁因为它要求更严格的平衡性。这可能导致在插入和删除操作中执行更多的旋转。 内存消耗 红黑树由于红黑树的平衡性要求较低通常会消耗更少的内存因为不需要额外的平衡因子来跟踪节点的高度差。AVL树AVL树需要为每个节点存储平衡因子这可能会导致更多的内存消耗。 应用场景 红黑树适用于需要高效的插入和删除操作而对查找操作的性能要求相对较低的场景如C的STL中的std::map和std::set。AVL树适用于对查找操作有更高性能要求的场景但可以容忍较慢的插入和删除操作的情况如数据库索引。
总的来说选择使用红黑树还是AVL树取决于应用的需求和性能要求在C的map和set的实现中底层调用的就是红黑树但在实际的面试和工作中红黑树的应用可能更为广泛。
