网站页面标题设置,wordpress如何将文章链接,wordpress是英文版的,大型网站设计网站#x1f307;前言
红黑树是一种自平衡的二叉搜索树#xff0c;因其出色的性能#xff0c;广泛应用于实际中。Linux 内核中的 CFS 调度器便是一个使用红黑树的例子#xff0c;这足以说明它的重要性。红黑树的实现通过红黑两种颜色的控制来维持平衡#xff0c;并在必要时使…前言
红黑树是一种自平衡的二叉搜索树因其出色的性能广泛应用于实际中。Linux 内核中的 CFS 调度器便是一个使用红黑树的例子这足以说明它的重要性。红黑树的实现通过红黑两种颜色的控制来维持平衡并在必要时使用旋转操作来降低树的高度使之保持平衡。
️正文
1. 认识红黑树
红黑树最初由德国慕尼黑大学的 Rudolf Bayer 教授于1978年发明后来由 Leo J. Guibas 和 Robert Sedgewick 修改为我们今天所熟悉的红黑树。红黑树在二叉搜索树的基础上增加了颜色属性通过一些规则降低树的高度。
与 AVL 树的严格平衡策略不同红黑树仅在需要时进行旋转从而减少了旋转操作的开销。虽然 AVL 树在极端情况下可能比红黑树快一倍但红黑树在插入、删除、修改操作中性能更优。 1.1、红黑树的定义
红黑树 也是 三叉链 结构不过它没有 平衡因子取而代之的是 颜色。 红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
templateclass ValueType
struct RBTreeNode
{
RBTreeNode(const ValueType data ValueType()Color color RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNodeValueType* _pLeft; // 节点的左孩子
RBTreeNodeValueType* _pRight; // 节点的右孩子
RBTreeNodeValueType* _pParent; // 节点的双亲(红黑树需要旋转为了实现简单给
出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
}
注意 定义新节点时颜色可以为 红 也可以为 黑推荐为 红色具体原因后面解释。
1.2 红黑树的性质
红黑树有以下五条性质
每个节点不是红色就是黑色。根节点是黑色的。如果一个节点是红色那么它的两个子节点必须是黑色不能有连续的红节点。从任一节点到其所有后代的叶子节点的路径中都包含相同数量的黑色节点。每个叶子节点都是黑色的空节点。
1.3 红黑树的特点
红黑树在插入节点时默认将新节点颜色设为红色。这种设计简化了调整因为红色新节点仅在特定条件下会触发旋转调整。
红黑树的路径特点如下
最长路径红黑相间最短路径全是黑节点
红黑树在极端情况下最长路径为最短路径的两倍但这种情况很少见。因此在实际应用中红黑树的查询性能与 AVL 树差异不大而在涉及旋转的操作中红黑树优势明显。 2. 红黑树的插入操作
2.1、抽象图
在演示 红黑树 的插入操作时也需要借助 抽象图此时的 抽象图 不再代表高度而是代表 黑色节点 的数量。 2.2、插入流程
红黑树 的插入流程也和 二叉搜索树 基本一致先找到合适的位置然后插入新节点当节点插入后需要对颜色进行判断看看是否需要进行调整
插入流程 判断根是否为空如果为空则进行第一次插入成功后返回 true 找到合适的位置进行插入如果待插入的值比当前节点值大则往 右 路走如果比当前节点值小则往 左 路走 判断父节点与新节点的大小关系根据情况判断链接至 左边 还是 右边 根据颜色判断是否需要进行 染色、旋转 调整高度 整体流程如下不包括染色调整的具体实现
bool Insert(const std::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);if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_parent parent;//判断是否需要 染色、旋转while (parent parent-_col RED){Node* grandfather parent-_parent; //祖父节点//……}return true;
}红黑树 如何调整取决于 叔叔即父亲的兄弟节点 。并且如果父亲为黑直接插入就行了不必调整 如果父亲为红并且叔叔也为红可以只通过染色解决当前问题然后向上走继续判断是否需要调整如果父亲为红并且叔叔为黑或者叔叔不存在此时需要 旋转 染色根据当前节点与父亲的位置关系选择 单旋 或 双旋值得一提的是旋转 染色 后不必再向上判断可以直接结束调整 关于旋转的具体实现这里不再展开叙述可以复用 AVL 中的旋转代码并且最后不需要调整平衡因子 《C【AVL树】》 注意红黑树的调整可以分为 右半区 和 左半区 两个方向根据 grandfather 与 parent 的位置关系而定每个方向中都包含三种情况单纯染色、单旋染色、双旋染色逐一讲解费时费力并且两个大方向的代码重复度极高因此 下面的旋转操作基于 右半区 左半区 的操作和 右半区 基本没啥区别可以去完整代码中求证。
2.3、单纯染色
如果父亲为黑色则不需要调整不讨论这种情况下面三种情况基本要求都是父亲为红
当新节点插入后如果 叔叔 节点也为 红色那么可以通过将 祖父 节点的黑色素下放给 父亲和叔叔祖父节点 变为 红色这样调整仍可确保 每条路径中的黑色节点数目相同
单次染色还不够需要从 grandfather 处继续向上判断是否需要 调整单纯染色后向上判断可能会变成其他情况这是不确定的具体情况具体分析
单纯染色 的操作如下
注意c 表示当前节点p 表示父亲节点u 表示叔叔节点g 表示祖父节点 修正 动图中语句修正为 “父亲为红叔叔也为红直接染色即可” 当 单次染色 结束后更新 cur 至 grandfather 的位置并同步更新 parent继续判断是需要进行 单纯染色、单旋 染色 还是 双旋 染色 本质将公共的黑色下放给两个孩子。
代码
//在右半区操作
Node* uncle grandfather-_left; //叔叔节点if (uncle uncle-_col RED)
{//染色、向上更新即可grandfather-_col RED;parent-_col uncle-_col BLACK;cur grandfather;parent cur-_parent;
}
else
{//此时需要 旋转 染色//……
}叔叔 存在且为 红 很好处理难搞的是 叔叔 不存在或 叔叔 为 黑需要借助 旋转 降低高度
注意 此时的五个抽象图都代表同一个具象图如果 parent 为空证明 cur 为根节点此时需要把根节点置为 黑色在返回 true 前统一设置即可。
2.4、左单旋 染色
单旋右右、左左此时在 右半区所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 右边 时可以通过 左单旋 降低高度
如果在左半区节点位于父亲的左边时则使用 右单旋 降低高度
在高度降低后需要使用 染色 确保符合 红黑树 的性质
旋转 思想很巧妙在 旋转 染色 后可以跳出循环结束调整
左旋转 染色 的操作如下
注意c 表示当前节点p 表示父亲节点u 表示叔叔节点g 表示祖父节点 显然旋转 染色 后parent 是一定会被修改为 黑色 的所以不必再往上判断调整因为现在已经很符合性质了即使 parent 的父亲是 红色也不会出现连续的 红色节点
本质将 parent 的左孩子托付给 grandfather 后parent 往上提并保证不违背性质。
//在右半区操作
Node* uncle grandfather-_left; //叔叔节点if (uncle uncle-_col RED)
{//染色、向上更新即可//……
}
else
{//此时需要 旋转 染色if (parent-_right cur){//右右左单旋 --- parent 被提上去了RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;cur-_col RED;}else{//右左右左双旋 --- cur 被提上去了//……}//旋转后保持平衡可以结束调整break;
}注意 这种情况多半是由 单纯染色 转变而来的所以不同区域的抽象图有不同的情况必须确保能符合红黑树的性质。
2.5、右左双旋 染色
双旋右左、左右此时在 右半区所以当 叔叔 不存在或者为 黑色 且节点位于 父亲 的 左边 时可以通过 右左双旋 降低高度
如果在左半区节点位于父亲的右边时则使用 左右双旋 降低高度
在高度降低后需要使用 染色 确保符合 红黑树 的性质
旋转 思想很巧妙在 旋转 染色 后可以跳出循环结束调整
右左双旋 染色 的操作如下
注意c 表示当前节点p 表示父亲节点u 表示叔叔节点g 表示祖父节点
双旋 其实就是两个不同的 单旋不过对象不同而已先 右旋转 parent再 左旋转 grandfather 就是 右左双旋
本质将 cur 的右孩子托付给 parent左孩子托付给 grandfather 后把 cur 往上提即可并保证不违背 红黑树 的性质
红黑树的检验主要是为了确保在插入或删除节点后红黑树的性质依旧得到了满足。我们可以通过以下几个方面来验证红黑树的合法性 4.红黑树的性质回顾
为了检验红黑树的合法性需要检查以下五条性质是否都被满足
每个节点不是红色就是黑色。根节点是黑色。如果一个节点是红色那么它的两个子节点必须是黑色即不能有连续的红色节点。从任一节点到其所有后代叶子节点的路径上必须包含相同数量的黑色节点。每个叶子节点的 nullptr 视为黑色。
检验步骤
我们可以通过编写检查函数递归地验证红黑树的合法性。
1. 验证根节点是否为黑色
红黑树的根节点必须是黑色的。如果根节点不是黑色就说明红黑树不合法。这是一个简单的检查。
if (_root-_col ! BLACK)
{std::cerr 根节点不是黑色违反红黑树性质二 std::endl;return false;
}2. 检查是否出现连续的红色节点
如果一个节点是红色那么它的子节点必须是黑色。因此当遍历树时可以检查每个红色节点的子节点是否都是黑色。如果出现连续的红色节点则树不合法。
bool CheckRedNodeRule(Node* node)
{if (node nullptr)return true;if (node-_col RED){// 如果当前节点是红色检查左右子节点if ((node-_left node-_left-_col RED) || (node-_right node-_right-_col RED)){std::cerr 出现连续的红色节点违反红黑树性质三 std::endl;return false;}}// 递归检查左右子树return CheckRedNodeRule(node-_left) CheckRedNodeRule(node-_right);
}3. 验证从根节点到每个叶子节点路径的黑色节点数量是否一致
每一条路径从根节点到叶子节点所包含的黑色节点数量必须一致。这个数量可以称为基准黑色节点数。
首先从根节点到最左边叶子节点的路径中统计黑色节点数量作为基准值。然后递归检查其他路径是否符合这个基准值。
// 计算左侧路径上的黑色节点数量作为基准
int GetBlackHeight(Node* node)
{int blackCount 0;while (node ! nullptr){if (node-_col BLACK)blackCount;node node-_left;}return blackCount;
}// 检查每条路径的黑色节点数是否一致
bool CheckBlackHeight(Node* node, int blackCount, int benchMark)
{if (node nullptr){// 到达叶子节点检查是否等于基准值return blackCount benchMark;}if (node-_col BLACK)blackCount;return CheckBlackHeight(node-_left, blackCount, benchMark) CheckBlackHeight(node-_right, blackCount, benchMark);
}4. 汇总检验
结合以上的检查点我们可以编写一个 IsRBTree() 函数逐步验证红黑树的合法性
// 计算左侧路径上的黑色节点数量作为基准
int GetBlackHeight(Node* node)
{int blackCount 0;while (node ! nullptr){if (node-_col BLACK)blackCount;node node-_left;}return blackCount;
}// 检查每条路径的黑色节点数是否一致
bool CheckBlackHeight(Node* node, int blackCount, int benchMark)
{if (node nullptr){// 到达叶子节点检查是否等于基准值return blackCount benchMark;}if (node-_col BLACK)blackCount;return CheckBlackHeight(node-_left, blackCount, benchMark) CheckBlackHeight(node-_right, blackCount, benchMark);
}5.调试和验证
当代码中的某些操作可能会破坏红黑树的性质时可以调用 IsRBTree() 来验证整个树的合法性输出不满足性质的详细信息。这些检查帮助确保红黑树操作在每次插入、删除或其他变动后仍符合红黑树的要求。 5. AVL和红黑树的性能比较
AVL树和红黑树是两种经典的自平衡二叉搜索树它们在不同应用场景中有各自的优势和劣势。下面从几个方面对它们的性能进行对比包括平衡机制、插入/删除性能、查询性能和实际应用场景。
1. 平衡机制对比
AVL树AVL树严格保持高度平衡每个节点的左右子树高度差称为平衡因子最多为1。为了维持这种严格的平衡AVL树在插入或删除节点时几乎每次都需要进行旋转操作以确保平衡。红黑树红黑树通过颜色标记红和黑以及特定的旋转规则来维持大致的平衡它的平衡策略相对宽松。红黑树允许路径长度差达到2倍因此在插入和删除时它会尽可能避免旋转除非触发特定条件。
2. 插入性能对比
AVL树由于AVL树保持严格的平衡性它在插入时往往需要频繁旋转以重新平衡树。插入操作的平均和最差时间复杂度都是 O(logN)O(\log N)O(logN)但旋转操作的频率较高尤其在接近完全平衡的情况下这会导致插入操作时间增加。红黑树红黑树在插入时通常只需要少量旋转且更多情况下可以通过染色来维持平衡而不进行旋转。插入操作的时间复杂度也是 O(logN)O(\log N)O(logN)但由于旋转较少因此在插入密集的应用场景中红黑树往往表现得更好。
3. 删除性能对比
AVL树AVL树删除节点后会执行严格的平衡操作频繁旋转调整确保树高度平衡因此在删除操作时会消耗更多时间。红黑树红黑树的删除操作复杂度相对较低因为其平衡策略宽松。删除时红黑树往往可以通过染色操作或少量旋转恢复平衡不会像AVL树那样频繁旋转。因此在删除操作密集的场景中红黑树性能通常优于AVL树。
4. 查询性能对比
在查询性能上二者的时间复杂度都是 O(logN)O(\log N)O(logN)但由于它们的平衡策略不同有以下几点差异
AVL树因为严格平衡AVL树的高度始终接近 logN\log NlogN这使得查找路径较短。理论上AVL树的查找性能略优于红黑树特别是在数据分布接近最差情况时AVL树会比红黑树更快。红黑树红黑树允许路径长度差达到2倍意味着它的高度可能比AVL树稍大一些。因此在某些场景下AVL树的查询可能略微快于红黑树。然而在实际应用中这种差距通常微乎其微。
5. 内存占用对比
AVL树AVL树每个节点除了存储左右子节点还要存储平衡因子。因此内存消耗会稍微多一点。红黑树红黑树每个节点只需一个颜色标记红或黑因此在内存开销上相对较小。
6. 实际应用场景对比
AVL树适用场景AVL树适合频繁查找、不频繁更新插入/删除的场景。例如适合用于静态数据库或对性能要求较高的读取密集型场景。红黑树适用场景红黑树适合需要频繁插入和删除操作的场景特别是在数据动态变化的情况下。红黑树的宽松平衡机制在插入、删除密集的情况下能够减少旋转从而提升性能。这使得红黑树广泛应用于系统中的许多集合操作例如C STL的 map、set 以及Linux内核中的调度器等。
7. 性能测试示例
假设插入和删除大量数据的性能测试结果通常会显示
插入/删除红黑树的插入和删除操作时间较短尤其在大量数据的随机插入/删除测试中红黑树的性能比AVL树好。查询查询操作性能上两者差距不大AVL树可能在极端情况下稍快但在实际应用中效果差别不大。
总结
属性AVL树红黑树平衡机制严格平衡更多旋转宽松平衡染色少量旋转插入性能较多旋转插入稍慢较少旋转插入较快删除性能较多旋转删除稍慢较少旋转删除较快查询性能高度接近完全平衡稍快高度略大于AVL性能接近内存开销较高存储平衡因子较低存储颜色标记适用场景查找频繁、更新较少的场景插入/删除频繁的动态场景
总体而言红黑树在插入和删除密集的动态应用场景中表现更好而AVL树在静态或查找频繁的场景中性能稍优。
完整代码
#pragma once
#includeiostream
#includemap
#includeassert.h
#includevector
using namespace std;enum Color
{RED,BREAK
};templateclass K, class V
struct RBTreeNode
{struct RBTreeNodeK, V* _left;struct RBTreeNodeK, V* _right;struct RBTreeNodeK, V* _parent;pairK, V _kv;int _color;RBTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(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-_color BREAK;return true;}else{Node* cur _root;Node* parent _root;while (cur)//比较Frist{if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false;//必须退出}}cur new Node(kv);if (cur-_kv.first parent-_kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}while (parent parent-_color RED){Node* grandfather parent-_parent;if (parent grandfather-_right)//父亲为右{Node* Uncle grandfather-_left;if (Uncle Uncle-_color RED){parent-_color Uncle-_color BREAK;grandfather-_color RED;cur grandfather;parent cur-_parent;}else{if (cur parent-_right){RotateL(grandfather);grandfather-_color RED;parent-_color BREAK;}else//交叉{RotateRL(grandfather);grandfather-_color RED;cur-_color BREAK;}}}else//父亲在左{Node* Uncle grandfather-_right;if (Uncle Uncle -_color RED){parent-_color Uncle-_color BREAK;grandfather-_color RED;cur grandfather;parent cur-_parent;}else//叔叔不存在或者等于黑色我直线或者弯曲{if (cur cur-_left){RotateR(grandfather);parent-_color BREAK;grandfather-_color RED;}else{RotateLR(grandfather);cur-_color BREAK;grandfather-_color RED;}}}_root-_color BREAK;}return true;}}void RotateL(Node * parent)//穿的是问题节点{Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;cur-_left parent;if (curleft){curleft-_parent parent;}Node* pphead parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (pphead-_left parent){pphead-_left cur;}else if (pphead-_right parent){pphead-_right cur;}cur-_parent pphead;} }void RotateR(Node * parent){Node* cur parent-_left;Node* curright cur-_right;cur-_right parent;parent-_left curright;if (curright){curright-_parent parent;}Node* phead parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (phead-_left parent){phead-_left cur;}else{phead-_right cur;}cur-_parent phead;}}void RotateRL(Node * parent)//传谁谁父亲下去{Node* cur parent-_right;Node* curleft cur-_left;RotateR(parent-_right);RotateL(parent);}void RotateLR(Node * parent){Node* cur parent-_left;Node* curright cur-_right;RotateL(cur);RotateR(parent);}bool IsBalanceTree(){return IsBalanceTree(_root);}bool IsBalanceTree(Node* root){if (root nullptr){return true;}if (root-_color ! BREAK){return false;}int benchmark 0;Node* cur root;while (cur){if (cur-_color BREAK){benchmark;}cur cur-_left;}return CheckColour(root, 0, benchmark);}bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark){return false;}return true;}if (root-_color BREAK){blacknum;}if (root-_color RED root-_parent root-_parent-_color RED){cout root-_kv.first 出现连续红节点 endl;}return CheckColour(root-_left, blacknum, benchmark);}private:Node* _root nullptr;
};
