C++ 红黑树

server/2024/11/24 22:22:55/

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

1. 每个结点不是红色就是黑色 
2. 根节点是黑色的  
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的  
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点  
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

那么红黑树是如何保证根到叶子节点的最长路径不会超过最短路径的两倍？

那么我们假设红黑树中根到叶子节点包含的黑色节点为N，那么最短路径就是全部为黑色节点，即长度为N

那么最长路径就是一黑一红，当红色和黑色节点的数目相同就是2N,因此，根到叶子节点的最长路径不会超过最短路径的两倍

红黑树节点的定义

我们这里用K V的模型，为方便后续的旋转操作

// 枚举定义节点颜色
enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;// 存储键值对pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};

这里我们给插入的节点定义为红色，是为了不违反规则4，规则4相较于规则3无异于更为严格，应为我们如果插入黑色节点一定会破坏规则4，如果插入红色节点只是可能破坏规则3，规则3可以理解为不能有连续的红色节点，因为父节点可能为黑色

总的来说就是：

· 插入黑色一定破坏规则4，必须调整红黑树

· 插入红色可能破坏规则3，可能调整红黑树

红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

情况一：g为黑，p为红，u存在且为红

为避免出现连续的红色节点，我们可将父亲节点变为黑，同时将祖父变为红，叔叔变为黑保证每条路径的黑色节点相同

但是祖父可能是根节点可能是某个树的子树，所以保险起见再把祖父变为黑

注意：cur不管是parent左边还是右边无所谓

抽象图：

情况二：p为红，g为黑，叔叔存在且为黑

这种情况一定是在情况一继续往上调整的过程中出现的，即这种情况下的cur结点一定不是新插入的结点，而是上一次情况一调整过程中的祖父结点，如下图：

我们将路径中祖父结点之上黑色结点的数目设为x xx，将叔叔结点之下黑色结点的数目设为y yy，则在插入结点前，图示两条路径黑色结点的数目分别为x + 1 x+1x+1 和 x + 2 + y x+2+yx+2+y，很明显x + 2 + y x+2+yx+2+y 是一定大于 x + 1 x+1x+1的，因此在插入结点前就不满足红黑树的要求了，所以说叔叔结点存在且为黑这种情况，一定是由情况一往上调整过程中才会出现的一种情况。

出现叔叔存在且为黑时，单纯使用变色已经无法处理了，这时我们需要进行旋转处理。若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。

当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。

若祖孙三代的关系是折现（cur、parent、grandfather这三个结点为一条折现），则我们需要先进行双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。

当折现关系为，parent是grandfather的右孩子，cur是parent的左孩子时，就需要先进行右左双旋操作，再进行颜色调整。

情况三：p为红，g为黑，叔叔不存在

实际上情况二与情况三是一样的，如图：

调整情况完全相同

代码如下：

bool Insert(const pair<K, 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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}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;// parent的颜色是黑色也结束while (parent && parent->_col == RED){// 关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 叔叔存在且为红,变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 往上更新cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或存在且为黑{if (cur == parent->_left){//        g//     p     u//   cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 叔叔存在且为红,变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}
红黑树的验证

红黑树是特殊的二叉树，因此，我们可以用中序遍历来判断是否满足二叉树的性质

void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

然后验证是否满足红黑树的性质

