【c++篇】：探秘红黑树平衡旋转原理--维持树的高度平衡之道

news/2024/11/25 9:08:49/

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

文章目录

  • 前言
  • 一.红黑树的概念和性质
    • 定义和性质
    • 节点结构与表示
  • 二.模拟实现
    • 基本框架
    • 红黑树的插入
    • 红黑树的变色处理和平衡调整
    • 红黑树的平衡检查
    • 测试
  • 三.完整代码文件

前言

在上一篇文章中，我们已经学习了平衡树之一的AVL树，在这篇文章中，我们将要继续学习另一个平衡树–红黑树。注意：如果想要更好地学习红黑树，建议先看一下关于二叉搜索树以及AVL树的讲解，红黑树是在这两个基础上来讲解的，有了上面两个的基础才能更好的理解和学习红黑树。

一.红黑树的概念和性质

红黑树是一种自平衡的二叉搜索树，他在计算机科学中有着广泛的应用，特别是在需要频繁插入，删除和查找的场景中。以下是关于红黑树的详细讲解：

定义和性质

红黑树是一种带有颜色属性的二叉搜索树，其中每个节点都带有红色或者黑色的颜色标志。它通过一系列的规则来确保树的平衡性，从而在插入，删除和查找操作中保持较高的效率，红黑树的性质包括：

  • 1.每个节点要么是红色要么是黑色
  • 2.根节点是黑色
  • 3.每个叶子节点（NIL节点，在红黑树中通常表示为空节点）是黑色
  • 4.如果一个节点是红色，那他的两个子节点都是黑色，即不存在两个连续的红色节点
  • 5.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

上面这些性质共同确保了红黑树的最长路径不会超过最短路径的二倍，从而保证了树的高度相对平衡，进而确保了插入，删除和查找操作的时间复杂度为O(log N)

在这里插入图片描述

节点结构与表示

在红黑树中，每个节点通常都包含一下信息：

  • 键值对(key,value)：key值用于存储节点的值，并作为二叉搜索树的比较基值
  • 颜色(_colour)：红色或者黑色，用于维护红黑树的平衡性
  • 左子节点指针(_left)：指向节点的左子节点
  • 右子节点指针(_right)：指向节点的右子节点
  • 父节点指针(_parent)：指向节点的父节点

二.模拟实现

基本框架

代码实现：

#include<iostream>
#include<utility>
#include<vector>
#include<time.h>
using namespace std;//颜色枚举
enum Colour{RED,BLACK
};//节点类封装
template<class K,class V>
class RBTreeNode{
public://构造函数RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)    {}//成员变量RBTree<K,V>* _left;RBTree<K,V>* _right;RBTree<K,V>* _parent;pair<K,V> _kv;Colour _col;
};//红黑树类的封装
template<class K,class V>
class RBTree{typedef RBTreeNode<K,V> Node;
public://构造函数RBTree():_root(nullptr){}    //....其他成员函数private://成员变量Node* _root;
};

红黑树的插入

红黑树的插入和二叉搜索树的原理一样，通过基值来查找到对应的插入位置，但不同的时，在插入完后需要进行变色处理以及出现失衡时进行平衡调整，具体代码如下：

  • 代码实现：

    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<kv.first){parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;//变色处理以及平衡调整//....//插入结束后要将根节点的颜色变为黑色_root->_col=BLACL;return true;
}

红黑树的变色处理和平衡调整

注意：这里只详细讲解红黑树的变色处理，以及各种平衡调整情况，关于如何旋转可以看我之前关于AVL树的文章，里面有关于旋转的详细讲解

1.parent节点在grandfather节点的左子节点

  • 代码实现：

    bool insert(const pair<int,int>& kv){//...//插入过程//变色处理和平衡调整while(parent&&parent->_col=RED){Node*grandfather=parent->_parent;//如果parent节点在grandfather节点的左子节点if(parent==grandfather->_left){Node* uncle=grandfather->_right;//如果uncle节点存在且节点为红色if(uncle&&uncle->_col==RED){//变色parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上cur=grandfather;parent=cur->_parent;}//如果uncle节点不存在或者存在且为黑色else{//如果cur节点在parent节点的左子节点if(cur=parent->_left){//右单旋RotateR(grandfather);//旋转后变色grandfather->_col=RED;parent->_col=BLACK;}//如果cur节点在parent节点的右子节点else{//先左单旋，再右单旋RotateL(parent);RoateR(grandfather);//旋转后变色cur->_col=BLACK;grandfather->_col=RED;}//旋转后就是平衡了，直接结束break;}}//如果parent节点再grandfather节点的右子节点//....}_root->_col=BLACK;return true;
}

  • 实现原理：

    在这里插入图片描述

