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

红黑树的平衡之舞：数据结构中的优雅艺术

article 2024/11/14 17:17:10

在这里插入图片描述

文章目录

  • 前言
    • 🚀一、红黑树的介绍
      • 1.1 红黑树的概念
      • 1.2 红黑树的特点
      • 1.3 红黑树的性质
    • 🚀二、红黑树结点的定义
    • 🚀三、红黑树的框架
    • 🚀四、旋转操作
    • 🚀五、红黑树的插入操作
      • 5.1 `uncle`结点存在且为红
      • 5.2 `uncle`结点不存在或者存在且为黑
      • 5.3 插入操作的全部代码
      • 5.4 测试插入
    • 🚀六、AVL树和红黑树的性能比较
      • 6.1 平衡性
      • 6.2 查找操作
      • 6.3 插入和删除操作
      • 6.4 内存使用
      • 6.5 使用场景
  • 结语

前言

继上篇在平衡中追寻高度：探秘AVL树的自我调节之美，我们继续讨论红黑树的相关知识。
在计算机科学的广阔天地中，数据结构如同乐器，各具特色，共同奏响高效算法的乐章。在众多自平衡树中，红黑树以其独特的结构与高效的性能，成为了实现平衡的典范。本博文将深入探讨红黑树的原理、特点及其在实际应用中的表现，揭示这一数据结构如何在动态数据操作中保持高效与稳定。

🚀一、红黑树的介绍

1.1 红黑树的概念

红黑树是一种自平衡的二叉搜索树，其中每个节点都被标记为红色或黑色。通过这些颜色标记以及特定的规则，红黑树能够在插入和删除节点时保持平衡，从而确保基本操作的效率。

1.2 红黑树的特点

  1. 节点颜色：每个节点可以是红色或黑色。
  2. 根节点：树的根节点始终是黑色。
  3. 叶子节点：所有叶子节点（空节点）都是黑色。
  4. 红色节点限制：任何红色节点的子节点必须是黑色，避免连续的红色节点。
  5. 黑色高度：从任何节点到其每个叶子节点的所有路径都必须包含相同数量的黑色节点。
    在这里插入图片描述

1.3 红黑树的性质

  1. 接近平衡：红黑树保证了从根到叶子节点的最长路径不会超过最短路径的两倍，因此树是接近平衡的。
  2. 时间复杂度：
    • 查找：O(log n)
    • 插入：O(log n)
    • 删除：O(log n)
  3. 自平衡：在插入和删除操作后，红黑树通过旋转和重新着色来保持上述性质，从而确保树的高度尽量低。

这些特性使得红黑树在需要动态数据存储和高效查找的应用中非常有用，比如标准库中的std::map和std::set。

🚀二、红黑树结点的定义

template<class K, class V>
class RBTreeNode {
public:
	RBTreeNode<K, V>* left;
	RBTreeNode<K, V>* right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv; //结点中存的键值对
	color _col;		//结点的颜色

	RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED)
		:_kv(kv)
		,left(nullptr)
		,right(nullptr)
		,_parent(nullptr)
		,_col(color)
	{}
	
};
  • 新节点默认颜色是RED。这是因为，如果新插入结点的颜色是BLACK，那意味着当前路径上新增了一个黑色结点，为了保证红黑树的第5条性质，我们要对这颗红黑树其他的所有路径进行检查，可见新插入结点如果默认是BLACK，会存在着牵一发而动全身的影响。而让新插入结点默认是RED则不会出现这样的结果。假如新插入结点的 parent 恰好是 BLACK，那这次插入就没有什么问题。如果新插入结点是 parent 是 RED，此时需要对这颗红黑树稍作调整。

🚀三、红黑树的框架

template<class K, class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;
public:
    // 成员函数...    
private:
	Node* _root;
};

🚀四、旋转操作

  • 这里我们只举例2种情况，一种是左单旋，另一种是右单旋，另外两种双旋可以观看我的前文。
// 左单旋
void RotateL(Node* parent) {
	Node* cur = parent->right;
	Node* curleft = cur->left;

	parent->right = curleft;	
	cur->left = parent;

	if (curleft) curleft->_parent = 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) {
	Node* cur = parent->left;
	Node* curright = cur->right;

	parent->left = curright;
	cur->right = parent;

	if (curright) curright->_parent = 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;
	}
}

🚀五、红黑树的插入操作

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

  • 按照二叉搜索树的规则插入结点。

  • 检测新节点插入后，红黑树的性质是否遭到破坏。

因为新结点的默认颜色是 RED，因此：如果其双亲结点的颜色是 BLACK，没有违反红黑树任何性质，则不需要调整；但是当新插入节点的双亲结点颜色为 RED 时，就违反了性质四不能有连在一起的红色结点，此时需要对红黑树分情况来讨论：

约定：cur为当前结点，parent 为父结点，grandfather 为祖父结点，uncle 为叔叔结点。如果 parent 为红那 grandfather 一定为黑。所以当前唯一不确定的就是 uncle，主要分以下三种情况：

5.1 uncle结点存在且为红

  1. 由于每条路径上的黑色结点的时候，连带着uncle和grandfather结点也要一起更新。
  2. 根据规则，红色结点不能连续，故需要往上继续更新。
    在这里插入图片描述
    在这里插入图片描述

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

5.2 uncle结点不存在或者存在且为黑

在这里插入图片描述

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

5.3 插入操作的全部代码

