红黑树——原理刨析

        众所周知，红黑树是从AVLTree树中衍变而来的，所以在学红黑树之前还是要好好的理解一下AVLTree树的原理，为理解红黑树减轻理解负担，好了进入正题。

红黑树原理：

        由名可知，红黑树——肯定是与颜色有关的一个树，又因为是从AVLTree树中衍化过来的，所以也是搜索树（不是平衡二叉树，后面讲解定义时会详细解释），通过对不同情况的处理，去调整红黑树节点的颜色或者红黑树的高度去使其满足，红黑树的定义规则。

红黑树的定义：

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

如上图，就是红黑树。

红黑树的性质：

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

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

答：上述红黑树的性质第4条 说明每条路上面的黑色节点数量都是相等的，所以说该节点的左右子树可以有一棵子树全为黑色节点 另一个红黑节点交替（红节点数量与黑节点数量相等），这就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

红黑树中重要的函数讲解：

        和AVLTree一样，插入函数是难点，但是掌握AVLTree之后，这里的插入就不怎么难了，AVLTree中提到左旋，右旋，这里不做讲解，如有疑惑，参考上篇文章，有流程图。

        在我看来红黑树与AVLTree不同点就是规则不同，红黑树是靠颜色去调整高度差，而AVLTree是通过平衡因子去调节的。

情况一：整棵树或者子树为上上图，就只能进行颜色更新 将uncle更新为黑色 父亲更新为黑色 祖父更新为红色 再继续向上以同样的方式更新 直到更新到根节点或者进行了一次旋转调整 （旋转调整会将树的高度改变并将颜色确定为最终的颜色）就不再向上更新

情况二：uncle存在且为黑或者不存在

1，先进行情况一的颜色更新，出现了旋转的情况，再进行旋转 最后进行旋转的颜色更新

               

        2，刚开始整棵树就为要旋转的情况或者为整棵树的子树，如上图

单选和双旋在AVLTree中已经讲解过了，这里最重要的就是如何进行颜色更新，而不是旋转。

        

红黑树完整代码：

