• 认识红黑树

    红黑树

    往期文章介绍了AVL树，它是一个颗平衡的搜索二叉树，当插入数据后如果导致任意结点的左右两边的高度差超过1，就会进行旋转调整，其平衡规则比较严格，所以当插入大量数据的时候就会导致多次旋转，本文介绍的红黑树也是一颗平衡搜索二叉树，它的平衡是通过控制结点的颜色来间接控制的，但是其平衡规则没有AVL树那样严格，是相对平衡的（最长的路径不超过最短路径的两倍都算平衡），所以其相对AVL树来说可以在大量插入数据的时候只需要旋转较少的次数就可以实现树的平衡。

    在这里插入图片描述

    什么是红黑树

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

    红黑树遵守的规则

    既然是平衡树就需要遵守一些规则来保持树的平衡，下面是红黑树必须遵守的五个规则，只有遵守这五个规则，才可以使得红黑树是平衡树！！！

    • 1.每个结点的颜色不是黑色就是红色
    • 2.根结点必须是黑色的
    • 3.如果一个节点是红色的，那么他的子节点就必须是黑色的（不能有连续的红色结点）
    • 4.对于每个结点，从该结点到其所有后代叶子结点的简单路径上，都包含相同颜色的黑色结点
    • 5.每个叶子结点都是黑色的（即空结点是黑色的，简单路径以空结尾）

    思考一：为什么遵循了上面的规则就可以保证树中的最长路径不超过最短路径的两倍呢？

    因为在不破坏规则的情况下，最短路径就是该路径都是全黑结点，最长路径就是一黑一红交替。极端情况下满足最长路径恰好是最短路径的两倍，不会超过两倍。

    在这里插入图片描述

    思考二：新增的结点是设为黑色还是红色呢？

    考虑到规则限制，我们可以知道如果在原本平衡的树中插入新的结点的颜色为黑色，就会违反规则4（从一个结点到其所有后代叶子结点的简单路径上的黑色结点个数相同），如果在原本平衡的树中插入新的结点的颜色为红色，那么就不会违反规则4，但是有可能会违反规则3（不能存在连续的红色结点）。

    • 综合以上两种情况，我们可以分析当一个树的结点非常多的时候那么一个结点到其所有后代的叶子结点的路径就会非常多，如果新增结点是黑色就必然违反这个规则，就需要更改每一条路径，非常难处理！！！

    • 但是如果新增是红色就是当新增结点的父亲是红色的时候（连续红结点）才会违反规则，但是这种连续红结点的情况我们可以通过往上迭代改变结点的颜色来维护规则，总而言之就是违反规则3相对违反规则4比较好处理。所以新增的结点颜色默认设为红色的。

    举例：
    在这里插入图片描述

    • 如果上面的额2是黑色结点就会导致4到其所有叶子结点的简单路径上黑色结点不相同，8也会受到影响，处理起来很麻烦。

    红黑树的实现

    基本结构

    //结点的颜色 用枚举表示
enum color
{
	RED,
	BLACK,
};
template<class K,class V>
//树的结点
struct RBTreeNode
{
    //三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;//每个结点可以找到父亲  

	color _col;//颜色
	pair<K, V> _kv;//数据
	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
		,_kv(kv)
	{

	}
	
};

template<class K,class V>
class RBTree
{
public:
	typedef RBTreeNode<K,V> Node;
    typedef __RBTree_Iterator<T, T&, T*> iterator;
	typedef __RBTree_Iterator<T,const T&,const T*> const_iterator;//迭代器
    
	RBTree()
		:_root(nullptr)
	{}
    RBTree(const RBTree<K, V>& t)//拷贝构造
	{
		_root = copyNode(t._root);
	}
	
    iterator begin();
    const_iterator begin()const {}
	iterator end();
    const_iterator endn()const{} 
	
