前言

学完 AVL 树后，你是不是也有过这样的疑惑：明明 AVL 树是 “严格平衡” 的二叉搜索树，查询效率还更高，可为啥 C++ STL 的map/set、Linux 内核里的关键结构，偏偏选红黑树而不用它？难道 “更平衡” 反而成了缺点？

其实答案藏在 “工程取舍” 里 —— 红黑树的精髓，从来不是 “比 AVL 树更平衡”，而是 “在‘查询效率’和‘写入开销’之间找最优解”。它不像 AVL 树那样追求 “极致的矮”，而是用 “近似平衡”（最长路径不超过最短路径 2 倍）的规则，换来了插入删除时更少的旋转、更低的空间开销，刚好适配了工程里 “读写频繁、追求均衡性能” 的大多数场景。

这篇内容不绕弯子，直接从红黑树的 5 条核心性质讲起，拆透 “新节点为啥默认红色”“插入时 3 种情况怎么处理” 这些经典难点，再对比 AVL 树说清 “什么时候该选谁”，最后附上可运行的手撕代码和验证逻辑 —— 不管你是为了面试手撕，还是想搞懂工程里的平衡树选型，这篇都能让你把红黑树的本质嚼透。

红黑树的概念

概念:红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black

红黑树的长相例图

红黑树的性质

1.每个结点不是红色就是黑色

2.根节点是黑色的

3.任何路径没有连续的红节点

4.各路径黑节点的个数相同

5.每个叶子结点都是黑色的(此处的叶子结点指的是那个空结点)

这些性质让红黑树的最长路径长度不超过最短路径长度的2倍

–因为一红后面必会跟一黑,各路径黑节点的个数又是一样的

关于路径:从根节点到空节点算一条路径(默认是这样的)

路径长度这一块的话，空节点不算上，根节点要算上

红黑树增删查改的时间复杂度也是O(logN) --N是节点个数

空树也可以是红黑树

AVL树跟红黑树的比较

AVL树和红黑树的在查找时的性能是同一量级的

但是AVL的平衡的控制在插入和删除时的旋转使用的次数很多

所以红黑树比AVL树好些,但是其实也大差不差

AVL的话大量查找要优于红黑树 但是红黑树在各方面更加均衡一点

红黑树的模拟实现

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)
		{
			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
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // u不存在 或 存在且为黑
				{
					if (cur == parent->_left)
					{
                       //图:
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // 也就是parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						// g
						//	  p
						// c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;//防止变色把根节点也变色了

		return true;
	}

private:
	Node* _root = nullptr;
};

插入新节点的时候默认先设置成红色的哈

设置成黑色的话，违反第四点，比设置成红色违反-第三点的调整难度更大

插入新节点的处理

这个处理的前提是插入的节点要先设置成红色的哈

这个新节点刚开始是cur

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

插入一个节点完成后，要把根节点重新改成黑色–怕处理插入问题时颜色被改了

情况一: cur为红，p为红，g为黑，u存在且为红

解决方法:把p,u改为黑，g改为红，然后把g当作cur，继续向上调整

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑 (cur p g直线)

p为g的左孩子，cur为p的左孩子时，进行右旋，然后让p变黑，g变红

p为g的右孩子，cur为p的右孩子时，则进行左旋，然后让p变黑，g变红

这里的旋转是c p g 进行，没有u"参与"哈–怎么旋转可以看AVL树的，一模一样

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑 (折线 p在最左边)

p为g的左孩子，cur为p的右孩子时，则做左旋

p为g的右孩子，cur为p的左孩子时，则做右旋

这里的旋转是c p g 进行，没有u"参与"哈–怎么旋转可以看AVL树的，一模一样

然后就转换成情况2了

红黑树的验证

也就是验证自己的红黑树写没写对

验证的话最主要是验证有没有连续红节点和每条路径的黑节点个数是不是一样多以及根节点是不是黑色的

不要去单独用最短路径和最长路径的关系是判断是不是红黑树–制约不够的

验证有无连续红节点的时候，检查该节点的孩子颜色太麻烦了，不如检查父亲的颜色

	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(Node* root)
	{
		if (root == nullptr)
			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 CheckColour(root, 0, benchmark);
	}

作业部分

关于AVL树和红黑树的区别说法不正确的是（C）
A.AVL树和红黑树保证平衡性的方式不同
B.AVL树和红黑树都是平衡树，因此查找的时间复杂度都是O(logN)
C.AVL树和红黑树的性质遭到破坏时，都需要进行旋转
//红黑树有时不需要旋转
D.AVL树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树

转载自CSDN-专业IT技术社区

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/rs1257483201/article/details/151156572