bool insert(const pr& kv) {
	if (!_root) {
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}

	// 定义当前节点cur
	Node* cur = _root;
	Node* parent = nullptr;
	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; // 不可能出现相等的情况插入
	}

	// 创建新的Node实例cur，并将它插入到适当的位置
	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;
		// 父亲是祖父的左孩子
		if (grandfather->left == parent) {
			// 叔叔存在且为红
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				
				//继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			// 叔叔不存在或者存在且为黑
			else {
				if (cur == parent->left) {
					RotateR(grandparent);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else {
					RotateL(cur);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
		// 父亲是祖父的右孩子
		else {
			// 叔叔存在且为红
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续向上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			// 叔叔不存在或者存在且为黑
			else {
				if (cur == parent->right) {
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else {
					RotateR(cur);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
	}

	return true;
}

5.4 测试插入

红黑树的检测分为两步：

  • 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
  • 检测其是否满足红黑树的性质（主要是性质四和性质五）。

成员函数：

// 调用判断平衡的函数
bool IsBalance() {
	return IsBalance(_root);
}

// 判断平衡
bool IsBalance(Node* root) {
	if (!root) 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 CheckColor(root, 0, benchmark);
}

// 主要检查有无连续的红色结点
bool CheckColor(Node* root, int blacknum, int benchmark) {
	if (!root) {
		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 CheckColor(root->left, blacknum, benchmark) && CheckColor(root->right, blacknum, benchmark);
}

// 调用中序遍历
void InOrder() {
	return InOrder(_root);
}

// 中序遍历
void InOrder(Node* root) {
	if (!root) return;

	InOrder(root->left);
	cout << root->_kv.first << " ";
	InOrder(root->right);
}

测试代码：

#include "RBTree.h"

int main() {
	int a[] = { 1, 5, 7, 16, 25, 36, 44, 55,6, 32, 9 };
	RBTree<int, int> rbt;
	for (auto e : a) {
		rbt.insert(make_pair(e,e));
		rbt.InOrder();
		cout << endl;
		if (rbt.IsBalance()) {
			cout << "插入成功" << endl;
		}
		else {
			cout << "插入失败" << endl;
		}
	}

	return 0;
}

在这里插入图片描述

🚀六、AVL树和红黑树的性能比较

AVL树和红黑树是两种常用的自平衡二叉搜索树，各有优缺点。以下是它们在性能方面的比较：

6.1 平衡性

  • AVL树：始终保持严格平衡，任何节点的两个子树高度差不超过1。这使得AVL树在查找操作时的高度更小，查找速度较快。
  • 红黑树：相对宽松的平衡条件，通过颜色属性和旋转操作维护平衡。虽然高度比AVL树大，但仍然保持在O(log n)的范围内。

6.2 查找操作

  • AVL树：查找操作效率更高，时间复杂度为O(log n)，因为树的高度较小。
  • 红黑树：查找操作的时间复杂度同样为O(log n)，但由于可能较高的树高度，平均查找速度稍慢。

6.3 插入和删除操作

  • AVL树：插入和删除后，树可能需要更多的旋转来恢复平衡，因此插入和删除的时间复杂度为O(log n)，但常数因子较高。
  • 红黑树：插入和删除操作相对简单，所需的旋转次数较少，性能上通常更快，时间复杂度为O(log n)。

6.4 内存使用

  • AVL树：每个节点需要存储额外的平衡因子，内存开销相对较大。
  • 红黑树：每个节点需要存储颜色信息，内存开销相对较小。

6.5 使用场景

  • AVL树：适用于需要频繁查找操作的场景，如数据库索引等。
  • 红黑树：适用于插入和删除操作较为频繁的场景，如 STL 中的 std::map 和 std::set 实现。

总结

  • AVL树更适合查找频繁的场合，提供较快的查找速度。
  • 红黑树则在插入和删除性能上表现更好，适合对这些操作有较高频率的场景。

结语

红黑树不仅是一种数据结构，更是一种智慧的象征。它巧妙地平衡了插入、删除与查找操作之间的矛盾，为开发者在处理复杂数据时提供了强大的支持。通过对红黑树的深入理解，我们不仅能提升自身的编程能力，更能在数据处理的艺术中，找到更为优雅的解决方案。希望本篇博文能够为你在数据结构的探索之路上，带来新的启发与思考。
在这里插入图片描述

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！

在这里插入图片描述


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

相关文章：

  • WPF学习之路，控件的只读、是否可以、是否可见属性控制
  • 【Webpack实用指南】如何拆分CSS资源（2）
  • NoSQL数据库与关系型数据库的主要区别
  • 万字长文分析函数式编程
  • Matlab: 生成对抗网络，使用Datastore结构输入mat格式数据
  • 低代码集成多方API的简单实现
  • Linux进程信号（信号的产生）
  • 你对安装在自己网站上的wordpress插件了解吗?
  • 【C语言】浮点型数据存储 和 整型数据存储的区别
  • 基于深度学习的路面裂缝检测算法matlab仿真
  • C#-运算符重载
  • Redis运行时的10大重要指标
  • 1688拿货经验分享：亚马逊中小卖家如何选合作厂家
  • JS面试题之---解释一下什么是闭包？
  • 【日常经验】RPC 调用的分类及示例
  • 非关系型数据库NoSQL的类型与优缺点对比
  • API接口精准获取商品详情信息案例
  • 【前端】Svelte：响应性声明
  • 动态规划（二）——路径问题
  • Android13 系统/用户证书安装相关分析总结(三) 增加安装系统证书的接口遇到的问题和坑
  • VScode配置C、C++环境，编译并运行并调试
  • Java之List常见用法
  • VUE3实现好看的通用网站源码模板
  • 深度学习经典模型之VGGNet
  • ＜＜零基础C++第一期，C++入门基础之引用知识点＞＞
  • JavaWeb--Maven