红黑树——原理刨析

2023-11-06 13:45
文章标签 原理 红黑树 刨析

本文主要是介绍红黑树——原理刨析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        众所周知，红黑树是从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.chinasem.cn/article/356985。

相关文章

MySQL中的MVCC底层原理解读

MySQL中的MVCC底层原理解读

《MySQL中的MVCC底层原理解读》本文详细介绍了MySQL中的多版本并发控制（MVCC）机制,包括版本链、ReadView以及在不同事务隔离级别下MVCC的工作原理,通过一个具体的示例演示了在可重... 目录简介ReadView版本链演示过程总结简介MVCC（Multi-Version Concurr
阅读更多...
Redis主从/哨兵机制原理分析

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制
阅读更多...
Redis主从复制的原理分析

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维
阅读更多...
SpringCloud配置动态更新原理解析

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
hdu4407容斥原理

hdu4407容斥原理

题意： 有一个元素为 1~n 的数列{An}，有2种操作（1000次）： 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu
阅读更多...
hdu4059容斥原理

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit
阅读更多...
寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

寻迹模块TCRT5000的应用原理和功能实现（基于STM32）

目录 概述 1 认识TCRT5000 1.1 模块介绍 1.2 电气特性 2 系统应用 2.1 系统架构 2.2 STM32Cube创建工程 3 功能实现 3.1 代码实现 3.2 源代码文件 4 功能测试 4.1 检测黑线状态 4.2 未检测黑线状态 概述 本文主要介绍TCRT5000模块的使用原理，包括该模块的硬件实现方式，电路实现原理，还使用STM32类
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2