2.parent节点在grandfather节点的右子节点

  • 代码实现：

    bool insert(const pair<int,int>& kv){//...//插入过程//变色处理和平衡调整while(parent&&parent->_col==RED){Node* grandfather=parent->_parent;//parent节点在grandfather节点的左子节点//....//parent节点在grandfather节点的右子节点else{Node* uncle=grandfather->_left;//如果uncle节点存在且为红色if(uncle&&uncle->_col=RED){//变色parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上cur=grandfather;parent=cur->_parent;}//如果uncle节点不存在 或者 节点为黑色else{//如果cur节点在parent节点的右子节点if(cur==parent->_right){//左单旋RotateL(grandfather);//变色parent->_col=BLACK;grandfather->_col=RED;}//如果cur节点在parent节点的左子节点else{//先右单旋，再左单旋RotateR(parent);RotateL(grandfather);//旋转后变色cur->_colo=BLACK;grandfather->_col=RED;}break;}}}_root->_col=BLACK;return true;
}

  • 实现原理：

    在这里插入图片描述

红黑树的平衡检查

  • 代码实现：
//平衡检查函数
bool IsBlance(){return _IsBlance(_root);
}bool CheckColour(Node* root,int blacknum,int benchmark){//当遇到空节点时，检查该路径上黑色节点个数是否等于基准值，不等于说明出现错误if(root==nullptr){if(blacknum!=benchmark){return false;}return true;}//当节点是黑色时，该路径上黑色节点个数加一if(root->_col==BLACK){blacknum++;}//当节点是红色时，检查父节点是否也是红色，如果是红色，说明出现连续的红色节点，出现错误if(root->_RED&&root->_parent&&root->_parent->_col==RED){cout<<root->_kv.first<<"RED false"<<endl;return false}//递归调用，检查左右子树return CheckColour(root->_left,blacknum,benchmark)&& CheckColour(root->_right,blacknum,benchmark);
}bool _IsBlance(Node* root){//如果是空树直接返回trueif(root==nullptr){return true;}//如果不是空树，但根节点不是黑色，出现错误if(root->_col!=BLACK){return false;}//设置一个基准值benchmark,从树的最左路径查找黑色节点个数作为基准值int benchmark=0;Node* cur=root;while(cur){if(cur->_col==BLACK){benchmark++;}cur=cur->_left;}return CheckColour(root,0,benchmark);
}
  • 实现原理：
    • 和之前的AVL树一样，这里也是借用两个函数来实现平衡检查
    • 当是空树时，直接返回true，非空树时检查根节点是否是黑色，如果不是，说明出现错误
    • 之后设置一个基准值benchmark,从树的最左路径查找黑色节点个数作为基准值，调用检查函数CheckColour()
    • 检查函数中当遇到空节点时，检查该路径上黑色节点个数是否等于基准值，不等于说明出现错误
    • 当节点是黑色时，该路径上黑色节点个数加一；当节点是红色时，检查父节点是否也是红色，如果是红色，说明出现连续的红色节点，出现错误
    • 递归调用，检查左右子树

测试

  • 测试代码：

    #include"RBTree.h"//第一组数据测试
void test1(){int arr[]={16, 3, 7, 11, 9, 26, 18, 14, 15};RBTree<int,int> t;for(auto e : arr){t.insert(make_pair(e,e));cout<<"Insert:"<<e<<"->"<<t.IsBlance()<<endl;}}//随机大量数据测试
void test2(){const int N=1000;vector<int> v;v.reserve(N);srand(time(0));for(size_t i=0;i<N;i++){v.push_back(i);}RBTree<int,int> t;for(auto e : v){t.insert(make_pair(e,e));}cout<<t.IsBlance()<<endl;cout<<t.Height()<<endl;
}int main(){//test1();test2();return 0;
}

  • 测试结果：

    • 第一组测试：

      在这里插入图片描述

    • 第二组测试：

      在这里插入图片描述

