• 【C++】红黑树插入过程详解

    学习导航

    (1)基本概况

    ​  红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
    ​  通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的 。

    红黑树的性质：

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

    2. 红色结点不能同时出现，而黑色结点可以

    3. 对于每个结点，从该结点到其所有后代叶结点的简单路径（路径上的各顶点均不互相重复）上，均包含相同数目的黑色结点

    4. 根节点必须是黑色

    ​  虽然红黑树不如AVL树平衡，但是它为了维持平衡而进行的旋转的次数更少，因此应用也很广泛。

    (2)红黑树结点的定义

    enum colour
{
	BLACK,
	RED
};


template <class K, class V>
struct RBTreeNode
{
	// 三叉链
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	
	pair<K, V> _kv;
	colour _col;       

	RBTreeNode(const pair<K, V>& kv)
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_kv(kv)
		,_col(RED)
		// 默认要插入红色结点，因为这样容易维护红黑树性质
	{}
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    【问题反思】：为什么默认插入红色的结点呢?

    ​  插入一个红色结点，可能会破坏性质2，插入一个黑色结点，一定会破坏性质3。秉着柿子要拿软的捏的原则，插入一个红色结点更便于我们之后红黑树性质的维护

    (3)红黑树的插入

    1.基本步骤

    红黑树的插入过程可以大致分为以下两步：

    • 按照二叉搜索树的的规则插入新节点
    • 检测新节点插入后，红黑树的性质是否遭到破坏
    2.插入新结点

    ​ 红黑树也是二叉搜索树的一种，其插入过程与二叉搜索树别无二致：

    1. 待插入的结点小于当前父结点，则与左孩子继续比较
    2. 待插入的结点大于当前父节点，则与右孩子继续比较
    3. 待插入结点与父节点相同，则插入失败，返回false，因为键(K)不允许重复

    ​ 重复上述过程直至遇到在空，在空节点位置处进行插入。参考代码如下：