#pragma once
#include<iostream>
using namespace std;enum color
{BLACK,RED
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;pair<K, V> _kv;color _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;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->_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 < cur->_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;if (uncle && uncle->_col == RED){grandfater->_col = RED;parent->_col = uncle->_col = BLACK;cur = grandfater;parent = cur->_parent;}else{if (parent->_left == cur){//    g//  p   u//cRotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{//    g//  p   u//    cRotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else{Node* uncle = grandfater->_left;if (uncle && uncle->_col == RED){grandfater->_col = RED;parent->_col = uncle->_col = BLACK;cur = grandfater;parent = cur->_parent;}else{if (parent->_right == cur){//    g//  u   p//        cRotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{//    g//  u   p//     cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;}void Inorder(){_Inorder(_root);}bool IsBalance(){if (_root == nullptr){return false;}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){blackNum = benchmark;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 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 (ppNode == nullptr){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;subL->_parent = ppNode;}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;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}
};
void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27 };  // 测试双旋平衡因子调节//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t1;for (auto e : a){t1.insert(make_pair(e, e));}t1.Inorder();cout << "IsBalance:" << t1.IsBalance() << endl;
}void TestRBTree2()
{size_t N = 1000;srand(time(0));RBTree<int, int> t1;for (size_t i = 0; i < N; ++i){int x = rand();cout << "Insert:" << x << ":" << i << endl;t1.insert(make_pair(x, i));}cout << "IsBalance:" << t1.IsBalance() << endl;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/182061.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

操作系统——文件在外存中的分配方式（王道视频p61 P62）

操作系统——文件在外存中的分配方式（王道视频p61 P62）

1.总体概述&#xff1a; 连续分配 —— 链接分配 —— 索引分配 &#xff08;1&#xff09;对于顺序分配&#xff0c;这种方式 基本不会使用了&#xff0c; 因为 它存在一个 核心的问题就是 没法更新&#xff1b;不过&#xff0c;还是要注意它的 “文件目录”——其中存放了…
阅读更多...
强化学习中策略的迭代

强化学习中策略的迭代

一、策略迭代 一旦使用vπ改善了策略π&#xff0c;产生了更好的策略π0&#xff0c;我们就可以计算vπ0并再次对其进行改进&#xff0c;产生更好的π00。因此&#xff0c;我们可以获得一系列单调改善的策略和值函数&#xff1a; 其中E−→表示策略评估&#xff0c;I−→表示策…
阅读更多...
企业通配符SSL证书的特点

企业通配符SSL证书的特点

企业通配符SSL证书是一种数字证书&#xff0c;其可以用于保护多个企业网站&#xff0c;对网站传输信息进行加密服务。这种证书通常适用于拥有多个子域名或二级域名的企事业单位。今天就随SSL盾小编了解企业通配符SSL证书的相关信息。 1. 保护所有域名和子域名&#xff1a;企业通…
阅读更多...
linux 启动引导找不到内核修复

linux 启动引导找不到内核修复

问题现象 选中内核按e 看到引导内核信息 挂载ISO映像进入救援模式&#xff0c;查看boot目录 与 引导文件内容不一致 再次重启引导系统&#xff0c;按e 修改内核引导项与boot目录一致&#xff0c; crtl - x 继续执行 登录系统 mount /dev/sdm1 /mnt 挂载vfat 引导目录 纠…
阅读更多...
CorelDRAW2024好不好用？怎么下载

CorelDRAW2024好不好用？怎么下载

cdr是CorelDRAW的简称&#xff0c;一款专注排版和矢量图形编辑的平面设计软件。这款软件的设计界面精微细致、简洁易懂。功能尤其强大&#xff0c;图标设计&#xff0c;印刷排版&#xff0c;服装设计等都可以胜任。还有多种模板使得设计相当的轻松&#xff0c;今天简单介绍一下…
阅读更多...
C语言查看各数据类型所占大小

C语言查看各数据类型所占大小

编译器&#xff1a;VC2010 #include<stdio.h> int main() {printf("%d\n",sizeof(char));printf("%d\n",sizeof(short));printf("%d\n",sizeof(int));printf("%d\n",sizeof(long));printf("%d\n",sizeof(long long))…
阅读更多...
【Python语言】集合的使用方法总结

【Python语言】集合的使用方法总结

目录 1、集合基本知识&#xff1a; 2、定义 2.1 定义集合变量 2.2 定义空集合 3、集合的常用操作 3.1 定义集合 3.2 添加新元素 3.3 移除元素 3.4 从集合中随机取出元素 3.5 清空集合 3.6 取两个集合的差集 3.7 消除两个集合的差集 3.8 两个集合合并 3.9 统计集合…
阅读更多...
软件外包开发质量控制方法

软件外包开发质量控制方法

在软件外包开发项目中&#xff0c;质量控制是确保交付的软件符合预期质量标准的关键步骤。以下是一些常用的软件外包开发质量控制方法&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 需求明确&#x…
阅读更多...
【第28例】IPD体系进阶 | 需求管理：需求实现过程

【第28例】IPD体系进阶 | 需求管理：需求实现过程

目录 简介 内容详解 CSDN学院相关推荐 作者简介 简介 继续 IPD 体系中的需求管理相关的专题。 先来看看整个需求管理涉及的过程内容： 需求管理流程主要包含五个阶段： 需求收集； 需求分析； 需求分发/分配；
阅读更多...
构建数字孪生的四大挑战

构建数字孪生的四大挑战

如果不能解决由数字孪生带来的开发难题&#xff0c;那么企业就无法享受这种技术便利。 数字孪生已经成为企业当前面对的一大机遇&#xff0c;其核心在于利用虚拟副本中的分析数据对未来业务事件开展预测。这不仅能够大大降低决策难度&#xff0c;同时也有助于提升决策效果。 然…
阅读更多...
“利用义乌购API揭秘跨境贸易商机：一键获取海量优质商品列表！“

“利用义乌购API揭秘跨境贸易商机：一键获取海量优质商品列表！“

义乌购API可以根据关键词取商品列表。通过调用义乌购API的item_search接口&#xff0c;传入关键词参数&#xff0c;可以获取到符合该关键词的商品列表。 以下是使用义乌购API根据关键词取商品列表的步骤&#xff1a; 注册义乌购开发者账号并获取授权码和密钥。在代码中导入义…
阅读更多...
redis教程 二 redis客户端Jedis使用

redis教程 二 redis客户端Jedis使用

文章目录 Redis的Java客户端-JedisJedis快速入门创建工程&#xff1a;引入依赖&#xff1a;建立连接测试&#xff1a;释放资源Jedis连接池创建Jedis的连接池改造原始代码 Redis的Java客户端-SpringDataRedis快速入门导入pom坐标配置文件测试代码 数据序列化器StringRedisTempla…
阅读更多...
【CIO人物展】黄淮学院副CIO周鹏：构建数智化平台赋能学校高质量发展

【CIO人物展】黄淮学院副CIO周鹏：构建数智化平台赋能学校高质量发展

周鹏 本文由黄淮学院副CIO周鹏投递并参与《2023中国数智化转型升级优秀CIO》榜单/奖项评选。丨推荐企业—锐捷网络 大数据产业创新服务媒体 ——聚焦数据 改变商业 黄淮学院是2004年经教育部批准成立的一所省属全日制普通本科高校。学校位于素有“豫州之腹地、天下之最中”之美…
阅读更多...
【Python】批量下载素材酷视频资源

【Python】批量下载素材酷视频资源

【需求】 做视频精彩需要用到梗图视频等，但是素材酷上面的视频没有搜索功能，每次用起来还要去下载也很麻烦，下载只能一个一个下载也很麻烦，下要搞一个能够批量下载的功能，然后把下载的资源全部放进万兴喵影编辑器的云空间，这样就可以做到随做随查随用了。 【效果】 目…
阅读更多...
springboot 连接西门子plc，读取对应的值，并修改到数据库

springboot 连接西门子plc，读取对应的值，并修改到数据库

springboot 连接西门子plc&#xff0c;读取对应的值&#xff0c;并修改到数据库 需求&#xff1a;服务器连接plc&#xff0c;读取数据&#xff0c;之后写入到数据库&#xff0c;但是要求速度很快&#xff0c;而且plc中命令对应的值是不断变化的&#xff0c;这个变化&#xff0c…
阅读更多...
深度学习框架TensorFlow.NET环境搭建1（C#）

深度学习框架TensorFlow.NET环境搭建1（C#）

测试环境 visual studio 2017 window10 64位 测试步骤如下&#xff1a; 1 新建.net framework控制台项目&#xff0c;工程名称为TensorFlowNetDemo&#xff0c;.net framework的版本选4.7.2&#xff0c;如下图&#xff1a; 2 分别安装TensorFlow.NET包(先装)和SciSharp.…
阅读更多...
QT+SQLite数据库配置和使用

QT+SQLite数据库配置和使用

一、简介 1.1 SQLite&#xff08;sql&#xff09;是一款开源轻量级的数据库软件&#xff0c;不需要server&#xff0c;可以集成在其他软件中&#xff0c;非常适合嵌入式系统。Qt5以上版本可以直接使用SQLite&#xff08;Qt自带驱动&#xff09;。 二、下载和配置 2.1 SQLite下载…
阅读更多...
Docker Compose安装milvus向量数据库单机版-milvus基本操作

Docker Compose安装milvus向量数据库单机版-milvus基本操作

目录 安装Ubuntu 22.04 LTS在power shell启动milvus容器安装docker desktop下载yaml文件启动milvus容器Milvus管理软件Attu python连接milvus配置下载wget示例导入必要的模块和类与Milvus数据库建立连接创建名为"hello_milvus"的Milvus数据表插入数据创建索引基于向量…
阅读更多...
7.spark sql编程

7.spark sql编程

概述 spark 版本为 3.2.4&#xff0c;注意 RDD 转 DataFrame 的代码出现的问题及解决方案 本文目标如下&#xff1a; RDD ,Datasets,DataFrames 之间的区别入门 SparkSession创建 DataFramesDataFrame 操作编程方式运行 sql 查询创建 DatasetsDataFrames 与 RDDs 互相转换 使用…
阅读更多...
动态规划（Dynamic Programming）—— Java解释

动态规划（Dynamic Programming）—— Java解释

一、基本思想 动态规划(Dynamic Programming)算法的核心思想是&#xff1a;将大问题划分为小问题进行解决&#xff0c;并将子问题的求解结果存储起来避免重复求解&#xff0c;从而一步步获取最优解的处理算法。 动态规划算法与分治算法类似&#xff0c;其基本思想也是将待求解…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023