三.完整代码文件

RBTree.h文件完整代码：

#include<iostream>
#include<utility>
#include<vector>
#include<time.h>
using namespace std;enum Colour {RED,BLACK
};template<class K , class V>
class RBTreeNode {
public://构造函数RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}//成员变量RBTreeNode<K,V>* _left;RBTreeNode<K,V>* _right;RBTreeNode<K,V>* _parent;pair<K,V> _kv;Colour _col;
};template<class K , class V>
class RBTree {typedef RBTreeNode<K,V> Node;
public://构造函数RBTree():_root(nullptr){}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<kv.first){parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;while(parent&&parent->_col==RED){Node* grandfather=parent->_parent;//如果parent节点在左子节点if(parent==grandfather->_left){Node* uncle=grandfather->_right;//如果uncle节点存在且节点为红色if(uncle&&uncle->_col==RED){//变色parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上cur=grandfather;parent=cur->_parent;}//如果uncle节点不存在 或者 节点为黑色else{//如果cur节点在左子节点if(cur==parent->_left){//右单旋RotateR(grandfather);//旋转后变色grandfather->_col=RED;parent->_col=BLACK;}//如果cur节点在右子节点else{//左双旋//先左单旋，再右单旋RotateL(parent);RotateR(grandfather);//旋转后变色cur->_col=BLACK;grandfather->_col=RED;}break;}}//如果parent节点在右子节点else{Node* uncle=grandfather->_left;//如果uncle节点存在且节点为红色if(uncle&&uncle->_col==RED){//变色parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上cur=grandfather;parent=cur->_parent;}//如果uncle节点不存在 后者 节点为黑色else{//如果cur节点在右子节点if(cur==parent->_right){//左单旋RotateL(grandfather);//变色parent->_col=BLACK;grandfather->_col=RED;}//如果cur节点在左子节点else{//右双旋//先右单旋，再左单旋RotateR(parent);RotateL(grandfather);//旋转后变色cur->_col=BLACK;grandfather->_col=RED;}break;}}}_root->_col=BLACK;return true;}int Height(){return _Height(_root);}bool IsBlance(){return _IsBlance(_root);}private:int _Height(Node* root){if(root==nullptr){return 0;}int leftheight=_Height(root->_left);int rightheight=_Height(root->_right);return leftheight>rightheight ? leftheight+1 : rightheight+1;}bool CheckColour(Node* root,int blacknum,int benchmark){//如果节点是空，判断黑色节点个数是否等于基准值if(root==nullptr){if(blacknum!=benchmark){return false;}return true;}//如果节点是黑色，黑色个数加加if(root->_col==BLACK){blacknum++;}//如果节点是红色，判断父节点是否也是红色，不能出现连续的红色节点if(root->_col==RED&&root->_parent&&root->_parent->_col==RED){cout<<root->_kv.first<<"RED False"<<endl;return false;}return CheckColour(root->_left,blacknum,benchmark)&&CheckColour(root->_right,blacknum,benchmark);}bool _IsBlance(Node* root){if(root==nullptr){return true;}//如果根节点不是黑色，返回错误if(root->_col!=BLACK){return false;}//设置一个基准值int benchmark=0;Node* cur=root;while(cur){if(cur->_col==BLACK){benchmark++;}cur=cur->_left;}return CheckColour(root,0,benchmark);}//左单旋void RotateL(Node* parent){Node* cur=parent->_right;Node* curleft=cur->_left;Node* ppnode=parent->_parent;parent->_right=curleft;if(curleft){curleft->_parent=parent;}cur->_left=parent;parent->_parent=cur;if(ppnode){if(ppnode->_left==parent){ppnode->_left=cur;cur->_parent=ppnode;}else{ppnode->_right=cur;cur->_parent=ppnode;}}else{cur->_parent=nullptr;_root=cur;}}//右单旋void RotateR(Node* parent){Node* cur=parent->_left;Node* curright=cur->_right;Node* ppnode=parent->_parent;parent->_left=curright;if(curright){curright->_parent=parent;}cur->_right=parent;parent->_parent=cur;if(ppnode){if(ppnode->_left==parent){ppnode->_left=cur;cur->_parent=ppnode;}else{ppnode->_right=cur;cur->_parent=ppnode;}}else{cur->_parent=nullptr;_root=cur;}}private:Node* _root;
};

