【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

03-27 1266阅读


【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）


快乐的流畅：个人主页


个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

文章目录

  • 引言
  • 一、红黑树的概念
  • 二、红黑树的模拟实现
    • 2.1 结点
    • 2.2 成员变量
    • 2.3 插入
      • 情况一：uncle在左，parent在右
        • ==如果uncle存在且为红色==：
        • ==如果uncle不存在，或者存在且为黑色==：
        • 情况二：parent在左，uncle在右
          • ==如果uncle存在且为红色==：
          • ==如果uncle不存在，或者存在且为黑色==：
          • 三、红黑树的验证
          • 四、红黑树的性能
            • 4.1 优势
            • 4.2 适用场景

              引言

              之前学习的AVL树，是一种平衡二叉搜索树，它追求绝对平衡，从而导致插入和删除性能较差。而今天学习的红黑树，是另一种平衡二叉搜索树，它追求相对平衡，使得增删查改的性能都极佳，时间复杂度皆为O(log2N)，是数据结构中的精华，天才般的设想！

              一、红黑树的概念

              红黑树，顾名思义，其节点有红和黑两种颜色。

              之所以新增结点颜色的标记，是因为通过结点着色方式的限制，能够让红黑树的最长路径不超过最短路径的两倍，以保证相对平衡。

              【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

              红黑树满足五条性质：

              1. 所有结点非黑即红
              2. 根结点为黑色
              3. NIL结点为黑色
              4. 红色结点的子结点必为黑色
              5. 任意结点到其叶子NIL结点的所有路径，都包含相同的黑色结点

              在红黑树中，NIL节点（也称为空节点）是叶子节点的一种特殊表示。它们不是实际存储数据的节点，而是树结构中的占位符，用于定义树的边界。所有的红黑树都以NIL节点为叶子节点，这些NIL节点在视觉上通常不被画出来。

              性质解读：

              • 性质4：表明不能有连续的红色结点
              • 性质4+性质5：
                • 理论最短路径：全为黑色结点
                • 理论最长路径：红黑相间

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  这样，就保证了最长路径不超过最短路径的两倍。

                  二、红黑树的模拟实现

                  2.1 结点

                  enum Color
{
	RED,
	BLACK
};
template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;
	Color _col;
	RBTreeNode(const pair& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

                  细节：

                  1. 使用三叉链，增加了指向parent的指针
                  2. 使用KV模型，数据存储键值对pair
                  3. 结点储存颜色，同时颜色使用枚举
                  4. 结点的颜色初始化为红色

                  说明：为什么结点的颜色初始化为红色呢？因为插入新节点时（不为根部），如果插入黑色，就会直接破坏性质5，导致每条路径黑结点数目不同；而如果插入红色，有可能不会破坏性质4，所以结点初始化为红色更优。

                  2.2 成员变量

                  template
class RBTree
{
protected:
	typedef RBTreeNode Node;
public:
protected:
	Node* _root = nullptr;
};

                  2.3 插入

                  因为红黑树也是二叉搜索树，所以默认成员函数和遍历与之前写的没什么不同，这里重点讲解红黑树的插入。

                  bool Insert(const pair& 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 _right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first _right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (grandparent->_right == parent)//uncle在左，parent在右
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)//uncle为红，变色+向上调整
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				cur = grandparent;
				parent = cur->_parent;
			}
			else//uncle为空或为黑，变色+旋转
			{
				if (parent->_right == cur)//左单旋
				{
					RotateL(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else//右左旋
				{
					RotateR(parent);
					RotateL(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
			}
		}
		else//parent在左，uncle在右
		{
			Node* uncle = grandparent->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				cur = grandparent;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_left == cur)//右单旋
				{
					RotateR(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else//左右旋
				{
					RotateL(parent);
					RotateR(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

                  思路：

                  1. 以二叉搜索树的方式正常插入
                  2. 讨论并调整结点的颜色，以及调整结构，使之满足红黑树的性质

                  循环条件：while (parent && parent->_col == RED)

                  保证了parent存在且为红，grandparent存在且为黑

                  情况一：uncle在左，parent在右

                  如果uncle存在且为红色：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 将parent和uncle变黑，grandparent变红
                  2. cur = grandparent，parent = cur->_parent，继续向上调整
                  3. 防止grandparent为根节点却变红，在循环结束后将根节点变为黑色
                  如果uncle不存在，或者存在且为黑色：

                  当cur在右部外侧时：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 先对grandparent进行左单旋
                  2. 再将parent变黑，grandparent变红

                  当cur在右部内侧时：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 先对parent进行右单旋
                  2. 再对grandparent进行左单旋
                  3. 最后将cur变黑，grandparent变红

                  情况二：parent在左，uncle在右

                  如果uncle存在且为红色：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 将parent和uncle变黑，grandparent变红
                  2. cur = grandparent，parent = cur->_parent，继续向上调整
                  3. 防止grandparent为根节点却变红，在循环结束后将根节点变为黑色
                  如果uncle不存在，或者存在且为黑色：

                  当cur在左部外侧时：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 先对grandparent进行右单旋
                  2. 再将parent变黑，grandparent变红

                  当cur在左部内侧时：

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  处理方法：

                  1. 先对parent进行左单旋
                  2. 再对grandparent进行右单旋
                  3. 最后将cur变黑，grandparent变红

                  红黑树插入的核心口诀：uncle存在且为红，变色+向上调整，uncle不存在或为黑，变色+旋转

                  附上旋转的实现：

                  void RotateL(Node* parent)
{
	Node* grandparent = parent->_parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	parent->_parent = subR;
	if (grandparent)
	{
		if (grandparent->_right == parent)
		{
			grandparent->_right = subR;
		}
		else
		{
			grandparent->_left = subR;
		}
	}
	else
	{
		_root = subR;
	}
	subR->_parent = grandparent;
}
void RotateR(Node* parent)
{
	Node* grandparent = parent->_parent;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	parent->_parent = subL;
	if (grandparent)
	{
		if (grandparent->_right == parent)
		{
			grandparent->_right = subL;
		}
		else
		{
			grandparent->_left = subL;
		}
	}
	else
	{
		_root = subL;
	}
	subL->_parent = grandparent;
}

                  三、红黑树的验证

                  bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout 
		if (cur-_col == BLACK)
		{
			++benchMark;
		}
		cur = cur-_right;
	}
	return Check(_root, 0, benchMark);
}
bool Check(Node* root, int blackNum, int benchMark)
{
	if (root == nullptr)
	{
		if (blackNum != benchMark)
		{
			cout 
		++blackNum;
	}
	if (root-_col == RED && root->_parent && root->_parent->_col == RED)
	{
		cout _right, blackNum, benchMark);
}

                  细节：

                  1. 验证根节点是否为黑
                  2. 先计算出一条路径的黑色结点个数作为基准值，再在递归中比较每条路径的黑色结点是否相等
                  3. 若该节点为红，检测其parent是否为红，判断是否存在连续的红色节点

                  四、红黑树的性能

                  4.1 优势

                  红黑树是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对AVL树而言，降低了插入和旋转的次数。

                  4.2 适用场景

                  因此，在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

                  【C++练级之路】【Lv.16】红黑树（冰与火的碰撞，红与黑的史诗）

                  真诚点赞，手有余香
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]