C++进阶——红黑树

news/2024/10/24 9:11:47/

目录

一、概念

二、特征

三、模拟实现

1.大致框架

2.插入分析

3.插入代码

四、测试

一、概念

红黑树是一颗近似平衡的二叉搜索树，最长路径的长度不会超过最短路径的两倍，主要是通过控制结点的“颜色”来实现的，第一次接触红黑树可能会觉得很抽象，不过明白了其中原理便会觉得它设计得如此巧妙。

二、特征

红黑树的最长路径不能超过最短路径的二倍。

————这是红黑树能成为近似平衡的二叉搜索树的唯一需要。

由于这个特征，会导致其结点个数和最短路径的高度满足：

计算下来， h和2h（理论上的最长路径）也是logN级别的，那么它的查找效率能达到O(logN)。

所以为了实现最长路径不能超过最短路径的二倍这个特征，红黑树必须满足以下几点规则：

1. 每个节点不是红色就是黑色

2. 根节点必须是黑色

3. 红色结点的孩子只能是黑色结点

4.每条路径的黑色结点个数相同

我们来捋一下这些规则与红黑树特征的关系：

规则3限制了红色结点的孩子必然是黑色结点，而黑色结点的孩子或父亲不一定是红色结点，而每条路径的黑色结点个数又相同（规则4），所以最长路径（理论上，实际上不一定会存在）会是（规则2，根节点必须是黑色）黑色红色黑色红色……黑色红色，最短路径是黑色黑色黑色……黑色，最长的路径长度就会是最短路径的二倍。

也就是说，规则1规定了红黑树的框架（红色和黑色结点），规则3和规则4大大限制了最短路径和最长路径之间的倍数差，规则2为这个规则3和规则4的限制添加了最后的保障。

三、模拟实现

1.大致框架

和之前AVL树一样，我们实现的是key/value版本的红黑树，主要实现它的插入操作即可。

红黑树本质上就是结点的封装，那么结点里应该有什么？

红黑树不再需要靠平衡因子来保持平衡，所以只需要_col（标记颜色），_kv（key/value），_parent，_left，_right就ok了（父结点在之后的调整中会经常用到）

#pragma once
#include <iostream>
using namespace std;// 枚举值代表颜色（当然用bool值也ok）
enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED) // 因为插入默认插入RED（除了根节点）{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:private:Node* _root = nullptr;
};

2.插入分析

首先，插入的结点应该是什么颜色的结点？

我们挨个分析：

如果插入的结点是黑色结点，那么就会出现这种情况：

如果插入的结点是红色结点，那么：

插入为黑色结点的孩子：

 

插入为红色结点的孩子：

uncle存在且是红色的情况：

上面这种情况继续向上调整的分析：继续向上调整时，cur变为grandfather（红色），其余都再更新

uncle存在且为黑色的情况：

uncle不存在的情况：

综合以上情况，我们分析出插入的结点必须为红色结点，

红色结点又要考虑的情况：

1.结点的插入位置（左孩子or右孩子）、

2.uncle的存在与否/颜色 

uncle的情况：

1.当uncle存在且为红色时，只需改变颜色就能完成红黑树的调整。

（需要注意的是这个调整会一直网上调整，有可能会调整到根节点，在写代码的时候要注意这个细节）

2.当uncle为其它情况时，就需要借助旋转+变色来帮我们完成调整。

当然，以上情况都是uncle在parent右边的情况，还有uncle在parent的右边的情况，这些情况就和前面完全镜像了，就不再拿出来一一分析

