【C++高阶四】红黑树

1.什么是红黑树

上篇博客学习了平衡二叉搜索树(AVLTree)，了解到AVL树的性质，二叉搜索树因为其独特的结构，查找、插入和删除在平均和最坏情况下时间复杂度都是O(logn)。
但在AVL树中插入或删除节点时，高度差绝对值大于1，平衡被破坏，为了重新维持其稳定，要进行旋转处理，但因为每个结点的高度差的绝对值都要小于1这个条件较为的严格，导致多数情况的插入和删除都需要旋转调整，导致插入和删除的效率降低
红黑树应运而生，并且因为其接近平衡的结构，使其查找效率十分高效，也没有像AVL树那样的严格要求，所以其插入和删除效率有时还优于AVL树

红黑树，是一种二叉搜索树，每个结点上增加一个存储位表示结点的颜色（红色或黑色），通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保最长路径不超过最短路径的二倍，因此接近平衡
在这里插入图片描述
红黑树保持接近平衡是依靠以下几个规则：

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个结点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该节点到其后代叶子结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的（此处的叶子结点指的是空结点）

由规则三可知：红黑树中没有连续的红色结点
由规则四可知：每一条路径都包含相同数目的黑色节点

2.红黑树的效率

红黑树的最短路径：全黑
红黑树的最长路径：一黑一红，红黑相间
假设总共有N个结点
那么最短路径就是以2为底的logN
最长路径就是2logN
而AVL树的查找效率是logN，和2logN差距并不大
但是红黑树的调整没有AVL树频繁，所以综合效率红黑树更胜一筹
在这里插入图片描述

像这样一棵树，如果是AVL树，则右边高度比左边高2，需要旋转，但是符合红黑树的条件，不用旋转

3.红黑树的实现

3.1框架搭建

enum color//颜色枚举
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode//节点结构体
{
	RBTreeNode<K, V>* _left;//左指针
	RBTreeNode<K, V>* _right;//右指针
	RBTreeNode<K, V>* _parent;//父亲指针
	color _color;//颜色标记位
	pair<K, V> _KV;//KV值

	RBTreeNode(const pair<K, V>& KV)//初始化列表构造
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _KV(KV)
		, _color(RED)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;//简称节点为Node
private:
	Node* _root = nullptr;
};

3.2 插入操作

和AVL树很相似，红黑树的插入也是分为两步：

  1. 按照二叉搜索树的规则插入值
  2. 插入后根据颜色或高度做旋转或变色

第一步可以将之前AVL的代码抄过来

bool insert(const pair<K, V>& kv)//按照二叉搜索树的方式插入值
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;//根节点是黑的
		return true;
	}
	
	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;//相等就插入失败
	}
	cur = new Node(kv);
	//链接
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;
	//此时new出来的节点的parent还指向空
	cur->_parent = parent;
}

新插入的节点是选择插入红色还是黑色？有两个选择：

  1. 插入黑色节点，打破规则四，要检查每个路径
  2. 插入红色节点，打破规则三，只用看父亲是否为红

因此新插入的节点是选择成为红色是更优选择

3.2.1插入情况一

在这里插入图片描述
cur是新增红色结点，因为parent是黑色父节点，符合所有规则，插入完成

3.2.2插入情况二：uncle节点是红色的

在这里插入图片描述
cur是新增红色结点28，因为parent是红色父节点30，插入28后导致连续的红色节点，违反规则三。
我们在处理时也要考虑规则四：每个路径的黑色结点的个数相同。
为了同时满足规则三和规则四，我们要改变结点颜色的同时，路径上的黑色结点个数还要相同：细致改变颜色向上更新，到达两个路径的公共节点，再改变公共结点的颜色

在情况二例子中的具体操作：当存在红色的uncle节点时，将uncle和parent节点的颜色都变为黑色，再将grandfather节点变为红色
在这里插入图片描述
如果grandfather是根节点，再将grandfather结点变成黑色
在这里插入图片描述

如果grandfather不是根节点且红黑树的节点数量更多呢？
在这里插入图片描述
28为新增红色节点，同样使用上述方法调节颜色
在这里插入图片描述
以25为根结点的子树完成了调整，但这只是完成了一颗子树，所以还需要继续向上调整

在这里插入图片描述
这时新的parent有两种情况：

  1. parent结点为黑色，调整结束
  2. parent结点为红色，继续调整

此处parent结点是红色，所以我们还需继续调整

在这里插入图片描述
在这里插入图片描述
这就是情况二：新插入结点的父亲结点是红色的，uncle结点存在且为红的情况下，将parent和uncle都变黑，grandfather变红，若grandfather不为根还需要继续向上更新，若grandfather为根就将其变成黑色

3.2.3插入情况三：没有uncle结点

