C++学习笔记:红黑树

news/发布时间2024/7/21 9:48:05

红黑树

  • 什么是红黑树
  • 红黑树的规则
  • 红黑树节点的定义
  • 红黑树的插入
    • 空树插入
    • 非空插入条件判断
    • 新插入的节点 cur 不为 root 且 parent->_col 为红就需要调整
    • 父节点为左 grandf->left == parent
      • 当uncle节点为红色时,只需要进行颜色调整,即可
      • 当uncle为空 或 者存在但是为黑
        • parent 为left , cur 为 left 单纯的grandf右旋
          • uncle 为空
          • uncle不为空
        • parent 为left , cur 为 right 先左旋parent再右旋grandf
          • uncle为空
          • uncle不为空
    • 父节点为右 grandf->right == parent
  • 代码实现

什么是红黑树

红黑树是一种特殊的由二叉搜索树为底的数据结构,**之所以被成为红黑树,是因为在每个节点增加一个存储位表示这个节点的颜色,不是黑色就是红色,**因为其特数的规则,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。并具有更优的算法复杂度.
在这里插入图片描述

红黑树的规则

正是因为有以下规则的限制,红黑树才能是红黑树

  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 红色节点的两个孩子结点是黑色的,即不存在两个连续的红色节点
  • 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点:这也称为黑色平衡,确保树的高度相对平衡,从而保证了最长路径不超过最短路径的两倍。
  • 叶子节点均为黑色

红黑树节点的定义

在定义节点之前,最好先定义一个枚举类型,用来记录每个节点的颜色
并且因为涉及到旋转调整,因此红黑树和AVL树一样需要记录父亲节点

enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;T _data;Color _col;RBTreeNode(const T& data = T(),Color color = RED):_parent(nullptr), _left(nullptr), _right(nullptr), _col(color), _data(data){}};

红黑树的插入

红黑树的插入和AVL树的插入相似,但不同点是AVL树插入完成后改变的是平衡因子,而红黑树插入后改变的是节点的颜色.仅凭节点的旋转调整和节点颜色的改变就可以使之成为红黑树,不得不说发明红黑树的人真的是个天才!
因为涉及到后续迭代器的实现,因此我这里使用带头的红黑树来举例
在这里插入图片描述

我们将红黑树的插入分成几种情况依次来看

空树插入