3.插入代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}// 先查找Node* parent = nullptr, * cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = parent->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = parent->_right;}else{return false;}}// 注意插入结点的构造使其默认就是红色cur = new Node(kv);if (kv.first < parent->_kv.first) parent->_left = cur;else parent->_right = cur;cur->_parent = parent;// 插入完毕，接下来就是旋转/变色// 1. 插入位置为黑色结点的孩子，管都不用管// if (parent->_col == BLACK)// 2. 插入位置为红色结点的孩子// 为啥不是if，就是因为可能还需要继续向上调整while (parent && parent->_col == RED){// 为啥不可能是空？因为parent是红色Node* grandfather = parent->_parent;// 镜像情况1，parent在左//      g// p        uif (parent == grandfather->_left){Node* uncle = grandfather->_right;// uncle存在且为红色if (uncle && uncle->_col == RED){// 只需要变色parent->_col = BLACK;grandfather->_col = RED;uncle->_col = BLACK;// 可能仍需要继续向上调整cur = grandfather;parent = cur->_parent;}else{// uncle是黑色或不存在（这个不重要，旋转不影响）// 变色+旋转if (cur == parent->_left){//        g//    p      u// c// 单旋+变色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//        g//    p      u//        cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 如果是通过旋转调整的，就直接break// 因为留在调整局部最上面的是黑色结点，不需要继续向上调整break;}}// 镜像情况2 parent在右//      g// u        pelse{Node* uncle = grandfather->_left;// uncle存在且为红色if (uncle && uncle->_col == RED){// 只需要变色parent->_col = BLACK;grandfather->_col = RED;uncle->_col = BLACK;// 可能仍需要继续向上调整cur = grandfather;parent = cur->_parent;}else{// uncle是黑色或不存在（这个不重要，旋转不影响）// 变色+旋转if (cur == parent->_right){//        g//    u      p//                c// 单旋+变色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//        g//    u      p//        cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 如果是通过旋转调整的，就直接break// 因为留在调整局部最上面的是黑色结点，不需要继续向上调整break;}}}// 最后不管根节点是不是变成红色了，都改成黑色// 这样就不用讨论cur是根节点（红色）但是跳出循环的那种情况了_root->_col = BLACK;return true;
}// 右单旋  rotate 旋转 right 右
void RotateR(Node* parent)
{// 连接Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;// 更新_parentsubL->_parent = parent->_parent;parent->_parent = subL;if (subLR)	subLR->_parent = parent;// 根结点的情况if (parent == _root)	_root = subL;// 非根结点	 更新“看不见的”parentelse if (parent == subL->_parent->_left)	subL->_parent->_left = subL;else subL->_parent->_right = subL;
}// 左单旋
void RotateL(Node* parent)
{// 连接Node* subR = parent->_right;Node* subRL = subR->_left;subR->_left = parent;parent->_right = subRL;// 更新_parentsubR->_parent = parent->_parent;parent->_parent = subR;if (subRL)	subRL->_parent = parent;// 根结点的情况if (parent == _root)	_root = subR;// 非根结点	 更新“看不见的”parentelse if (parent == subR->_parent->_left)	subR->_parent->_left = subR;else subR->_parent->_right = subR;
}

四、测试

我们可以复用AVL树的测试代码，不过需要有新增的判断是否为红黑树的测试。

判断是否为红黑树，只需要判断是否符合红黑树的规则即可。

1. 每个节点不是红色就是黑色

2. 根节点必须是黑色

3. 红色结点的孩子只能是黑色结点

4.每条路径的黑色结点个数相同

我们着重思考3、4怎么测试

3：如果遍历找出每个红色结点，再去看该红色结点的左右孩子结点（而且不一定存在）是比较繁琐的，但是如果我们反其道而行之，既然红色结点的孩子只能是黑色结点，那么红色结点的父亲就必然不能是红色结点，一旦红色结点的父亲是红色结点，那么就不符合红黑树的规则

4：我们可以先随便找一条路径，算出其黑色结点的个数，然后再使用递归比较一下其它路径的黑色结点个数是否与该路径黑色结点个数相等，如果不相等，就不符合红黑树的规则

本博客所有实现代码（包括测试）：

// RBTree.h
#pragma once
#include <iostream>
using namespace std;// 枚举值代表颜色（当然用bool值也ok）
enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED) // 因为插入默认插入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, *cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = parent->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = parent->_right;}else{return false;}}// 注意插入结点的构造使其默认就是红色cur = new Node(kv);if (kv.first < parent->_kv.first) parent->_left = cur;else parent->_right = cur;cur->_parent = parent;// 插入完毕，接下来就是旋转/变色// 1. 插入位置为黑色结点的孩子，管都不用管// if (parent->_col == BLACK)// 2. 插入位置为红色结点的孩子// 为啥不是if，就是因为可能还需要继续向上调整while (parent && parent->_col == RED){// 为啥不可能是空？因为parent是红色Node* grandfather = parent->_parent;// 镜像情况1，parent在左//      g// p        uif (parent == grandfather->_left){Node* uncle = grandfather->_right;// uncle存在且为红色if (uncle && uncle->_col == RED){// 只需要变色parent->_col = BLACK;grandfather->_col = RED;uncle->_col = BLACK;// 可能仍需要继续向上调整cur = grandfather;parent = cur->_parent;}else{// uncle是黑色或不存在（这个不重要，旋转不影响）// 变色+旋转if (cur == parent->_left){//        g//    p      u// c// 单旋+变色RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//        g//    p      u//        cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 如果是通过旋转调整的，就直接break// 因为留在调整局部最上面的是黑色结点，不需要继续向上调整break;}}// 镜像情况2 parent在右//      g// u        pelse{Node* uncle = grandfather->_left;// uncle存在且为红色if (uncle && uncle->_col == RED){// 只需要变色parent->_col = BLACK;grandfather->_col = RED;uncle->_col = BLACK;// 可能仍需要继续向上调整cur = grandfather;parent = cur->_parent;}else{// uncle是黑色或不存在（这个不重要，旋转不影响）// 变色+旋转if (cur == parent->_right){//        g//    u      p//                c// 单旋+变色RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//        g//    u      p//        cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 如果是通过旋转调整的，就直接break// 因为留在调整局部最上面的是黑色结点，不需要继续向上调整break;}}}// 最后不管根节点是不是变成红色了，都改成黑色// 这样就不用讨论cur是根节点（红色）但是跳出循环的那种情况了_root->_col = BLACK;return true;}// 右单旋  rotate 旋转 right 右void RotateR(Node* parent){// 连接Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;// 更新_parentsubL->_parent = parent->_parent;parent->_parent = subL;if (subLR)	subLR->_parent = parent;// 根结点的情况if (parent == _root)	_root = subL;// 非根结点	 更新“看不见的”parentelse if (parent == subL->_parent->_left)	subL->_parent->_left = subL;else subL->_parent->_right = subL;}// 左单旋void RotateL(Node* parent){// 连接Node* subR = parent->_right;Node* subRL = subR->_left;subR->_left = parent;parent->_right = subRL;// 更新_parentsubR->_parent = parent->_parent;parent->_parent = subR;if (subRL)	subRL->_parent = parent;// 根结点的情况if (parent == _root)	_root = subR;// 非根结点	 更新“看不见的”parentelse if (parent == subR->_parent->_left)	subR->_parent->_left = subR;else subR->_parent->_right = subR;}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool IsBalance(){if (_root == nullptr)return true;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 (refNum != blackNum){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);}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}
private:Node* _root = nullptr;
};