在这里插入图片描述
在5的右边新增结点，此时没有uncle结点，不是情况二
通过观察发现，这棵树的高度很不均衡，我们可以采用旋转的方式降低这棵树的高度
使用左单旋：
在这里插入图片描述
没有破坏二叉搜索树的结构的情况下降低了树的高度，但仍然不满足红黑树，继续调整颜色：将grandfather变红，parent变黑
在这里插入图片描述
当情况三出现在子树部分也可以完美符合规则
在这里插入图片描述

旋转变色后：整棵树也符合规则
在这里插入图片描述

当grandfather、parent和cur线性排列时使用单旋
在这里插入图片描述
当grandfather、parent和cur折线排列时使用双旋
在这里插入图片描述

3.2.4插入情况四：uncle节点是黑色的

在这里插入图片描述
插入19红色节点并调整颜色后，继续向上调整：
在这里插入图片描述

parent是红色，但是uncle却是黑色
因为grandfather、parent和cur呈折线排列，所以使用双旋
左右双旋：先左单旋，后右单旋
在这里插入图片描述
旋转结束后调整颜色：cur变成黑色，grandfather变成红色
在这里插入图片描述

无论哪种情况的旋转，看是线性还是折线，线性使用单旋，折线型使用双旋

4.完整代码

#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

enum color//颜色枚举
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode//节点结构体
{
	RBTreeNode<K, V>* _left;//左指针
	RBTreeNode<K, V>* _right;//右指针
	RBTreeNode<K, V>* _parent;//父亲指针
	color _color;//颜色标记位
	pair<K, V> _kv;//KV值

	RBTreeNode(const pair<K, V>& KV)//初始化列表构造
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(KV)
		, _color(RED)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;//定义节点为Node
public:
	bool Insert(const pair<k, v>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_color = BLACK;//根节点是黑的
			return true;
		}

		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;//相等就插入失败
			}
		}

		cur = new Node(kv);
		//链接
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		//此时new出来的节点的parent还指向空
		cur->_parent = parent;

		//新插入节点的父亲 存在 且是 红色,再调整
		while (parent && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;
			
			if (parent == grandfather->_left)//新插入的节点其父节点在子树左侧
			{
				Node* uncle = grandfather->_right;
				
				if (uncle && uncle->_color == RED)//uncle存在且为红
				{
					uncle->_color = parent->_color = BLACK;
					grandfather->color = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//uncle不存在 或uncle是黑色
				{
					if (cur = parent->left)//grandfather和parent和cur是线性
					{
						RotateR(grandfather);
						grandfather->color = RED;
						parent->color = BLACK;
					}
					else//grandfather和parent和cur是折线型
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->color = BLACK;
						grandfather->_color = RED;
					}

					break;//旋转后一定满足要求，跳出循环
				}
			}
			else//新插入的节点其父节点在子树右侧
			{
				Node* uncle = grandfather->_left;

				if (uncle && uncle->_color == RED)//uncle 存在 且为 红色
				{
					uncle->_color = parent->_color = BLACK;
					grandfather->color = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//uncle 不存在 或为 黑色
				{
					if (cur = parent->right)//grandfather和parent和cur是线性
					{
						RotateL(grandfather);
						grandfather->color = RED;
						parent->color = BLACK;
					}
					else//grandfather和parent和cur是折线型
					{
						RotateR(parent);
						RotateL(grandfather);

						cur->color = BLACK;
						grandfather->_color = RED;
					}

					break;//旋转后一定满足要求，跳出循环
				}
			}
		}
		_root->color = BLACK;
		return true;
	}

	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_ + left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* parentparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentparent->_left = parent)
			{
				parentparent->_left = subR;
			}
			else
			{
				parentparent->_right = subR;
			}
			subR->_parent = parentparent;
		}
		subR->_bf = parent->_bf = 0;
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		subL->_bf = parent->_bf = 0;
	}
	
	size_t size()
	{
		return _size(_root);
	}

	size_t _size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _size(root->left) + _size(root->right) + 1;
	}

	Node* find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if(cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	void InOrder()//中序
	{
		_InOrder(_root);
	}

	int Height()
	{
		return _Height(_root);
	}
private:
	void _InOrder(Node* root)//中序
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return max(_Height(root->left), _Height(root->right) + 1);
	}

	Node* _root = nullptr;
};
# c++ # 算法
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

远程 MCP 项目实战：LangChain 连接高德地图、Chrome DevTools 与文件系统

avatar AI Agent技术社区
cover

企业 AI Agent 的真正门槛，不是模型能力，而是工作底座

avatar AI Agent技术社区
cover

字节跳动开源AI Agent「上下文数据库」，2.6万星，比传统RAG好用太多了

avatar AI Agent技术社区