装修设计那个网站好,营销培训心得,wordpress显示加载耗时,Wordpress全站404红黑树 1. 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树结构5. 红黑树的插入操作5.1 按照二叉搜索的树规则插入新节点5.2 检测新节点插入后#xff0c;红黑树的性质是否造到破坏5.2.1 情况一: cur为红#xff0c;p为红#xff0c;g为黑#xff0c;u存在且为红… 红黑树 1. 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树结构5. 红黑树的插入操作5.1 按照二叉搜索的树规则插入新节点5.2 检测新节点插入后红黑树的性质是否造到破坏5.2.1 情况一: cur为红p为红g为黑u存在且为红5.2.2 情况二: cur为红此时只需要单旋p为红g为黑u不存在/u存在且为黑5.2.3 情况三: cur为红此时需要进行双旋变成情况二p为红g为黑u不存在/u存在且为黑 完整代码6. 红黑树的验证1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)2. 检测其是否满足红黑树的性质 7. 红黑树与AVL树的比较8. 红黑树的应用 注本文的是在理解AVL树的基础上进行讲解的 AVL树的实现万字图文详解 1. 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
2. 红黑树的性质
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 红黑树中的性质确保了任意路径上的黑色节点数量相等这是红黑树能够保持平衡的关键。根据这个性质我们可以证明红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍。假设红黑树的最短路径上的黑色节点数量为k。由于性质5任意路径上的黑色节点数量相等所以最长路径上的黑色节点数量不能少于k个。现在我们来看最长路径上的节点个数。由于性质4红色节点的两个子节点都是黑色的因此最长路径上不能有连续的红色节点。而对于红黑树而言最长路径上的红色节点数量最多为k因为最长路径上的黑色节点数量不能少于k个。所以最长路径上的节点个数最多为2k其中k个是黑色节点k个是红色节点。综上所述红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍即最长路径上的节点个数最多为2k其中k为最短路径上的黑色节点数量。这个性质保证了红黑树的高度始终保持在较小的范围内从而保持了树的平衡性。因为红黑树的高度与最长路径上的节点个数成正比所以最长路径的节点个数的上限为最短路径的节点个数的两倍确保了红黑树的平衡性和高效性。 3. 红黑树节点的定义
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;int _bf;RBTreeNode(const pairK, V kv):_left(nullptr)//左孩子, _right(nullptr)//右孩子, _parent(nullptr)//父亲, _kv(kv)//存储键值对的成员变量, _col(RED)//默认红色{}
}; 具体解释如下 _left指向左子节点的指针。_right指向右子节点的指针。_parent指向父节点的指针。_kv存储键值对的成员变量。这里使用了 pairK, V 类型来表示键值对其中 K 是键的类型V 是值的类型。_col表示节点的颜色。这里使用了 Colour 枚举类型来表示可能的取值为 RED 或 BLACK其中 RED 表示红色BLACK 表示黑色。_bf平衡因子用于平衡二叉树的调整。 4. 红黑树结构
为了后续实现关联式容器简单红黑树的实现中增加一个头结点因为根节点必须为黑色为了与根节点进行区分将头结点给成黑色并且让头结点的 pParent 域指向红黑树的根节点pLeft域指向红黑树中最小的节点_pRight域指向红黑树中最大的节点。 如下
5. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
5.1 按照二叉搜索的树规则插入新节点
#pragma once
#include iostream
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;int _bf;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//默认红色{}
};templateclass K, class V
class 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;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}红黑树开整//1.cur为红parent为红grandfather为黑uncle存在且为红//解决方法p,u变成黑g变成红cg继续向上调整//2.cur为红parent为红grandfather为黑,uncle不存在 or 存在且为黑//解决方法: 单旋p变红g变黑//双旋c变黑g变红private:Node* _root nullptr;
};5.2 检测新节点插入后红黑树的性质是否造到破坏 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
5.2.1 情况一: cur为红p为红g为黑u存在且为红 解决方法将p,u改为黑g改为红然后把g当成cur继续向上调整。 5.2.2 情况二: cur为红此时只需要单旋p为红g为黑u不存在/u存在且为黑 解决方法 p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色–p变黑g变红 5.2.3 情况三: cur为红此时需要进行双旋变成情况二p为红g为黑u不存在/u存在且为黑 解决方法 p为g的左孩子cur为p的右孩子则针对p做左单旋转再对g右单旋即可完成调整相反 p为g的右孩子cur为p的左孩子则针对p做右单旋转 再对g左单旋即可完成调整 完整代码
#pragma once
#include iostream
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;int _bf;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//默认红色{}
};templateclass K, class V
class 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;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}红黑树开整//1.cur为红parent为红grandfather为黑uncle存在且为红//解决方法p,u变成黑g变成红cg继续向上调整//2.cur为红parent为红grandfather为黑,uncle不存在 or 存在且为黑//解决方法: 单旋p变红g变黑//双旋c变黑g变红//parent不为空且parent-_colRED这样保证肯定有祖先也就是grandfather不为空while (parent parent-_col RED){// g// p u//cNode* grandfather parent-_parent;if (parent grandfather-_left){// g// p u//cNode* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上更新处理cur grandfather;parent cur-_parent;//这儿parent更新完之后可能为空为空就结束}else//uncle不存在 or 存在且为黑{ //单旋// g// p u//cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;//p变黑grandfather-_col RED;//g变红}else if (cur parent-_right){//双旋// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}// g// u p// celse// parent grandfather-_left{Node* uncle grandfather-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上更新处理cur grandfather;parent cur-_parent;}else//(uncle不存在 or 存在且为黑){ //单旋// g // u p // c if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;//p变黑grandfather-_col RED;//g变红} else//cur parent-_left {//双旋// g// u p// c RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//管你根节点更新成啥了管你个求直接把_root-_col改成黑色_root-_col BLACK;return true;}//左单旋//1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点//【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】void RotateL(Node* parent){Node* SubR parent-_right;Node* SubRL SubR-_left;//旋转链接parent-_right SubRL;SubR-_left parent;Node* Parent_Parent parent-_parent;parent-_parent SubR;if (SubRL){SubRL-_parent parent;}//和父节点的父节点链接if (_root parent){_root SubR;SubR-_parent nullptr;}else{if (Parent_Parent-_left parent){Parent_Parent-_left SubR;}else{Parent_Parent-_right SubR;}SubR-_parent Parent_Parent;}}//右单旋void RotateR(Node* parent){Node* SubL parent-_left;Node* SubLR SubL-_right;//旋转链接//动一个节点就把他的父亲也变动parent-_left SubLR;if (SubLR)//SubLR可能为空{SubLR-_parent parent;}Node* Parent_Parent parent-_parent;SubL-_right parent;parent-_parent SubL;//和父节点的父节点链接if (_root parent){_root SubL;SubL-_parent nullptr;}else{if (Parent_Parent-_left parent){Parent_Parent-_left SubL;}else{Parent_Parent-_right SubL;}SubL-_parent Parent_Parent;//链接}}void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}//根节点到当前这条路径的黑色节点个数bool Check(Node *root,int blacknum,const int RefVal){if (root nullptr){if (blacknum ! RefVal){return false;}return true;}//直接反向检查儿子很复杂父亲只有一个if (root-_col RED root-_parent-_col RED){cout有连续的红节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, RefVal) Check(root-_right, blacknum, RefVal);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED){return false;}int blacknum 0;//记录每条路径的黑色节点个数int RefVal 0;//定一个标准Node* cur _root;while (cur)//改了一个bug 之前这儿脑子抽抽了写成了if{if (cur-_col BLACK){RefVal;}cur cur-_left;}return Check(_root, blacknum,RefVal);}private:Node* _root nullptr;
};6. 红黑树的验证
红黑树的检测分为两步
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
#include vector
#include RBTree.hint main()
{int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int a;for (auto e : arr){a.insert(make_pair(e, e));}a.InOrder();return 0;
}2. 检测其是否满足红黑树的性质
我们可以通过递归地遍历红黑树的节点并统计根节点到每个叶子节点路径上的黑色节点个数来进行检查。
//根节点到当前这条路径的黑色节点个数
bool Check(Node *root,int blacknum,const int RefVal)
{if (root nullptr){if (blacknum ! RefVal){return false;}return true;}//直接反向检查儿子很复杂父亲只有一个if (root-_col RED root-_parent-_col RED){cout有连续的红节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, RefVal) Check(root-_right, blacknum, RefVal);
}bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col RED){return false;}int blacknum 0;//记录每条路径的黑色节点个数int RefVal 0;//定一个标准Node* cur _root;while (cur)//改了一个bug 之前这儿脑子抽抽了写成了if{if (cur-_col BLACK){RefVal;}cur cur-_left;}return Check(_root, blacknum,RefVal);
}函数讲解 Check 函数是一个递归函数用于检查从当前节点到叶子节点的路径上的黑色节点个数是否与参考值 RefVal 相等。参数 root 表示当前节点指针blacknum 表示根节点到当前节点的路径上的黑色节点个数RefVal 是参考值。 如果当前节点为空指针即到达了叶子节点那么检查路径上的黑色节点个数 blacknum 是否等于参考值 RefVal如果不相等则返回 false否则返回 true。如果当前节点的颜色为红色并且父节点也是红色表示存在连续的红节点不符合红黑树的性质返回 false。如果当前节点的颜色为黑色将 blacknum 值加一。递归地调用 Check 函数检查左子节点和右子节点并将当前节点的黑色节点个数 blacknum 作为参数传递。 IsBalance 函数用于检查整个红黑树是否符合红黑树的性质。 如果红黑树为空树即根节点为空认为是一棵合法的红黑树返回 true。如果根节点的颜色是红色违反了红黑树的性质返回 false。初始化 blacknum 为 0用于记录每条路径的黑色节点个数。初始化 RefVal 为 0作为参考值。通过遍历从根节点到最左子节点的路径统计参考值 RefVal即路径上的黑色节点个数。调用 Check 函数传入根节点、路径上的黑色节点个数 blacknum 和参考值 RefVal 进行检查。 #include vector
#include RBTree.h
int main()
{const int N 30;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand()%100 );}RBTreeint, int t;for (auto e : v){if (e 0){int i 0;}t.insert(make_pair(e, e));cout Insert e - t.IsBalance() endl;}t.InOrder();//中序打印if (t.IsBalance()){cout 是平衡二叉树 endl;}else{cout 不是平衡二叉树 endl;}return 0;
}7. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
8. 红黑树的应用 C STL库 – map/set、mutil_map/mutil_set C STL中的std::map和std::set这些容器类通常使用红黑树作为底层数据结构提供了高效的查找、插入和删除操作。 数据库系统红黑树常被用作数据库索引结构例如在关系型数据库中可以使用红黑树来实现B树索引提供高效的数据检索和排序功能。 线程调度器操作系统中的线程调度器通常需要高效地管理和调度线程红黑树可用于实现定时器和任务调度器以快速查找和处理就绪的线程。 路由算法在网络路由算法中红黑树可以用于快速查找最佳路径和路由表项提供高效的路由查找和转发功能。 linux内核 文件系统某些文件系统使用红黑树来管理文件和目录的索引以支持快速的文件查找和访问。 编译器和解释器在编译器和解释器中红黑树可以用于符号表的实现以支持快速的符号查找和关联。 并发数据结构在多线程和并发编程中红黑树可以用于实现并发安全的数据结构例如并发哈希表、并发有序集合等。
本章完