// Test.cpp
#include<iostream>
#include<vector>
using namespace std;#include"RBTree.h"void TestRBTree1()
{RBTree<int, int> t;// 常规的测试用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalance() << endl;
}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestRBTree2()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalance() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值//for (auto e : v)//{//	t.Find(e);//}// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}int main()
{TestRBTree2();return 0;
}

okkkkkkkkk~

完结撒花啦~


http://www.ppmy.cn/news/1541560.html

相关文章

MySQL【知识改变命运】复习前1~11

MySQL【知识改变命运】复习前1~11

复习 1&#xff1a;客户端和数据库操作2&#xff1a;表操作3: CRUD 增删改查4:数据库约束5:表的设计6:聚合函数7:GROUP BY分组查询和HAVING子句8:联合查询(表连接查询) 1&#xff1a;客户端和数据库操作 1. 登录 mysql -uroot -p > 2. 查看当前数据库的版本 select version(…
阅读更多...
RabbitMQ概述

RabbitMQ概述

Rabbit是一个公司名.MQ也就是消息队列的意思&#xff0c;RabbitMQ是Rabbit企业下一个消息队列产品。 RabbitMQ是一个实现了AMQP的消息队列服务&#xff0c;是当前主流的消息中间件。 什么是MQ MQ&#xff08;message queue&#xff09;&#xff0c;本身是个队列&#xff0c;…
阅读更多...
Ansible自动化运维项目实战指南

Ansible自动化运维项目实战指南

Ansible自动化运维项目实战指南 在当今快速发展的IT环境中&#xff0c;运维工作的复杂性和规模性日益增加&#xff0c;传统的手动运维方式已难以满足高效、可靠、可重复性的需求。Ansible作为一款开源的自动化运维工具&#xff0c;凭借其简单易用、无需代理、基于SSH的架构特性…
阅读更多...
idea 开发插件

idea 开发插件

idea 开发插件 一、代码生成插件MybatisX&#xff08;免费&#xff09;MyBatisCodeHelperPro &#xff08;收费&#xff09; 二、自动生成单元测试插件JUnitGenerator V2.0&#xff08;免费&#xff09;Squaretest插件&#xff08;收费&#xff09;TestMe插件&#xff08;免费&…
阅读更多...
强化学习和运筹决策优化

强化学习和运筹决策优化

强化学习 强化学习&#xff08;Reinforcement Learning, RL&#xff09;是机器学习的一个分支&#xff0c;特别关注智能体&#xff08;Agent&#xff09;在与环境交互的过程中通过试错学习来改进决策策略。在强化学习中&#xff0c;智能体通过观察环境状态并采取行动来获得奖励…
阅读更多...
[0154].第5节：IDEA中创建Java Web工程

[0154].第5节：IDEA中创建Java Web工程

我的后端学习大纲 IDEA大纲 1.1.IDEA中配置Tomcat&#xff1a; 1.找打setting: 2.配置Tomcat Server的位置&#xff1a; 3.这里配置Tomcat的名称以及配置应用服务器的位置。根据自己Tomcat的安装位置决定 4.配置好后&#xff0c;如下图所示 1.2.创建Web工程&#xff1a; 1.建…
阅读更多...
centos配置ssh

centos配置ssh

在CentOS上配置SSH服务主要步骤&#xff1a; 安装OpenSSH服务器&#xff1a; 首先&#xff0c;你需要确保OpenSSH服务器软件包已经安装在你的系统上。你可以使用以下命令来安装它&#xff1a; sudo yum update sudo yum install openssh-server 启动SSH服务&#xff1a; 安装完…
阅读更多...
基于Django+Python的宾馆管理系统设计与实现

基于Django+Python的宾馆管理系统设计与实现

项目运行 需要先安装Python的相关依赖&#xff1a;pymysql&#xff0c;Django3.2.8&#xff0c;pillow 使用pip install 安装 第一步&#xff1a;创建数据库 第二步&#xff1a;执行SQL语句&#xff0c;.sql文件&#xff0c;运行该文件中的SQL语句 第三步&#xff1a;修改源…
阅读更多...
最新文章

Copyright @ 2022~2023