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

数据结构——红黑树

article 2025/1/10 18:55:05

一、红黑树

1.红黑树的概念

        红黑树是一种二叉搜索树，但在其每个节点上增加了一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是近似平衡的。

2.红黑树的性质★

（1）每个节点不是红色就是黑色；

（2）根节点是黑色的；

（3）如果一个节点是红色的，则它的两个孩子节点是黑色的（即不存在两个相连的红色节点）；

（4）对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点；

（5）每个叶子节点都是黑色的（此处的叶子节点指的是空节点）。

3.红黑树节点的定义

enum Color{RED, BLACK};//节点颜色

//约定value唯一
template<class T>
struct RBTreeNode {//节点定义
	RBTreeNode(const T& value = T(), Color color = RED)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _value(value)
		, _color(color)
	{}
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _value;
	Color _color;
};

注意：节点颜色默认给红色

4.红黑树的结构

        为了方便后续实现关联式容器，在红黑树的实现中加入一个头结点，因为根节点必须是黑色，为了与根节点进行区分，将头节点给定为红色，让根节点的_parent指针域指向头节点，，并且让头结点的_parent指针域指向红黑树根节点，_left指针域指向红黑树中最左侧节点，_right指针域指向红黑树中最右侧节点：

  

二、红黑树的操作

1.红黑树的插入

        红黑树是在二叉搜索树的基础上加入了平衡限制条件，因此红黑树的插入可分为两步：

（1）按照二叉搜索树的方式进行插入新节点。

（2）检测新节点插入后，红黑树的性质是否被破坏：

        因为新节点的默认颜色是红色，因此，若其双亲节点是黑色，则没有违法红黑树任何性质，此时不需要调整；若其双亲节点是红色，则违法了性质三不能有两个连在一起的红节点，此时就需要进行调整，调整需要分情况讨论：

约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1.1 情况一

cur红，p红，g黑，u存在且为红

注意：此树可能是一棵完整的树，也可能是一棵子树。abcde可能为空，也可能是节点。

解决方法：

        将p、u改为黑色，g改为红色，然后把g当成cur，若g是根节点则改回黑色，否则继续向上调整。

1.2 情况二

cur红，p红，g黑，u不存在/u黑

u的情况有两种：

（1）u节点不存在：则cur一定是新插入的节点，可根据性质判断出。

（2）u节点存在：则其一定是黑色，cur原先的颜色也一定是黑色，是由于cur子树的节点在调整时被调整成了红色，同样是可以根据性质判断出。

解决方法：

①p为g的左孩子，cur为p的左孩子，则进行右单旋；如图左

②p为g的右孩子，cur为p的右孩子，则进行左单旋；图左的对称图

③p改为黑色，g改为红色。

1.3 情况三

cur红，p红，g黑，u不存在/u黑

 解决方法：

①p为g的左孩子，cur为p的右孩子，则针对p进行左单旋；如图

②p为g的右孩子，cur为p的左孩子，则针对p进行右单选；图为上图的对称图

③旋转后，如图就变成了情况二，再按照情况二进行调整即可。

2.红黑树的验证

红黑树的验证分为两步：

（1）验证其是否满足二叉搜索树，即中序遍历是否为有序序列。

（2）验证其是否满足红黑树的性质。

三、红黑树实现

1.代码实现


enum Color{RED, BLACK};//节点颜色

template<class T>
struct RBTreeNode {//节点定义
	RBTreeNode(const T& value = T(), Color color = RED)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _value(value)
		, _color(color)
	{}
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _value;
	Color _color;
};

