红黑树(RBTree)的插入算法以及如何测试一棵树是否是红黑树?(详细图解说明)

本文主要是介绍红黑树(RBTree)的插入算法以及如何测试一棵树是否是红黑树?(详细图解说明),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.什么叫红黑树?

             红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,因而近似于平衡。


2.红黑树的性质

     

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

   2. 根节点是黑色的

   3. 如果一个节点是红色的,则它的两个子节点是黑色的(没有连续的红色结点

   4. 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。(每条路径的黑色结点个数相等)

   5. 每个叶子节点都是黑色的(这里的叶子节点是指的NIL节点(空节点))


3.红黑树为什么通过颜色的约束能够保证最长路径不超过最短路径的两倍?




4.红黑树的结点的定义

enum Colour
{RED,BLACK
};template<typename K,typename V>
struct RBTreeNode
{//结点RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;//颜色Colour _col;//KVK _key;V _value;RBTreeNode(const K& key, const V& value):_key(key), _value(value), _left(NULL), _right(NULL), _parent(NULL), _col(RED)  //把新增结点置成红色为了保持每条路径的黑色结点个数不变{}
};


为什么把新增结点的颜色设置为红色而不是黑色呢?

    因为设置为红色,比较容易维护这棵树,设置为黑色,会导致当前这条路径多了一个黑色结点,为了满足每条路径的黑色结点个数相同,需要维护多条路径。



5.红黑树插入的几种情况


注:由于p结点(父结点)可能为g结点(祖父结点)的左孩子或者右孩子,下面的作图以左孩子为模板,右孩子与左孩子类似,只是在某些需要旋转的情况下不一样。

    (1)插入结点为根节点(只有一个结点的情况),将结点颜色置成黑色即可

    

    (2)插入结点的父结点或调整结点的父结点为黑色结点(不需要调整)



  

  (3)插入结点的父结点或向上调整的结点父结点为红色之——uncle结点存在为红色

  

  (4)插入结点的父结点为红色之——uncle结点不存在



  (5)插入结点的父结点为红色之——uncle结点存在为黑色





6.红黑树插入实现代码


template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(NULL){}bool Insert(const K& key, const V& value){//1.插入结点为根节点,必须为黑色if (_root == NULL){_root = new Node(key, value);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = NULL;while (cur != NULL){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key, value);if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent != NULL){Node* pparent = parent->_parent;Node* uncle = NULL;//2.如果插入节点或者调整结点的父结点为黑色结点,增加一个红色结点,对每条路径的黑色结点个数没影响if (parent->_col == BLACK){break;}//判断叔叔结点是否存在,存在是在左还是右?if (pparent != NULL){if (pparent->_right == parent)uncle = pparent->_left;elseuncle = pparent->_right;}//3.插入结点或调整结点父结点为红色且叔叔结点为红色if (uncle != NULL&&uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;if (pparent == _root)return true;pparent->_col = RED;//继续向上调整//假如调整到根结点,只需将根结点的颜色置为黑色即可if (parent == _root){parent->_col = BLACK;return true;}cur = parent->_parent;parent = cur->_parent;}//4.插入结点或调整结点父结点为红色且叔叔结点不存在或//  插入结点或调整结点父结点为红色且叔叔结点存在为黑色二者逻辑一样。else//剩下的情况 (uncle == NULL || uncle->_col == BLACK){//判断父结点在左还是在有if (pparent->_left == parent){//左--左if (parent->_left == cur){_RotateR(pparent);pparent->_col = RED;parent->_col = BLACK;if (pparent == _root){_root = parent;}}//左--右else{_RotateL(parent);_RotateR(pparent);cur->_col = BLACK;parent->_col = RED;pparent->_col = RED;if (pparent == _root)_root = cur;}}//父结点在右else{//右--右if (parent->_right == cur){_RotateL(pparent);pparent->_col = RED;parent->_col = BLACK;if (pparent == _root)_root = parent;}//右--左else{_RotateR(parent);_RotateL(pparent);parent->_col = RED;pparent->_col = RED;cur->_col = BLACK;if (pparent == _root)_root = parent;}}break;}}return true;}void InOrder(){_InOrder(_root);cout << endl;}
protected:void _InOrder(Node* root){if (root == NULL)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void _RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;//链上SubLRparent->_left = SubLR;if (SubLR != NULL)SubLR->_parent = parent;Node* pparent = parent->_parent;//链上SubLSubL->_parent = pparent;if (pparent != NULL){if (pparent->_left == parent)pparent->_left = SubL;elsepparent->_right = SubL;}//链上parentparent->_parent = SubL;SubL->_right = parent;}void _RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL= SubR->_left;//链上SubLRparent->_right= SubRL;if (SubRL != NULL)SubRL->_parent = parent;Node* pparent = parent->_parent;//链上SubLSubR->_parent = pparent;if (pparent != NULL){if (pparent->_left == parent)pparent->_left = SubR;elsepparent->_right = SubR;}//链上parentparent->_parent = SubR;SubR->_left = parent;}Node* _root;
};

7.如何测试一棵树是不是红黑树?

(1)测试它的根节点是不是黑色

(2)测试是否有连续的红结点

(3)测试每条路径上的黑节点的数量是否相等?

以某一条路径(测试用例用的是左子树)上的黑色结点的个数为判断标准,如果有一条不满足相等,证明不是红黑树。

实现代码:

    

bool Isbalance(){//1.空树认为是RBTreeif (_root == NULL)return true;//2.根结点非黑不是RBTreeif (_root->_col == RED)return false;int count = 0;//以左子树上的黑色结点作为一个基准,如果一样就证明是,不一样就证明不是RBTreeNode* cur = _root;while (cur != NULL){if (cur->_col == BLACK)count++;cur = cur->_left;}//num用来标记每条路径上的黑色结点的个数//count用来标记左子树上的黑色结点的个数int num = 0;return _Isbalance(_root, count, num);}bool _Isbalance(Node* root, int count, int num){if (root == NULL)return true;//3.连续红结点不是RBTree,root结点一定有父结点if (root->_col == RED&&root->_parent->_col == RED){cout << root->_key << " 有连续的红结点" << endl;return false;}if (root->_col == BLACK)num++;if (root->_left == NULL&&root->_right == NULL){if (num != count){cout << root->_key << " 黑色结点个数不一样" << endl;return false;}}return _Isbalance(root->_left, count, num) && _Isbalance(root->_right, count, num);}

  




8.测试用例

测试用例:

void TestRBTree()
{int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int, int> t;for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++){t.Insert(a[i], i);}t.InOrder();cout << "Isbalance---->" << t.Isbalance()<< endl;
}


       运行结果和测试用例红黑树模型:





9.红黑树和AVL树比较

      (1)红黑树和AVL树都是高效的平衡二叉树,增删查改的时间复杂度都是O(lg(N))。            

         (2)红黑树的不追求完全平衡,保证最长路径不超过最短路径的2倍,相对而言,降低了旋转的要求,所以性能会优于AVL树,所以实际运用中红黑树更多。(效率差不多要求还低)。

注:

AVL旋转因子的调节(详细图解)



这篇关于红黑树(RBTree)的插入算法以及如何测试一棵树是否是红黑树?(详细图解说明)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/579925

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种,单机模式和集群模式以及伪集群模式。 ■ 单机模式:Zookeeper只运行在一台服务器上,适合测试环境; ■ 伪集群模式:就是在一台物理机上运行多个Zookeeper 实例; ■ 集群模式:Zookeeper运行于一个集群上,适合生产环境,这个计算机集群被称为一个“集合体”(ensemble) Zookeeper通过复制来实现

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在