    template <class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	bool insert(const pair<K, V>& kv)
	{
		Node* newnode = new Node(kv);
		if (_root == nullptr)
		{
			_root = newnode;
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		// (1)按照二叉搜索树的方式插入新结点
		while (cur)
		{
			parent = cur;
			if (cur->_kv.first > kv.first)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		if (parent->_kv.first < kv.first)
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		else
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}

		cur = newnode;
		// (2)维护红黑树的性质
        // 代码见下

private:
	Node* _root = nullptr;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    3.维护红黑树性质

    ​  如何在插入新结点后维护红黑树的性质呢?五个字——关键看舅舅。为了便于说明，我们约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点 ，灰框表示子树（可能为空树）：
     
    ​  插入新结点前，p一定为红色，否则插入新结点后不需要维护红黑树，我们不考虑；g一定为黑色，否则将不满足红黑树的性质。因为默认插入的新结点为红色，所以cur、p、g的结点颜色都是确定的，唯一不能确定的是u的颜色。

    ​ 根据u结点的状态，我们有以下三种情况：

    • 【情况一】：舅舅结点为红色

      【案例】：image-20220914194921465

      【处理】：

      1. 将p和u的颜色修改为黑，g的颜色修改为红
      2. 令cur = grandfather; parent = cur->_parent;，并继续往上检测

      【分析】：

      • 这颗树有可能只是某一节点的子树，为了保证子树中每条路径的黑色结点数目不变，需要将g结点颜色变为黑色。
      • g结点的父节点可能也是红色，这样将不满足红黑树的第三条性质，所以需要继续往上检测
      • 注意u结点可能在左，p结点可能在右，但分析过程同理

    • 【情况二】：舅舅结点为空或者为黑色（且g、p、cur在“同一直线”上）

      【案例】：

      【处理】：

      1. 首先对g进行右旋转
      2. 旋转后将祖父结点变红色，父节点变黑色

      【分析】：

      • 插入cur结点前，一定是满足红黑树性质的，虽然看起来g-u一路的黑结点多，但别忘记了0,1,2,3,4子树里也有黑结点。所以我们只需关注各个有色结点在调整前后最简路径上的黑色结点数不变即可。
      • 如果cur存在子树，那它一定是情况一种向上调整后的结果
      • 若p在右子树，u在左子树，分析过程相同，旋转方向对称
      • 如何旋转?旋转的注意点?在上一篇博客里做了详细说明，这里不再赘述 【C++】AVL树插入过程详解

    • 【情况三】：舅舅结点为空或者为黑色（且g、p、cur不在“同一直线”上）

      【案例】：

      image-20220914220643885

      【处理】：

      1. 首先对p进行左旋转将g、cur、p三点转换到同一直线上
      2. 然后同情况二的方式进行旋转+变色

      【分析】：

      • 若p在右子树，u在左子树，分析过程相同，旋转方向对称

    红黑树插入过程参考代码如下：

    template <class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	bool insert(const pair<K, V>& kv)
	{
		Node* newnode = new Node(kv);
		if (_root == nullptr)
		{
			_root = newnode;
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		// (1)按照二叉搜索树的方式插入新结点
		// ……见上
        
		// (2)维护红黑树的性质

		// 红色结点一定存在父节点，所以祖父结点一定存在
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			Node* uncle = nullptr;
			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}
			else
			{
				uncle = grandfather->_left;
			}

			if (uncle && uncle->_col == RED)
			{
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandfather->_col = RED;

				// 注意cur不是变成parent，这个没意义
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (parent == grandfather->_left)
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
				}

				break;
			}

		}
		_root->_col = BLACK;  // 根节点一定是黑色
		return true;
	}

private:
	void RotateR(Node* parent)
	{
		Node* pparent = 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 (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = pparent;
			if (parent == pparent->_left)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
	}

	void RotateL(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
        // 小心subRL为空的情况
		if (subRL)              
		{
			subRL->_parent = parent;
		}

		parent->_parent = subR;
		subR->_left = parent;

		if (parent == _root)    
        // 小心parent的头结点为空的情况
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = pparent;
            // 位于pparent的左子树
			if (parent == pparent->_left) 
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
	}
	Node* _root = nullptr;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    4.验证是否为红黑树

    红黑树的验证主要有以下两个方面：

    1. 验证没有连续出现的红色结点
    2. 验证各条支路的黑色结点个数是否相同

    （注：遇到红色结点就检查父亲比遇到红色结点就检查孩子更容易实现，因此下面递归实现中不从根节点开始）

    参考代码如下：

    template <class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	bool IsValidRBTree()
	{
		Node* root = GetRoot();
        // 空树也是红黑树
		if (root == nullptr)  
			return true;
		// 根据性质4，根节点一定是黑色的
		if (root->_col == RED)
			return false;

		Node* cur = root->_left;
		int blackcount = 0;
        // 计算出一条支路中除根节点外有多少个黑色结点
        // 依次作为其他支路的参照
		while (cur)
		{
			if (cur->_col == BLACK)
				blackcount++;
			cur = cur->_left;
		}
		return _IsValidRBTree(root->_left, 0, blackcount)
			&& _IsValidRBTree(root->_right, 0, blackcount);
		
	}

private:

	Node* GetRoot()
	{
		return _root;
	}

	bool _IsValidRBTree(Node* root, int k, int blackCnt)
	{
		if (root == nullptr)
		{
			if (k != blackCnt)
			{
				cout << "不满足各个路径的黑色结点数相同" << endl;
				return false;
			}
			return true;
		}
		
        // 遇到红色结点就检查父亲
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "出现连续的红色结点";
		}

		if (root->_col == BLACK)
			k++;
		// 分支——检查左右子树
		return _IsValidRBTree(root->_left, k, blackCnt) &&
			_IsValidRBTree(root->_right, k, blackCnt);
	}
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
  • 相关阅读:
    msql检索包含中文的记录
    关于FlowUs这一款国民好笔记
    openpowerlink 01
    【计算机网络】网络编程接口 Socket API 解读（3）
    设计模式学习笔记（十八）备忘录模式及其实现
    []==![]结果为true,探究 == 本质
    外包干了10个月，技术退步明显.......
    通过WebSocket实现实时系统通知，以后再也不能装作没看到老板的通知了～～
    linux统计程序耗时和最大内存消耗
    python（进阶篇）——多线程
  • 原文地址：https://blog.csdn.net/whc18858/article/details/126861844