C++之红黑树

不会就选b

782人浏览 · 2026-05-13 18:12:59

不会就选b · 2026-05-13 18:12:59 发布

红黑树的概念

红黑树是自平衡二叉搜索树，二叉搜索树 (BST) 基础上，通过节点染色（红 / 黑）+ 5 条规则自动维持平衡，最长路径不超过最短路径的 2 倍，保证增删查时间复杂度稳定 O(log n)。
特点

每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的
红色结点。
对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

红黑树的实现

红黑树的结构

在这里插入图片描述

template <class K,class V>
struct AVLNode
{
	pair<K, V> _kv;
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;
	int _bf;
	
	AVLNode(const pair<K, V> kv)
		:_kv(kv)
		,_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		, _bf(0)
	{ }
	
};

template <class K, class V>
class AVLTree
{
	typedef AVLNode<K,V> Node;

public:

private:
	Node* _root = nullptr;
};

红黑树的插入

基本原理和二叉树相类似，但是还要控制颜色和旋转
我们先来思考一个问题插入的节点应该是什么颜色的节点？
应该是红色，因为插入黑色节点，条件四很难调控。

前提要求：
新节点默认是红色（为了尽量不破坏 “黑高” 规则）
只有当父节点也是红色时，才会触发冲突（连续红节点），需要修复。
此时爷爷节点一定是黑色，叔叔节点（父的兄弟）分三种情况。

1.uncle为红
此时需要只需要变颜色
parent和uncle变黑
grandparent变红
发现grandparent的父亲是红色，我们任然要向上遍历。
cur=grandparent
parent=cur->_parent

在这里插入图片描述

2.uncle为黑
此时单单依靠变色以及难以解决，我们还要旋转。
1.以grandparent为节点进行左旋
2.parent变黑，grandparent变红

在这里插入图片描述

3.uncle不存在

1.以grandparent为节点左旋
2.将parent变黑，grandparent比红
在这里插入图片描述
从上面的观察我们可以将其分为两类

uncle	操作
存在为红	变色
存在为黑,或者不存在	变色加旋转

颜色逻辑

通过观察我们需要将旋转过后最顶上节点的颜色变成黑色，而从原来顶上换下里的节点grandparent的颜色变为红。

保证「黑高不变」，不破坏整棵树的平衡
1.红黑树最关键的约束之一是：从任意节点到所有叶子的路径，黑色节点数量（黑高）必须相同。
2.原来的 grandparent 是黑色，它在的路径黑高里，贡献了 1 个黑色节点。
旋转后，parent或者cur（双旋）变成了黑色，相当于在原来的位置补上了这个黑色节点，路径的黑高没有变化。
3.被换下来的 grandparent 变成红色，它的子路径（包括原来的叔叔分支）的黑高也不会变，因为它的位置下移，不会再影响上层路径的黑高计数。

旋转逻辑

parent在grandparent左侧	操作
cur在parent右	1.以parent为轴进行左单旋2.以grandparent为轴进行右单旋
cur在parent左	1.以parent为轴进行右单旋

parent在grandparent右侧	操作
cur在parent右	1.以parent为轴进行左单旋
cur在parent左	1.以parent为轴进行做右单旋2.以grandparent为轴进行左单旋

在这里插入图片描述
代码实现

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 != nullptr)
		{
			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 (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;

		}
		cur->_parent = parent;
		cur->_color = RED;

		

		while (parent&&parent->_color==RED)
		{
			
			Node* grandparent = parent->_parent;
			if (grandparent->_left == parent)
			{
				//      g
				//   p      u
				// c
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_color == RED)//叔叔存在且为红色
				{
					parent->_color = uncle->_color = BLACK;
					grandparent->_color = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				
				else//叔叔不存在或者叔叔存在为黑色，此时要发生旋转和变色
				{//      g
				//   p      u
				// c
				//
					if (cur == parent->_left)
					{
						RotateR(grandparent);//旋转点就是要被压下去的点
						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else
					{//      g
					//   p      u
					//     c
					//
						RotateL(parent);
						RotateR(grandparent);
						cur->_color = BLACK;
						grandparent->_color = RED;
						
					}
					break;

				}

				

			}
			else//parent在grandparent->_right
			{
				Node* uncle = grandparent->_left;
				//      g
				//    u    p 
				//           c
				if (uncle && uncle->_color == RED)//需要变色即可
				{
					parent->_color = uncle->_color = BLACK;
					grandparent->_color = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else//叔叔不存在或者叔叔存在但是颜色为嘿
				{
					
					if (cur == parent->_right)
					{
					//      g
					//    u    p 
					//           c
						RotateL(grandparent);
						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else
					{
					//      g             c
					//    u    p      g       p
					//       c     u
						RotateR(parent);
						RotateL(grandparent);
						cur->_color= BLACK;
						grandparent->_color = RED;
					}
					break;
				}
				



			}

		

		}
		_root->_color = BLACK;
		return true;

		}

find

比较简单不多做介绍

bool find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first == key)
					return true;
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else
					cur = cur->_left;
			}
			return false;
		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else
					cur = cur->_left;
			}
			return nullptr;
		}

