当前位置： 首页 > news >正文

从零手写红黑树（C++实现详解）

news 2025/7/20 19:40:28

目录

一、红黑树概述

二、红黑树节点设计

  (1)枚举红黑

（2）红黑树的节点设计

三、红黑树核心实现:Insert

1.首先将节点遍历到对应位置创建对应节点并插入到二叉搜索树对应的位置

2.本文重点的重点

（1）parent为黑时直接插入即可

（2）uncle存在且为红

（3）uncle不存在

（4）uncle存在且为黑

四、红黑树检查代码

五、总代码

1.RBTree.h

2.Test.c代码

一、红黑树概述

学完AVL树之后对我来说，红黑树可能更容易理解，还有水了这么多篇，该认真写一篇了，哈哈哈哈。

红黑树顾名思义就是得有红色和黑色的树，红黑树利用红色和黑色节点来创建二叉平衡搜索树

红黑树的5条核心特点：

（1）每个节点是红色或黑色

（2）根节点必须是黑色

（3）所有叶子节点（NIL/空节点）是黑色（NIL节点是红黑树中所有空指针的替代节点，表示树的

叶子位置。）

（4）红色节点的子节点必须是黑色（即不能有连续的黑色节点）

（5）从任意节点到其所有叶子节点的路径上，黑色节点的数量相同

二、红黑树节点设计

  (1)枚举红黑

enum Colour
{RED,BLACK
};

（2）红黑树的节点设计

1.其中的三叉链是指_left _right _parent ,在我的理解中_left和_right是为了前进，而_parent是为了后退

2.kv是储存的值，set中储存的V是与K一样的类型，map中储存的是<const K ,V>

template<class K,class V> 
struct RBTreeNode
{//三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V> & kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

三、红黑树核心实现:Insert

二叉树的核心操作就是插入，插入分为三种情况:

（1）uncle存在且为红

（2）uncle不存在

（3）uncle存在且为黑

1.首先将节点遍历到对应位置创建对应节点并插入到二叉搜索树对应的位置

	typedef RBTreeNode<K, V> Node;
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;}}//这里是创建一个初始化_kv(kv)的新节点，并别把颜色初始化为红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;

2.本文重点的重点

注：给出的图画是以 parent == grandfather->_left 条件下进行的,panret==grandfather->_right同理，最后有完整代码可参考

（1）parent为黑时直接插入即可

！！！下面都是parent为红的情况

（2）uncle存在且为红

在parent和uncle为红的情况我们，让我们grandfatehr变成红，让parent和uncle变成黑

然后让cur=grandfatehr ,parent=cur->_parent,grandfather=parent->_parent

继续向上处理：

（一） .grandfather没有父亲，就是根，grandfatehr变黑即可

（二）.grandfather有父亲，父亲时黑色，就结束了

（三）.grandfather有父亲，父亲是红色，和上面一样处理

继续像刚才一样的操作

因为grandfatehr 是根节点，因为根节点只能是红，最后让根节点的颜色变成红                  

最后有完整代码，现在给出对应部分代码

Node* uncle = grandfather->_right;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;//grandfather = parent->_parent; 
}
（3）uncle不存在

这里是grandfather->_left且parent是红色节点的前提，这里有两种情况

情况一：parent->_left=cur

在grandfather节点进行右旋，让grandfather的颜色变成红色，让parent的颜色变成黑色

情况二:parent->_right=cur

在parent节点进行左旋

再在grandfather哪里进行右旋

旋转完之后，grandfather的颜色变红，cur的颜色变黑

代码：

现在给出对应部分代码，左旋，右旋，左右旋，右左旋代码也在最后的完整代码中

else//uncle不存在或uncle存在且为黑
{//这是什么意思？这里我自己判断了if (cur == parent->_left ){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED; }break;
}
（4）uncle存在且为黑

这里是grandfather->_right且parent是红色节点的前提，与（3）的以grandfather->_left情况相反了

这种情况有点特殊，要操作一步才能得到

按照（2）变成，变成我们（4）所需要的状态

情况一：parent->_right=cur

然后对grandfather进行左旋

grandfather的颜色变红，parent的颜色变黑

情况二：parent->_left=cur

首先要在parent进行右旋操作

再对grandparent进行左旋，让grandfather的颜色变红，cur的颜色变黑

代码：

现在给出对应部分代码，左旋，右旋，左右旋，右左旋代码也在最后的完整代码中

if (cur == parent->_right)
{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;
}
else
{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;
}
break;

