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

发布于：2025-07-20 ⋅ 阅读:(19) ⋅ 点赞:(0)

目录

一、红黑树概述

二、红黑树节点设计

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

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

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布