中序遍历

为了便于操作，我们用调用子函数的方法来实现

void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}

private:
void _Inorder(Node* root)
			{
				if (root == nullptr)
					return;
				_Inorder(root->_left);
				//cout << root->_kv.first << " "<< root->_kv.second<<endl;
				cout << root->_kv.first << " ";
				_Inorder(root->_right);

			}

检查平衡

1.先看根是不是黑色，不是直接不平衡
2.红色节点的左右孩子不能为红色,我们这里可以看cur和parent来验证，不然要先判断左右指针是否存在，然后看颜色。
3.计算最左路径黑高作为标准值
4.遍历所有其他路径，对比黑高，全部相等才平衡


bool IsBalenceTree()
		{
			if (_root == nullptr)
				return true;
			//反向验证,检查不满足
			if (_root->_color == RED)
				return false;
			Node* cur = _root;
			int blackRef = 0;
			while (cur)
			{
				if (cur->_color == BLACK)
					blackRef++;
				cur = cur->_left;
			}
			return _IsBalanceTree(_root,0,blackRef);
		}

private:
bool _IsBalanceTree(Node* root,int blackNum ,const int blackRef)
			{
				if (root == nullptr)
				{
					if (blackNum != blackRef)
					{
						return false;
					}
					 return true;
				}
				if (root->_parent&&root->_parent->_color == RED && root->_color == RED)
				{
					cout << root->_kv.first << "两个连续红色节点";
					return false;
				}
				if (root->_color == BLACK)
					blackNum++;

				return _IsBalanceTree(root->_left, blackNum,blackRef)
				        &&_IsBalanceTree(root->_right, blackNum,blackRef);

			}

实现size，height

int Height()
		{
			return _Height(_root);
		}
		int Size()
		{
			return _Size(_root);
		}

		private:

			int _Size(Node* root)
			{
				if (root == nullptr)
					return 0;
				return _Size(root->_left) + _Size(root->_right) + 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;

			}

在这里插入图片描述
红黑树是弱平衡二叉搜索树，靠节点红黑染色 + 5 条规则、左旋右旋 + 变色维持自平衡，保证最长路径≤最短路径 2 倍，增删查稳定 O (log n)。
红黑树改得快，查稍慢，弱平衡，适合频繁插入删除，工程里基本都用红黑树。

全部代码

RBTree.h

#pragma once
#include<iostream>
using namespace std;
namespace maomao
{
	enum Color
	{
		BLACK,RED
	};
	template <class K, class V>
	struct RBTreeNode
	{
		pair<K, V> _kv;
		RBTreeNode* _left;
		RBTreeNode* _right;
		RBTreeNode* _parent;
		Color _color;

		RBTreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _right(nullptr)
			, _left(nullptr)
			, _parent(nullptr)
			,_color(RED)
		{
		}

	};

	template <class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:

