红黑树——原理刨析

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

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景:什么是隐式锁?2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L

Spring Cloud Hystrix原理与注意事项小结

《SpringCloudHystrix原理与注意事项小结》本文介绍了Hystrix的基本概念、工作原理以及其在实际开发中的应用方式,通过对Hystrix的深入学习,开发者可以在分布式系统中实现精细... 目录一、Spring Cloud Hystrix概述和设计目标(一)Spring Cloud Hystr

MySQL中的MVCC底层原理解读

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