当红黑树是空树时则直接插入,并且每次插入完成后将红黑树的根置为黑色,没什么特别的思路,直接上代码

		if (_root == nullptr){//根节点必须为黑色Node* root = new Node(data, BLACK);_root = root;_root->_parent = _pHead;_pHead->_parent = _root;}

非空插入条件判断

新插入的节点为红色,并且按照正常的二叉搜索树的条件去依次插入

			Node* cur = _root;//像搜索二叉树一样插入while (cur){if (cur->_data > data){parent = cur;cur = cur->_left;}else if (cur->_data < data){parent = cur;cur = cur->_right;}else{return false;}}//到位置了,创建节点并赋予红色 cur = new Node(data, RED);//判断是父节点的左还是右并进行链接if (data < parent->_data){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;
	链接完成后,查看父亲节点是否为红色  因为新节点为红色,若父节点也为红就需要进行调整

并且在每次插入完成后需要进行检查,若还是这种情况,则需要继续调整

新插入的节点 cur 不为 root 且 parent->_col 为红就需要调整

因为新插入的节点默认为红色,此时父亲节点也为红就需要进行调整

而红黑树的调整不仅仅只看cur节点和parent节点,还需要查看uncle(叔叔节点)和grandf(爷爷节点)节点及其颜色来进行判断
uncle节点:
在这里插入图片描述
接下来根据条件来进行调整

父节点为左 grandf->left == parent

当uncle节点为红色时,只需要进行颜色调整,即可

在这里插入图片描述
这种情况下这颗子树的黑色节点的高度依然没有发生变化
在进行颜色的调整后继续检查父亲节点

当uncle为空 或 者存在但是为黑

此时就要进行旋转和变色了,因为已经没有办法仅仅只通过变色来使这个子树的黑色节点的高度不发生变化了

在这里插入图片描述

parent 为left , cur 为 left 单纯的grandf右旋
uncle 为空

在这里插入图片描述

uncle不为空

此时当前的这个新插入的节点一定是从子树中调节变色变上来的,因为在有当前节点之前,parent一定有一个黑色节点的子树,否则这颗红黑树不平衡,
在这里插入图片描述

这种情况下这颗子树的黑色节点的高度依然没有发生变化
此时插入完成

parent 为left , cur 为 right 先左旋parent再右旋grandf
uncle为空

在这里插入图片描述

uncle不为空

在这里插入图片描述
在这里插入图片描述

父节点为右 grandf->right == parent

父节点为右时,与父节点为左完全相反,对照查看即可

代码实现

为了方便后续迭代器的实现,我使用了带头的红黑树:
定义头文件 RBTree.h

#pragma once#include<iostream>
using namespace std;enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;T _data;Color _col;RBTreeNode(const T& data = T(),Color color = RED):_parent(nullptr), _left(nullptr), _right(nullptr), _col(color), _data(data){}};template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree(){_pHead = new Node();_pHead->_left = _pHead;_pHead->_right = _pHead;}// 在红黑树中插入值为data的节点,插入成功返回true,否则返回false// 注意:为了简单起见,本次实现红黑树不存储重复性元素bool Insert(const T& data){Node*& _root = _pHead->_parent;if (_root == nullptr){//根节点必须为黑色Node* root = new Node(data, BLACK);_root = root;_root->_parent = _pHead;_pHead->_parent = _root;}else{Node* parent = nullptr;Node* cur = _root;//像搜索二叉树一样插入while (cur){if (cur->_data > data){parent = cur;cur = cur->_left;}else if (cur->_data < data){parent = cur;cur = cur->_right;}else{return false;}}//到位置了,创建节点并赋予红色 cur = new Node(data, RED);//判断是父节点的左还是右并进行链接if (data < parent->_data){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//链接完成后,查看父亲节点是否为红色  //因为新节点为红色,若父节点也为红就需要进行调整while (parent != _pHead && parent->_col == RED){Node* uncle = nullptr;Node* grandf = parent->_parent;if (grandf->_left == parent){//    g//   p    u//  c/cuncle = grandf->_right;//叔叔存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandf->_col = RED;//继续往上更新cur = grandf;parent = cur->_parent;}//叔叔为空 或 者存在但是为黑else{//p 为left  cur 为 left  单纯的右旋if (cur == parent->_left){RotateR(grandf);parent->_col = BLACK;grandf->_col = RED;}//p 为left  cur 为 right   先左旋p再右旋grandfelse{RotateL(parent);RotateR(grandf);cur->_col = BLACK;grandf->_col = RED;}break;}}else //grandf->_right == parent{//    g//  u    p//      c/cuncle = grandf->_left;//叔叔存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandf->_col = RED;//继续往上更新cur = grandf;parent = cur->_parent;}//叔叔不存在或者 叔叔为黑else{//p 为 right c 为 right 单纯的左旋if (cur == parent->_right){RotateL(grandf);parent->_col = BLACK;grandf->_col = RED;}//p 为 right c 为 left 先右旋parent再左旋grandfelse{RotateR(parent);RotateL(grandf);cur->_col = BLACK;grandf->_col = RED;}break;}}}}_root->_col = BLACK;_pHead->_left = LeftMost();_pHead->_right = RightMost();return true;}// 检测红黑树中是否存在值为data的节点,存在返回该节点的地址,否则返回nullptrNode* Find(const T& data){Node*& _root = _pHead->_parent;Node* cur = _root;while (cur){if (cur->_data > data){cur = cur->_left;}else if (cur->_data < data){cur = cur->_right;}else{return cur;}}return nullptr;}// 获取红黑树最左侧节点Node* LeftMost(){if (_pHead->_parent == nullptr){return _pHead;}Node* root = _pHead->_parent;;while (root->_left){root = root->_left;}return root;}// 获取红黑树最右侧节点Node* RightMost(){if (_pHead->_parent == nullptr){return _pHead;}Node* root = _pHead->_parent;;while (root->_right){root = root->_right;}return root;}// 检测红黑树是否为有效的红黑树,注意:其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){Node*& _root = _pHead->_parent;//空树if (_root == nullptr){return true;}else if(_root->_col == BLACK){size_t blacknum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){blacknum++;}cur = cur->_left;}size_t k = 0;return _IsValidRBTRee(_root, k , blacknum);}else{return false;}}void InOrder(){_InOrder(_pHead->_parent);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_data << ":";if (root->_col == RED){cout << "red"<<endl;}else{cout << "black" << endl;}_InOrder(root->_right);}bool _IsValidRBTRee(Node* root, size_t k, size_t blacknum ){if (root == nullptr){if (k != blacknum){cout << "黑色节点平衡" << endl;return false;}return true;}if (root->_col == BLACK){k++;}Node* parent = root->_parent;if (parent && parent->_col == RED && parent != _pHead && root->_col == RED){cout << "有连续的红色节点" << endl;return false;}return _IsValidRBTRee(root->_left, k, blacknum)&& _IsValidRBTRee(root->_right, k, blacknum);}// 左单旋void RotateL(Node* parent){Node*& _root = _pHead->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* pparent = parent->_parent;parent->_parent = subR;if (subRL){subRL->_parent = parent;}if (parent == _root){_root = subR;subR->_parent = _pHead;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}}// 右单旋void RotateR(Node* parent){Node*& _root = _pHead->_parent;Node* pparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;parent->_parent = subL;subL->_right = parent;if (subLR){subLR->_parent = parent;}if (_root == parent){_root = subL;subL->_parent = _pHead;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}}// 为了操作树简单起见:获取根节点Node* GetRoot(){return  _pHead->_parent;}private:Node* _pHead;
};