四、红黑树检查代码

1.通过递归得出高度的代码

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;
}

2.根据红节点的父亲是否是红色来判断红黑树是否有误

//为什么不是int & blacknum，因为要利用栈帧，保存当前形式下，blackanum的值
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 << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left,blacknum,benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}

3.利用左边的那条支路创建黑高的基准值，再在checkcolour把所有节点黑高节点检查一遍得出结果

bool IsBalance()
{return IsBalance(_root);
}
bool IsBalance(Node* root)
{if (root == nullptr)return true;if (root->_col != BLACK)return false;
//	return CheckColour(root);//基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchmark;  }//这里是以最左路径为标准cur = cur->_left;}return  CheckColour(root, 0, benchmark);
}

五、总代码

1.RBTree.h

#pragma once
#include<iostream>
#include<stdio.h>
using namespace std;enum Colour
{RED,BLACK
};
template<class K,class V> 
struct RBTreeNode
{//三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V> & kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K, class V>
struct RBTree
{typedef RBTreeNode<K, V> Node;
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){//Node* parent = 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 if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;while (parent&&parent->_col==RED){Node* grandfather = 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;//grandfather = parent->_parent; }else//uncle不存在或uncle存在且为黑{//这是什么意思？这里我自己判断了if (cur == parent->_left ){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED; }break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;//grandfather = parent->_parent;}else{//我觉得案按理来说得判断，这是叔叔不存在的情况？if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){//这是AVL树第一集的末尾了Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){//这是AVL树第一集的末尾了Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}Node* ppnode = parent->_parent;cur->_right = parent;//Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = cur;}else{ppnode->_left = cur;}cur->_parent = ppnode;}}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;//int bf = cur->_left->_bf;RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;//	int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);}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;}//为什么不是int & blacknum，因为要利用栈帧，保存当前形式下，blackanum的值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 << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left,blacknum,benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)return false;//	return CheckColour(root);//基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchmark;  }//这里是以最左路径为标准cur = cur->_left;}return  CheckColour(root, 0, benchmark);}
private:Node* _root = nullptr;
};

2.Test.c代码

插入10000个随机数进行测试

#include"RBTree.h"
#include<vector>
#include<time.h>
//int main()
//{
//	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
//	RBTree<int, int> t;
//	for (auto e : a)
//	{
//		t.Insert(make_pair(e, e));
//		cout << "Insert:" << e << "->"<<t.IsBalance() << endl;
//	}
//	return 0;
//}int main()
{const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0;i < N;i++){v.push_back(rand());}RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));cout << "Insert:" << e << "->" << t.IsBalance() << endl;}return 0;
}

谢谢观众老爷的观看！！！

http://www.lryc.cn/news/593782.html

相关文章：

  • 【工具变量】地级市城市包容性绿色增长数据（2011-2023年）
  • [FFmpeg] AVFormatContext、AVInputFormat、AVOutputFormat | libavformat
  • 语义熵怎么增强LLM自信心的
  • MyBatis动态SQL全解析：五大核心标签实战指南
  • IIS部署 .net项目
  • 新华三ACG身份验证实验
  • Linux操作系统之线程（三）
  • JavaScript基础语法和简单数据结构
  • 响应式单位rpx及搭配使用UI产品工具
  • Java-Lambda表达式
  • Ceph存储阈值调整：优化nearfull_ratio参数
  • Vue组件化开发小案例
  • lvs 集群技术
  • LVS技术知识详解（知识点+相关实验部署）
  • sql练习二
  • MySQL练习3
  • Linux内核设计与实现 - 第6章 内核数据结构
  • [AI风堇]基于ChatGPT3.5+科大讯飞录音转文字API+GPT-SOVITS的模拟情感实时语音对话项目
  • 一动一静皆消耗——IC设计之低功耗技术(Low Power Design)
  • Linux C 信号操作
  • 单稳态触发器Multisim电路仿真——硬件工程师笔记
  • CS231n-2017 Lecture3线性分类器、最优化笔记
  • 深度解析 rag-vector-agent-semantic-kernel：基于 Semantic Kernel 的 Agentic RAG 实践
  • 关于Vuex
  • web.m3u8流媒体视频处理
  • 巧用Callbre RVE生成DRC HTML report及CTO的使用方法
  • Js中var VS let VS const
  • 关于饥饿加载（Eager Loading）
  • 解锁C++性能密码：TCMalloc深度剖析
  • 4 ASPICE的支持过程