bool IsBalance(){if (_root->_col == RED){return false;}int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refnum;}cur = cur->_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int blacknum, const int refnum){if (root == nullptr){if (blacknum != refnum){cout <<  "存在节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续红色的节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, refnum)&& Check(root->_right, blacknum, refnum);}
红黑树的查找：

红黑树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：

若树为空树，则查找失败，返回nullptr。
若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值，则查找成功，返回对应结点。

Node* Find(const K& kv)
{Node* cur = _root;while (cur){if (cur->_first > kv){cur = cur->_left;}else if (cur->_first < kv){cur = cur->_right;}else{return cur;}}return nullptr;
}
红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

附上完整代码：

enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, 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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}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;// parent的颜色是黑色也结束while (parent && parent->_col == RED){// 关键看叔叔Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 叔叔存在且为红,变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 往上更新cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或存在且为黑{if (cur == parent->_left){//        g//     p     u//   cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 叔叔存在且为红,变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}Node* Find(const K& kv)
{Node* cur = _root;while (cur){if (cur->_first > kv){cur = cur->_left;}else if (cur->_first < kv){cur = cur->_right;}else{return cur;}}return nullptr;
}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root->_col == RED){return false;}int refnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refnum;}cur = cur->_left;}return Check(_root, 0, refnum);}private:bool Check(Node* root, int blacknum, const int refnum){if (root == nullptr){if (blacknum != refnum){cout <<  "存在节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续红色的节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, refnum)&& Check(root->_right, blacknum, refnum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};


http://www.ppmy.cn/server/144648.html

相关文章

【国产MCU系列】-GD32F470-通用同步异步收发器（USART）

【国产MCU系列】-GD32F470-通用同步异步收发器（USART）

通用同步异步收发器（USART） 文章目录 通用同步异步收发器（USART）1、USART与UART介绍2、GD32F4的USART2.1 GD32F4的USART介绍与特性2.2 GD32F4的USART寄存器列表3、USART数据发送与接收与配置3.1 数据帧格式与配置3.2 波特率发生与配置3.3 UART发送器配置与步骤3.4 UART接收…
阅读更多...
Linux 后台运行的方式启动一个 Java 应用程序

Linux 后台运行的方式启动一个 Java 应用程序

nohup java -jar -Dapp.iddefect-web -Dspring.profiles.activetest -Denvtest /home/webedit/source/server/mall_server/webshop/target/webshop-0.0.1-SNAPSHOT.jar >> /home/webedit/deploy/webshop.log 2>&1 &① nohup 表示忽略挂断信号&#xff08;SIG…
阅读更多...
Maven高级篇

Maven高级篇

本篇主要讲解做项目过程中学习到一些关于maven使用的知识&#xff0c;主要包括分模块设计、继承&#xff0c;继承中的版本锁定&#xff0c;maven的聚合以及maven私服。 目录 一、分模块设计 二、继承 三、继承中的版本锁定 四、maven的聚合 五、maven私服 一、分模块设计…
阅读更多...
JavaWeb-表单-07

JavaWeb-表单-07

表单标签 介绍 code: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>HTML-表单</title> &…
阅读更多...
如何能让安全责任更清晰——构建清晰安全责任体系策略与实践

如何能让安全责任更清晰——构建清晰安全责任体系策略与实践

安全已成为各行各业不可忽视的重要议题。然而&#xff0c;要确保组织的安全运行&#xff0c;仅仅有安全意识是不够的&#xff0c;还需要有一套清晰明确的安全责任体系来支撑。这套体系能够明确每个人的安全职责&#xff0c;促进安全管理工作的有序进行&#xff0c;降低事故发生…
阅读更多...
Paint 学习笔记

Paint 学习笔记

目录 ippaint 外扩对象 LCM_inpaint_Outpaint_Comfy&#xff1a; 不支持文字引导 ippaint https://github.com/Sanster/IOPaint 外扩对象 https://www.iopaint.com/models/diffusion/powerpaint_v2 GitHub - open-mmlab/PowerPaint: [ECCV 2024] PowerPaint, a versatile …
阅读更多...
MyBatis-数据库连接池、属性文件config.properties、类名简化、MyBatis的整体架构

MyBatis-数据库连接池、属性文件config.properties、类名简化、MyBatis的整体架构

一、数据库连接池 1、概述 存储实现创建好的连接对象的容器 2、优点 避免了频繁创建和销毁连接对象 3、使用 在使用到连接对象时可在数据库连接池中直接获取 4、实现 不需要我们去实现,框架和一些第三方有现成的组件&#xff08;C3P0、ADCP、德鲁伊(阿里巴巴)&#xff…
阅读更多...
Leetcode 每日一题 11. 盛最多水的容器

Leetcode 每日一题 11. 盛最多水的容器

目录 引言 问题背景 输入输出规范 示例解析 示例 1 示例 2 算法策略 Java代码实现 复杂度分析 结语 引言 在算法的世界里&#xff0c;有些问题虽然简单&#xff0c;但却是锻炼算法思维的绝佳练习。今天&#xff0c;我们将深入探讨一个在面试中经常出现的问题——“接…
阅读更多...
最新文章

Copyright @ 2022~2023