		RBTree()
			:_root(nullptr)
		{
		}


		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 != nullptr)
			{
				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 (cur->_kv.first < parent->_kv.first)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;

			}
			cur->_parent = parent;
			cur->_color = RED;

			

			while (parent&&parent->_color==RED)
			{
				
				Node* grandparent = parent->_parent;
				if (grandparent->_left == parent)
				{
					//      g
					//   p      u
					// c
					Node* uncle = grandparent->_right;
					if (uncle && uncle->_color == RED)//叔叔存在且为红色
					{
						parent->_color = uncle->_color = BLACK;
						grandparent->_color = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					
					else//叔叔不存在或者叔叔存在为黑色，此时要发生旋转和变色
					{//      g
					//   p      u
					// c
					//
						if (cur == parent->_left)
						{
							RotateR(grandparent);//旋转点就是要被压下去的点
							parent->_color = BLACK;
							grandparent->_color = RED;
						}
						else
						{//      g
						//   p      u
						//     c
						//
							RotateL(parent);
							RotateR(grandparent);
							cur->_color = BLACK;
							grandparent->_color = RED;
							
						}
						break;

					}

					

				}
				else//parent在grandparent->_right
				{
					Node* uncle = grandparent->_left;
					//      g
					//    u    p 
					//           c
					if (uncle && uncle->_color == RED)//需要变色即可
					{
						parent->_color = uncle->_color = BLACK;
						grandparent->_color = RED;
						cur = grandparent;
						parent = cur->_parent;
					}
					else//叔叔不存在或者叔叔存在但是颜色为嘿
					{
						
						if (cur == parent->_right)
						{
						//      g
						//    u    p 
						//           c
							RotateL(grandparent);
							parent->_color = BLACK;
							grandparent->_color = RED;
						}
						else
						{
						//      g             c
						//    u    p      g       p
						//       c     u
							RotateR(parent);
							RotateL(grandparent);
							cur->_color= BLACK;
							grandparent->_color = RED;
						}
						break;
					}
					



				}

			

			}
			_root->_color = BLACK;
			return true;

		}


		bool find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first == key)
					return true;
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else
					cur = cur->_left;
			}
			return false;
		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else
					cur = cur->_left;
			}
			return nullptr;
		}
		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}

		bool IsBalenceTree()
		{
			if (_root == nullptr)
				return true;
			//反向验证,检查不满足
			if (_root->_color == RED)
				return false;
			Node* cur = _root;
			int blackRef = 0;
			while (cur)
			{
				if (cur->_color == BLACK)
					blackRef++;
				cur = cur->_left;
			}
			return _IsBalanceTree(_root,0,blackRef);
		}
		int Height()
		{
			return _Height(_root);
		}
		int Size()
		{
			return _Size(_root);
		}

		private:

			int _Size(Node* root)
			{
				if (root == nullptr)
					return 0;
				return _Size(root->_left) + _Size(root->_right) + 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;

			}
			//判断路径上的黑色节点数量是否一致
			//采用根左右的遍历
			bool _IsBalanceTree(Node* root,int blackNum ,const int blackRef)
			{
				if (root == nullptr)
				{
					if (blackNum != blackRef)
					{
						return false;
					}
					 return true;
				}
				if (root->_parent&&root->_parent->_color == RED && root->_color == RED)
				{
					cout << root->_kv.first << "两个连续红色节点";
					return false;
				}
				if (root->_color == BLACK)
					blackNum++;

				return _IsBalanceTree(root->_left, blackNum,blackRef)
				        &&_IsBalanceTree(root->_right, blackNum,blackRef);

			}
			void _Inorder(Node* root)
			{
				if (root == nullptr)
					return;
				_Inorder(root->_left);
				//cout << root->_kv.first << " "<< root->_kv.second<<endl;
				cout << root->_kv.first << " ";
				_Inorder(root->_right);

			}
	

			void RotateR(Node* parent)
			{
				Node* subl = parent->_left;
				Node* sublr = subl->_right;
				Node* parentparent = parent->_parent;

				//处理左右指针
				//             pp                 pp
				//        p                              p
				//    l                                 l
				// ll   lr                                 lr


				//          l
				//      ll        p
				//            lr(lr可能不存在)

				parent->_left = sublr;
				subl->_right = parent;
				//parentparent的左右指针的处理
				if (parentparent)
				{
					if (parentparent->_left == parent)
					{
						parentparent->_left = subl;
					}
					else
					{
						parentparent->_right = subl;
					}
				}
				

				//_parent指针的处理
				if (sublr)
				{
					sublr->_parent = parent;
				}
				//parent不是根节点
				if (parent != _root)
				{
					subl->_parent = parentparent;
				}
				//parent为根节点
				else
				{
					subl->_parent = nullptr;
					_root = subl;
				}
				parent->_parent = subl;



			}

			void RotateL(Node* parent)
			{
				Node* subr = parent->_right;
				Node* subrl = subr->_left;
				Node* parentparent = parent->_parent;

				//处理左右指针
				// pp                                       pp
				//    p                                p
				//         r                               r
				//      rl         rr                   rl      rr      


				//          r
				//      p         rr
				//        rl(rl可能不存在)

				parent->_right = subrl;
				subr->_left = parent;
				//parentparent的左右指针的处理
				if (parentparent)
				{
					if (parentparent->_left == parent)
					{
						parentparent->_left = subr;
					}
					else
					{
						parentparent->_right = subr;
					}

				}
				
				//_parent指针的处理
				if (subrl)
				{
					subrl->_parent = parent;
				}
				//parent不是根节点
				if (parent != _root)
				{
					subr->_parent = parentparent;
				}
				//parent为根节点
				else
				{
					subr->_parent = nullptr;
					_root = subr;
				}
				parent->_parent = subr;



			}
			
			
	private:
		Node* _root;

	};
}

test.h

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
#include"BRTree.h"
using namespace maomao;
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	maomao::RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalenceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值
/*for (auto e : v)
{
t.Find(e);
}*/
// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}
int main()
{
	/*maomao::RBTree<string, string> t;
	t.Insert({ "cat","猫" });
	t.Insert({ "dog","狗" });

	t.Insert({ "apple","苹果" });
	t.Insert({ "pineapple","菠萝" });
	t.Insert({ "peach","桃子" });
	t.Inorder();
	int x=t.find("apple");
	cout << x;
	int y=t.IsBalenceTree();
	cout << y;*/
	TestAVLTree2();
	return 0;
}

亚马逊云科技技术品牌专区

更多推荐

【世界杯中的AI】（2026-07-04）三场生死战，AI成了预言家？揭晓“首届AI世界杯”最疯狂的24小时！

亚马逊云科技技术品牌专区

4-20mA/0-10V 通用模拟量采集电路

亚马逊云科技技术品牌专区

智能科学与技术毕业设计容易的方向怎么做

本文提供了人工智能方向毕业设计选题的全面指导。首先介绍了选题原则，强调要结合个人能力、兴趣、就业方向等因素。随后分享了8个实用的选题技巧，包括逆向思维、项目拆分、技术融合等方法。重点推荐了人工智能与机器学习方向的三大热点领域：智能推荐系统、计算机视觉应用和自然语言处理应用，并列举了20个具体课题。最后详细展示了4个基于YOLO算法的实际项目案例(焊接缺陷检测、血液细胞计数、脑瘤检测、葡萄采摘辅助系