小小测试以下

#define _CRT_SECURE_NO_WARNINGS 1#include"RBTree.h"void test1()
{int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTree<int> rb;for (auto& e : arr){rb.Insert(e);}rb.InOrder();if (rb.Find(11) != nullptr){cout << "get find" << endl;}if (rb.IsValidRBTRee()){cout << "is RBTree" << endl;}else{cout << "is not BRTree" << endl;}
}int main()
{test1();return 0;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.shwantai.cn/a/75870126.html

如若内容造成侵权/违法违规/事实不符,请联系万泰站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

升级ChatGPT4.0失败的解决方案

ChatGPT 4.0科普 ChatGPT 4.0是一款具有多项出众功能的新一代AI语言模型。以下是关于ChatGPT 4.0的一些关键特点和科普内容&#xff1a; 多模态&#xff1a;ChatGPT 4.0具备处理不同类型输入和输出的能力。这意味着它不仅可以接收文字信息&#xff0c;还能处理图片、视频等多…

2023年中国高校大数据挑战赛D题参考论文发布(全网首发)

腾讯文档】2023年大数据挑战赛资料说明 https://docs.qq.com/doc/DSEpWUVFySm1ObFB0 基于数据分析的行业职业技术培训能力评价 摘要 中国是制造业大国&#xff0c;产业门类齐全&#xff0c;每年需要培养大量的技能娴熟的技术工人进入工厂。本文将基于题目给出的数据&#x…

仿牛客网项目---Elasticsearch分布式搜索引擎

1.什么是ElasticSearch分布式搜索引擎&#xff1f; Elasticsearch是一个开源的分布式搜索引擎&#xff0c;提供实时的、高可用性的搜索和分析解决方案。它支持快速索引和搜索大规模数据&#xff0c;具有分布式架构、RESTful API、基于JSON的查询语言等功能&#xff0c;适用于各…

Python 科学计算与可视化

一、学习目标 1&#xff0e;了解NumPy数组简单应用。 2&#xff0e;掌握Matplotlib制作折线图、柱形图等。 3&#xff0e;了解pandas进行数据分析使用。 二、相关练习 1、编写程序&#xff0c;建立一维数组a&#xff0c;数组值为array([1,2,3,4])&#xff1b;建立二维数组…

Ajax、Axios、Vue、Element与其案例

目录 一.Ajax 二.Axios 三.Vue 四.Element 五.增删改查案例 一.依赖&#xff1a;数据库&#xff0c;mybatis&#xff0c;servlet&#xff0c;json-对象转换器 二.资源&#xff1a;elementvueaxios 三.pojo 四.mapper.xml与mapper接口 五.service 六.servlet 七.html页…

macbook pro 2018 安装 arch linux 双系统

文章目录 友情提醒关于我的 mac在 mac 上需要提前做的事情复制 wifi 驱动 在 linux 上的操作还原 wifi 驱动连接 wifi 网络磁盘分区制作文件系统挂载分区 使用 archinstall 来安装 arch linux遗留问题 友情提醒 安装 archl linux 的时候&#xff0c;mac 的键盘是没法用的&#…