红黑树——原理刨析

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。

相关文章

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

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

文章目录 前言一、协同过滤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类
阅读更多...
TL-Tomcat中长连接的底层源码原理实现

TL-Tomcat中长连接的底层源码原理实现

长连接：浏览器告诉tomcat不要将请求关掉。  如果不是长连接，tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。
阅读更多...
PHP原理之内存管理中难懂的几个点

PHP原理之内存管理中难懂的几个点

PHP的内存管理, 分为俩大部分, 第一部分是PHP自身的内存管理, 这部分主要的内容就是引用计数, 写时复制, 等等面向应用的层面的管理. 而第二部分就是今天我要介绍的, zend_alloc中描写的关于PHP自身的内存管理, 包括它是如何管理可用内存, 如何分配内存等. 另外, 为什么要写这个呢, 因为之前并没有任何资料来介绍PHP内存管理中使用的策略, 数据结构, 或者算法. 而在我们
阅读更多...
Smarty模板执行原理

Smarty模板执行原理

为了实现程序的业务逻辑和内容表现页面的分离从而提高开发速度，php 引入了模板引擎的概念，php 模板引擎里面最流行的可以说是smarty了，smarty因其功能强大而且速度快而被广大php web开发者所认可。本文将记录一下smarty模板引擎的工作执行原理，算是加深一下理解。 其实所有的模板引擎的工作原理是差不多的，无非就是在php程序里面用正则匹配将模板里面的标签替换为php代码从而将两者
阅读更多...
Restful API 原理以及实现

Restful API 原理以及实现

先说说API 再说啥是RESRFUL API之前，咱先说说啥是API吧。API大家应该都知道吧，简称接口嘛。随着现在移动互联网的火爆，手机软件，也就是APP几乎快爆棚了。几乎任何一个网站或者应用都会出一款iOS或者Android APP，相比网页版的体验，APP确实各方面性能要好很多。 那么现在问题来了。比如QQ空间网站，如果我想获取一个用户发的说说列表。 QQ空间网站里面需要这个功能。
阅读更多...
laravel框架实现redis分布式集群原理

laravel框架实现redis分布式集群原理

在app/config/database.php中配置如下： 'redis' => array('cluster' => true,'default' => array('host' => '172.21.107.247','port' => 6379,),'redis1' => array('host' => '172.21.107.248','port' => 6379,),) 其中cl
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2