//约定value唯一
template<class T>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	RBTree() {
		_head = new Node();
		_head->_left = _head;
		_head->_right = _head;
	}
	~RBTree() {
		Destroy(_head->_parent);
		delete _head;
		_head = nullptr;
	}

	//插入
	bool Insert(const T& value) {
		Node*& root = GetRoot();
		//1.按照二叉搜索树的方式插入
		if (root == nullptr) {//空树
			root = new Node(value, BLACK);
			root->_parent = _head;
			_head->_left = root;
			_head->_right = root;
			return true;
		}
		//查找插入位置
		Node* cur = root;
		Node* parent = cur->_parent;
		while (cur) {
			parent = cur;//保存其双亲
			if (value < cur->_value) {
				cur = cur->_left;
			}
			else if (value > cur->_value) {
				cur = cur->_right;
			}
			else {//已存在
				return false;
			}
		}
		//插入新节点
		cur = new Node(value);//默认插入节点为红色
		if (value < parent->_value) {
			parent->_left = cur;
		}
		else {
			parent->_right = cur;
		}
		cur->_parent = parent;
		//2.红黑树性质约束
		while (parent != _head && parent->_color == RED) {//两个红色相连违法规则
			Node* grandFather = parent->_parent;
			if (parent == grandFather->_left) {
				Node* uncle = grandFather->_right;
				//情况一：叔叔节点存在且为红
				if (uncle && uncle->_color == RED) {
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandFather->_color = RED;
					//改变cur，继续向上调整
					cur = grandFather;
					parent = cur->_parent;
				}
				else {//情况二或三：叔叔节点为空，或叔叔节点存在且为黑
					//因为情况三可以调整为情况二，所有先处理情况三
					if (cur == parent->_right) {
						//将情况三转换为情况二
						RotateLeft(parent);
						std::swap(parent, cur);
					}
					//情况二
					parent->_color = BLACK;
					grandFather->_color = RED;
					RotateRight(grandFather);
				}
			}
			else {//三种情况的对称情况-->解决方法相同
				Node* uncle = grandFather->_left;
				if (uncle && uncle->_color == RED) {//情况一
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandFather->_color = RED;
					//改变cur，继续向上调整
					cur = grandFather;
					parent = cur->_parent;
				}
				else {//情况二或三
					if (cur == parent->_left) {//情况三
						//调整为情况二
						RotateRight(parent);
						std::swap(cur, parent);
					}
					//情况二
					parent->_color = BLACK;
					grandFather->_color = RED;
					RotateLeft(grandFather);
				}

			}
		}
		//注意：最后根节点可能被调整为了红色，所以需要被改回黑色
		root->_color = BLACK;

		//3.更新头结点左右指针域--插入元素可能改变树的最值
		_head->_left = MostLeft();
		_head->_right = MostRight();
		return true;
	}

	//查找
	Node* Find(const T& value) {
		Node*& root = GetRoot();
		if (root == nullptr) return nullptr;
		Node* cur = root;
		while (cur) {
			if (value < cur->_value) {
				cur = cur->_left;
			}
			else if (value > cur->_value) {
				cur = cur->_right;
			}
			else {
				return cur;
			}
		}
		return nullptr;
	}

	//检测是否是红黑树
	bool IsRBTree() {
		Node* root = GetRoot();
		if (root == nullptr) return true;
		if (root->_color == RED) {
			//检测性质2
			std::cout << "FALSE: 根节点为红色！" << std::endl;
			return false;
		}
		int blackCount = 0;
		Node* cur = root;
		while (cur) {//统计一条路径黑色节点个数
			if (cur->_color == BLACK) ++blackCount;
			cur = cur->_left;
		}
		return _IsRBTree(root, blackCount, 0);
	}

	//中序遍历
	void InOrder() {
		_InOrder(GetRoot());
		std::cout << std::endl;
	}
	//获取最值
	int GetMax() {
		return MostRight()->_value;
	}
	int GetMin() {
		return MostLeft()->_value;
	}