    //左右旋转
	void RotateL(Node* parent);
    void RotateR(Node* parent);
    //主要是掌握插入数据构建红黑树
    bool insert(const pair<K,V>& kv);
    size_t getMaxHight();
    size_t getMinHight();
    bool checkIsRBTree();
private:
    Node* _root;
}
    
    

    • 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

    学习红黑树主要是学插入数据的过程中的各种导致不平衡的情况该如何调整，使得插入数据前后都是平衡的树，不违法红黑树遵循的规则。

    插入的多种情况分析

    这里称插入结点（c表示）的父亲结点的兄弟结点为叔叔结点（u表示)，插入结点的父亲的父亲为祖父结点(g表示）。

    第一种：叔叔存在且为红

    在这里插入图片描述

    处理：将p变黑，u变黑，g变红（如果g是根结点就将其颜色改成黑）再往上迭代器处理（即第一次变色后可能会影响上层的结点，就需要往上迭代处理，如果有违反的情况就处理）

    为什么需要迭代往上修改呢？

    如下图，出现连续的红色结点后进行了改色，这可能会影响上层的结点，这里使g变成了红色g的父节点也是红色，就又出现了连续的红结点，就还需要处理，所以要往上迭代处理如果不符合规则就对其进行处理，处理到符合所有规则为止！！！

    第二种：叔叔不存在

    叔叔不存在的情况也有四种

    满足c为红 p为红 g为黑

    • 1、p为g的左，c为p的左（g p c 形成斜线 / ）
      在这里插入图片描述

    处理方式：对g进行右单旋，再把p变成黑色，g变红色

    • 2、p为g的左 ，c为p的右（g p c形成折线 < )

    在这里插入图片描述

    处理方式：对p进行左单旋，然后变成第一种情况（/斜线型），进行处理。

    • 3、p为g的右，c为p的右（g p c 形成斜线 \ ）

    在这里插入图片描述

    处理方式：对g进行左单旋，再把p变成黑色，g变红色

    • 4、p为g的右， c为p的左（g p c 形成折线 > )

    在这里插入图片描述

    处理方式：对p进行右单旋，然后变成第一种情况（\斜线型），进行处理。

    第三种：叔叔存在且为黑

    叔叔存在且为黑的情况是由叔叔存在且为红的情况转化而来的，下面的图都是包含叔叔存在且为红的情况，处理完叔叔存在且为红后就有可能会形成叔叔存在且为黑的情况，以下就是所有的情况，其中的△是代表空或者各种子树（也就是说△可以拓展开来，只要拓展开后不违反规则就可以！）

    这里涉及树的旋转 可以参考前几期的AVL树的博客 里面有旋转的详细解析

    满足c为红 p为红 g为黑

    • 1、p为g的左，c为p的左（g p c 形成斜线 / ）

    在这里插入图片描述

    处理方式：1、处理完叔叔存在且为红的情况后转化为叔叔存在且为黑的情况。

    ​ 2、对g进行右单旋，再把p变成黑色，g变红色

    • 2、p为g的左 ，c为p的右（g p c形成折线 < )

    在这里插入图片描述

    处理方式：1、处理完叔叔存在且为红的情况后转化为叔叔存在且为黑的情况。

    ​ 2、对p进行左单旋，将折线型（<）转化为斜线型(/），转化为上面的情况1处理

    • 3、p为g的右，c为p的右（g p c 形成斜线 \ ）

    在这里插入图片描述

    处理方式：1、处理完叔叔存在且为红的情况后转化为叔叔存在且为黑的情况。

    ​ 2、对g进行左单旋，再把p变成黑色，g变红色

    • 4、p为g的右， c为p的左（g p c 形成折线 > )

    在这里插入图片描述

    处理方式：1、处理完叔叔存在且为红的情况后转化为叔叔存在且为黑的情况。

    ​ 2、对p进行右单旋，将折线型（>）转化为斜线型(\），转化为上面的情况3处理

    插入函数的代码：

    bool insert(const pair<K,V>& kv)
	{
    	//第一次插入的情况 新插入结点（红色）做根结点 然后得把其颜色改成黑
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		else
		{
			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已经为空了 直接将新结点赋值给cur
			cur = new Node(kv);
			cur->_col = RED;
			//链接新增结点和其父节点
			if (cur->_kv.first < parent->_kv.first)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

			//调整红黑树 维持规则
			while (parent&&parent->_col==RED)
			{
				Node* grandfather = parent->_parent;
				Node* uncle = nullptr;
			
				if (grandfather->_left == parent)
				{
					uncle = grandfather->_right;
				}
				else
				{
					uncle = grandfather->_left;
				}

			
				 if (parent&&parent->_col== RED && uncle && uncle->_col == RED)//叔叔存在且为红
				{
					
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;//迭代往上调整
						parent = cur->_parent;
				
				}
				else if (parent&&parent->_col==RED&&(uncle == nullptr||(uncle!=nullptr&&uncle->_col==BLACK)) )//叔叔不存在或存在且为黑
				{
					if (grandfather->_left==parent&&cur==parent->_right)//叔叔不存在
					{
						//        g
						//	  p
						//        c
						RotateL(parent);
						swap(parent, cur);
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						
					}
					else if (grandfather->_left == parent && cur == parent->_left)
					{
						//        g
						//    p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (grandfather->_right == parent && cur == parent->_left)
					{
						//    g
						//		 p
						//    c
						RotateR(parent);
						swap(parent, cur);
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED; 

					}
					else if (grandfather->_right == parent && cur == parent->_right)
					{
						//    g
						//		 p
						//			 c
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			
			_root->_col = BLACK;
			return true;
		}
	}


    • 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

    旋转代码

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

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* ppnode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else if(ppnode->_right==parent)
			{
				ppnode->_right = subR;
			}
			else
			{
				cout << "内部错误！" << endl;
				assert(false);
			}
			subR->_parent = ppnode;
		}

	}

    • 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
    RotateR
    void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* ppnode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else if (ppnode->_right == parent)
			{
				ppnode->_right = subL;
			}
			else
			{
				cout << "内部错误！" << endl;
				assert(false);
			}
			subL->_parent = ppnode;
		}
	}

    • 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

    判断是否为红黑树的函数（也就是检查是否符合规则）

    checkIsRBTree
    	bool checkIsRBTree()
	{
		if (_root == nullptr)//空树也是红黑树
		{
			return true;
		}
		if (_root->_col != BLACK)
		{
			cout << "根结点不为黑！" << endl;
			return false;
		}
		Node* cur = _root;
		size_t standardBlackCount = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				standardBlackCount++;
			}
			cur = cur->_left;
		}
		size_t k = 0;
		return _checkIsRBTree(_root, standardBlackCount, k); 
	}

	//传一个最短基准值 判断每条路径是否超过其两倍
	bool _checkIsRBTree(Node* root,size_t standardCount,size_t blackCount)
	{
		if (root == nullptr)
		{
			if (standardCount != blackCount)
			{
				cout << "不符合每条路径上的黑结点数目相同！" << endl;
				return false;
			}
			
			return true;
		}
		//统计当前路径的黑结点的数量
		if(root->_col==BLACK)
		blackCount++;

		Node* parent = root->_parent;
		if (root->_col == RED && parent && parent->_col == RED)
		{
			cout << "存在连续红结点！" << endl;
			return false;
		}
		
		return _checkIsRBTree(root->_left,standardCount,blackCount) && _checkIsRBTree(root->_right,standardCount,blackCount);

	}

    • 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

    拷贝构造函数（深拷贝）

    RBTree(const RBTree<K, V>& t)
	{
		_root = copyNode(t._root);
	}
	Node* copyNode(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* newroot = new Node(root->_kv);
		newroot->_left = copyNode(root->_left);
		newroot->_left = copyNode(root->_right);
		return newroot;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    获取树的最小和最大高度

    size_t getMaxHight()
	{
		return _getMaxHight(_root);
	}
	size_t _getMaxHight(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		size_t LMH = _getMaxHight(root->_left);
		size_t RMH = _getMaxHight(root->_right);
		return LMH > RMH ? LMH + 1 : RMH + 1;
	}

	size_t getMinHight()
	{
		return _getMinHight(_root);
	}

	size_t _getMinHight(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		size_t LMH = _getMinHight(root->_left);
		size_t RMH = _getMinHight(root->_right);
		return LMH < RMH ? LMH + 1 : RMH + 1;
	}


    • 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

    红黑树的迭代器实现

    在这里插入图片描述

    operator-- 就是类比operator++ 即可推出，这里就不多bb了 。

    	template<class T,class Ref,class Ptr>
	struct __RBTree_Iterator
	{
		typedef __RBTree_Iterator<T, Ref, Ptr> self;
		typedef RBTreeNode<T> Node;
		__RBTree_Iterator(Node* root)
			:_root(root)
		{

		}
		Ref operator*()//这里是无参的返回的额是当前迭代器对象的数据 
		{
			return _root->_data;
		}
		Ptr operator->()
		{
			return &(_root->_data);
		}
		self& operator=(const self& it)
		{
			_root = it._root;
		}
		self& operator++()
		{
			if (_root->_right == nullptr)
			{
				Node* cur = _root;
				Node* parent = _root->_parent;
				while (parent&&parent->_left != cur)//要保证最后一个结点的 
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_root = parent;
			}
			else
			{
				Node* right = _root->_right;
				while (right->_left)
				{
					right = right->_left;
				}
				_root = right;
			}
			return *this;
		}
		self& operator++(int)
		{
			//self tmp = *this;
			self tmp(*this);
			++ *this;
			return tmp;

		}
		self& operator--()
		{
			if (_root->_left==nullptr)
			{
				Node* cur = _root;
				Node* parent = _root->_parent;
				while (parent&&parent->_right != cur)
				{
					cur = cur->_parent;
					parent = parent->_parent;
				}
				_root = parent;
			}
			else
			{
				Node* left = _root->_left;
				while (left->_right)
				{
					left = left->_right;
				}
				_root = left;
			}
			return *this;
		}
		self& operator--(int)
		{
			//self tmp = *this;
			self tmp(*this);
			-- *this;
			return tmp;
		}

		bool operator==(const self& it)const 
		{
			return _root == it._root;
		}
		bool operator!=(const self& it)const 
		{
			return _root != it._root;
		}

		Node* _root;
	};


    • 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
  • 相关阅读:
    pg distinct 改写递归优化（德哥的思路）
    麻了，不要再动不动就BeanUtil.copyProperties！！！
    iOS 16 SwiftUI列表（List）项包含 Label 视图导致分隔线变短的解决
    数字电路中的基础电路结构
    IDEA Java1.8通过sqljdbc4连接sqlserver插入语句
    在PostgreSQL中如何有效地批量导入大量数据，并确保数据加载过程中的性能和稳定性？
    BERT知识蒸馏Distilled BiLSTM
    net 获取本地ip地址，net mvc + net core 两种
    7-7 六度空间
    jdbc连接oracle数据库
  • 原文地址：https://blog.csdn.net/xbhinsterest11/article/details/126815978