以上就是关于平衡树之一的红黑树平衡原理讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
在这里插入图片描述


http://www.ppmy.cn/news/1549775.html

相关文章

七天掌握SQL---＞第四天：事务处理与并发控制

七天掌握SQL---＞第四天：事务处理与并发控制

# 7天掌握SQL - 第四天&#xff1a;事务处理与并发控制 ## 目标 - 学习事务处理的基本概念&#xff0c;如ACID特性。 - 掌握并发控制的方法&#xff0c;如锁机制、事务隔离级别等。 - 通过实际案例练习事务处理和并发控制。 ## 1. 事务处理的基本概念 事务处理是数据库管理系…
阅读更多...
鸿蒙主流路由详解

鸿蒙主流路由详解

鸿蒙主流路由详解 Navigation Navigation更适合于一次开发,多端部署,也是官方主流推荐的一种路由控制方式,但是,使用起来入侵耦合度高,所以,一般会使用HMRouter,这也是官方主流推荐的路由 Navigation官网地址 个人源码地址 路由跳转 第一步-定义路由栈 Provide(PageInfo) pag…
阅读更多...
idea添加版权信息

idea添加版权信息

1、添加Copyright Profiles 打开Settings -> Editor -> Copyright -> Copyright Profiles -> 新增 Copyright (c) 【你的版权信息】 【开始年份】-${today.year}. All rights reserved.如&#xff1a; Copyright (c) by cwp 2024-${today.year}. All rights rese…
阅读更多...
Zero-Shot Next-Item Recommendation using Large Pretrained Language Models-问题咨询

Zero-Shot Next-Item Recommendation using Large Pretrained Language Models-问题咨询

问题背景&#xff1a; 我正在尝试复现一篇名为 “Zero-Shot Next-Item Recommendation using Large Pretrained Language Models” 的论文中的实验结果。 遇到的问题&#xff1a; 缺少关键代码&#xff1a; 我发现论文代码库中没有提供计算 HR10 和 NDCG10 这两个关键指标的…
阅读更多...
JavaWeb后端开发知识储备2

JavaWeb后端开发知识储备2

目录 1.HttpClient 2.微信小程序开发 3.Spring Cache 1.HttpClient 简单来说&#xff0c;HttpClient可以通过编码的方式在Java中发送Http请求 2.微信小程序开发 微信小程序的开发本质上是前端开发&#xff0c;对于后端程序员来说了解即可 3.Spring Cache Spring Cache 是…
阅读更多...
Spring Boot 3.3高级日志配置详解：从 Logback 到 Log4j 2 的全面掌握

Spring Boot 3.3高级日志配置详解：从 Logback 到 Log4j 2 的全面掌握

Spring Boot 3.3 对日志系统进行了一些更新和改进&#xff0c;特别是在对 Logback 和 Log4j 2 的支持上。以下是从 Logback 切换到 Log4j 2 的一些高级配置详解&#xff1a; 1. 依赖管理 首先&#xff0c;你需要在项目的 pom.xml 或 build.gradle 文件中包含正确的依赖。 对…
阅读更多...
基于STM32的火灾报警装置的Proteus仿真

基于STM32的火灾报警装置的Proteus仿真

文章目录 一、火灾报警1.题目要求2.思路2.1 主控2.2 传感器2.3 设定阈值--按键2.4 报警和通风2.5 OLED显示2.6 电源部分2.7 远程终端 3.仿真3.1 未仿真时3.2 仿真开始&#xff0c;界面13.3 切换界面23.4 切换界面3 4.仿真程序4.1 程序说明4.2 主函数4.3 OLED显示函数 二、总结 …
阅读更多...
什么是Axios，有什么特点

什么是Axios，有什么特点

什么是 Axios&#xff1f; Axios 是一个基于 Promise 的 HTTP 客户端&#xff0c;可以用于浏览器和 Node.js 环境。它由 Matt Zabriskie 创建&#xff0c;旨在提供一个简单、灵活且功能强大的 HTTP 请求库。Axios 支持所有现代浏览器和 Node.js&#xff0c;可以用于发送 GET、…
阅读更多...
最新文章

Copyright @ 2022~2023