private:
	//获取根节点
	Node*& GetRoot() {
		return _head->_parent;
	}
	//获取树的最值节点
	Node* MostLeft() {//最左侧节点
		Node*& root = GetRoot();
		if (root == nullptr) return _head;
		Node* cur = root;
		while (cur->_left) {
			cur = cur->_left;
		}
		return cur;
	}
	Node* MostRight() {//最右侧节点
		Node*& root = GetRoot();
		if (root == nullptr) return _head;
		Node* cur = root;
		while (cur->_right) {
			cur = cur->_right;
		}
		return cur;
	}
	//左单旋
	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) {//注意subrl可能为空
			subRL->_parent = parent;
		}
		subR->_left = parent;
		//跟新parent和subR的双亲节点
		//先保存好parent原先的双亲节点
		Node* pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;
		//处理上层节点
		if (pparent == _head) {//已经更新到根节点
			_head->_parent = subR;
		}
		else {
			if (parent == pparent->_left) {
				pparent->_left = subR;
			}
			else {
				pparent->_right = subR;
			}
		}
	}
	//右单旋
	void RotateRight(Node* parent) {
		//其思想与左单旋相同
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) {
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* pparent = parent->_parent;
		parent->_parent = subL;
		subL->_parent = pparent;
		if (pparent == _head) {
			_head->_parent = subL;
		}
		else {
			if (parent == pparent->_left) {
				pparent->_left = subL;
			}
			else {
				pparent->_right = subL;
			}
		}
	}
	//检测是否满足红黑树特性
	bool _IsRBTree(Node* root, const int blackNum, int count) {
		if (root == nullptr) return true;
		if (root->_color == BLACK) ++count;//统计路径内的黑色节点
		//检测是否满足性质3
		if (root->_parent != _head && root->_color == RED && root->_parent->_color == RED) {
			std::cout << "FALSE: 存在两个相连的红色节点！" << std::endl;
			return false;
		}
		if (root->_left == nullptr && root->_right == nullptr) {
			//是叶子节点，此路径统计结束
			return count == blackNum;//检测性质4
		}
		return _IsRBTree(root->_left, blackNum, count) && _IsRBTree(root->_right, blackNum, count);
	}
	//中序遍历
	void _InOrder(Node*& root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		std::cout << root->_value << " ";
		_InOrder(root->_right);
	}
	//销毁
	void Destroy(Node* root) {
		if (root == nullptr) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
private:
	Node* _head;
};

2.红黑树与AVL树的比较

        红黑树与AVL树都是高效的平衡二叉树，增删改查时间复杂度都是O(log_{2}^{N})，红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的两倍即可，相对而言，降低了插入和旋转的次数，所以经常在增删改查的结构中性别比AVL树更好，且红黑树的实现相对来说更简单，实际运用中也更多。


http://www.kler.cn/a/5231.html

相关文章：

  • Spring 项目 基于 Tomcat容器进行部署
  • 【马来西亚理工大学主办，ACM出版】2025年大数据、通信技术与计算机应用国际学术会议（BDCTA 2025)
  • 【Leetcode 热题 100】20. 有效的括号
  • Selenium 的四种等待方式及使用场景
  • 【linux系统之redis6】redisTemplate的使用方法
  • MCU 和 PSK
  • 亚马逊流量密码-优化listing的跳出率
  • 2023年非业绩亏损ST股票投资策略研究报告
  • 《程序员面试金典（第6版）》面试题 08.04. 幂集（回溯算法，位运算，C++）不断更新
  • 王爽-汇编语言第二版学习-day1
  • 最强绘图AI：一文搞定Midjourney（附送咒语）
  • MybatisPlus简讲 -- 狂神说JAVA版
  • gpt2中文训练教程-gpt2文本生成
  • 传感器实验讲解1
  • HarmonyOS/OpenHarmony应用开发-HUAWEI DevEco Studio 3.1API9集成SDK
  • 项目一：挑战6秒
  • 你看这个spring的aop它又大又宽
  • Node.js学习笔记——HTTP协议
  • 电脑微博批量删除-2023怎么批量删除微博网页版代码
  • OPNET Modeler 例程——创建一个包交换网络
  • Web前端学习：章四 -- JavaScript初级（六-七）
  • DBeaver连接达梦DM数据库及配置
  • 小黑仿生轮腿机器人（一）-本体说明及运动控制
  • 第08章_聚合函数
  • 【20230401】【每日一题】前K个高频元素
  • Springboot 多线程分批切割处理 大数据量List集合 ，实用示例