当前位置:   article > 正文

【数据结构】红黑树_红黑树概念 csdn

红黑树概念 csdn


在这里插入图片描述

1. 红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的,不像AVL树那样严格的平衡。
在这里插入图片描述

2. 红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的(即不能出现连续的红节点
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点(即每条路径上的黑色节点相等
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍(最长路径 <= 最短路径×2 ),为什么会这样呢?-- 如下图
在这里插入图片描述
如果比较AVL树和红黑树的搜索,AVL树的查找效率更高为:logN;

在这里插入图片描述

但是在插入和删除时红黑树的效率更高,它不需要严格的平衡,旋转的次数更少。

3. 红黑树的实现

3.1 节点与树的定义

插入时,我们是插入黑节点好还是红节点好呢?选择破坏性质3还是性质4呢?

  • 如果插入黑色的,每条路径上的黑色节点数量就不相等了,每条路径都得改,非常麻烦。
  • 如果插入红色的,如果它的父亲是黑色的,那就没有破坏任何规则;若父亲是红色,那就存在了连续的红节点,最长路径可能就会超过最短路径的二倍,需要进行调整了。

那我们肯定选择调整次数少的方式,因此新增节点的颜色给红色(注意:当插入节点为根节点时,应该是黑色

  • 节点的结构
	//颜色
	enum Color
	{
		RED = 0,
		BLACK
	};

	template<class K, class V>
	struct TreeNode
	{
		pair<K, V>  _kv;
		TreeNode<K, V>* _left;
		TreeNode<K, V>* _right;
		TreeNode<K, V>* _parent;//前驱节点
		Color _col;

		TreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _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
  • 树的结构
	template<class K,class V>
	class RBTree
	{
		typedef TreeNode<K, V> Node;
	public:
		RBTree()
			:_root(nullptr)
		{}
		RBTree(const RBTree<K, V>& tree)
		{
			this->_root = Copy(tree._root);
		}
		RBTree<K, V>& operator=(RBTree<K, V> tree)
		{
			swap(this->_root, tree._root);//现代写法
			return *this;
		}
		~RBTree()
		{
			Destroy(_root);
		}

		bool insert(const pair<K, V>& kv)
		{

		}

		Node* find(const pair<K, V>& kv)
		{

		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	private:
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			_root->_left = Copy(root->_left);
			_root->_right = Copy(root->_right);
			return _root;
		}
		
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " ";
			_InOrder(root->_right);
		}

		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

3.2 查找

对于查找功能,搜索树都是一样的,非常简单就不赘述了。

		Node* find(const pair<K, V>& kv)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_kv.first < kv.first)
					cur = cur->_right;
				else if (cur->_kv.first > kv.first)
					cur = cur->_left;
				else
					return  cur;
			}
			return nullptr;
		}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

3.3 插入(重点)

在插入时,我们要先按照搜索树的规则找到插入位置,然后将新节点插入;新节点插入后,要检查红黑树的规则有没有被破坏注意:如果新插入的节点就是根节点,需要遵守规则2,根节点应为黑色

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点,需要遵守规则2(根是黑的)
				//需要将默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}
			
			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			//检查是否违反红黑树的规则
			//....
		}
  • 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

检测新节点插入后,红黑树的性质是否造到破坏;因为新节点的默认颜色是红色,因此,

  • 如果其父亲节点的颜色是黑色,没有违反红黑树任何规则,则不需要调整
  • 当其父亲节点颜色为红色时,就违反了性质三:不能有连在一起的红色节点

此时需要对红黑树分情况来讨论:
在这里插入图片描述

那违反规则后如何调整呢?又分为一下几种情况:

  1. 若新增节点为红,父亲为红,爷爷为黑,叔叔存在且为红,需要变色处理

在这里插入图片描述

但是当爷爷节点不是子树而是根时,需要将其变成黑色;若是子树,则保持它的红色,继续向上调整。

在这里插入图片描述

在这里插入图片描述

  1. 若新增节点为红,父亲为红,爷爷为黑,叔叔不存在或者叔叔存在且为黑,需要旋转+变色处理

右单旋的情况

  • 父亲在爷爷的左边、新增在父亲的左边
  • 如果叔叔不存在,旋转后将父亲变黑,爷爷变红
  • 如果叔叔存在且为黑,旋转后将父亲变黑,爷爷变红

在这里插入图片描述
新增节点为红色的原因如下:
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

左右双旋的情况

  • 父亲在爷爷的左边、新增在父亲的右边
  • 如果叔叔不存在,旋转后将新增节点变黑,爷爷变红
  • 如果叔叔存在且为黑,旋转后将新增节点变黑,爷爷变红

在这里插入图片描述

在这里插入图片描述

由于旋转的具体代码我们在AVL树种已经写过,这里就不给出具体步骤了。

	private:
		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;

			//降级连兵
			parent->_left = SubLR;
			if (SubLR)
				SubLR->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubL->_right = parent;
			parent->_parent = SubL;

			//将连将
			SubL->_parent = parentParent;
			if (parentParent == nullptr)
			{
				_root = SubL;
			}
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubL;
				else
					parentParent->_right = SubL;
			}
		}

		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;

			//降级连兵
			parent->_right = SubRL;
			if (SubRL)
				SubRL->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubR->_left = parent;
			parent->_parent = SubR;

			//将连将
			SubR->_parent = parentParent;
			if (parentParent == nullptr)
				_root = SubR;
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubR;
				else
					parentParent->_right = SubR;
			}
		}
  • 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

当父亲在爷爷左侧时,大体框架就是这样:

在这里插入图片描述

父亲在爷爷的右侧时,也是类似的,我们仅给出旋转时的图:

新增在父亲的右侧,构成“直”树,采用左单旋

在这里插入图片描述


右左双旋
新增在父亲的左侧,构成“弯”树,采用右左双旋

在这里插入图片描述

具体的代码实现如下:

				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑,需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
  • 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

那红黑树的插入就实现完了,完整代码如下:

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点,需要遵守规则2(根是黑的)
				//需要默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}

			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;
			//-----------------------------------------------------------------------
			//检查是否违反红黑树的规则
			//如果父亲存在且为红,则违反规则
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					//根据爷爷节点找叔叔
					Node* uncle = grandfather->_right;

					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//然后继续向上调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑,需要旋转+变色
					else
					{
						//判断单旋(直树)还是双旋(弯树)
						//单旋
						if (parent->_left == cur)
						{	
							//       g
							//     p   u
							//	c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//双旋
						else
						{
							//        g
							//     p     u
							//	     c
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

						}
						break;//旋转后已经符合规则,无需再调整了
					}
				}
				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑,需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_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
  • 127
  • 128
  • 129
  • 130

3.4 红黑树的验证

红黑树的检测分为两步:

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质
    • 是否存在连续的红节点
    • 每条路径黑色节点的个数是否相等

在检查每条路径上黑节点的个数时,首先要有一个黑节点个数的标准值,可以是最左侧或者最右侧;同时还要有一个变量或者容器来存储当前路径中表黑节点的个数。

		bool IsRBTree()
		{
			Node* root = _root;
			if (root == nullptr)//空树也是
				return true;
			
			if (root->_col == RED)
			{
				cout << "根节点为红色,违反规则" << endl;
				return false;
			}

			//先统计最左侧路径上有多少黑节点作为标准
			Node* cur = root;
			int blackNum = 0;
			while (cur)
			{
				if (cur->_col == BLACK)
					blackNum++;
				cur = cur->_left;
			}
			//k用来记录路径中黑节点的个数
			int k = 0;
			//在依据标准黑节点的个数,比较其它路径
			return _IsRBTree(root, blackNum, k);
		}
  • 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

有了黑节点的标准值后,我们才可正式开始比较每条路径黑节点的个数

		bool _IsRBTree(Node* root, int blackNum, int k)
		{
			//一条路径走完,比较黑节点的个数
			if (root == nullptr)
			{
				if (blackNum != k)
				{
					cout << "路径黑节点个数不相等,违反规则" << endl;
					return false;
				}
				return true;
			}
			Node* parent = root->_parent;
			if (parent && root->_col == RED && parent->_col == RED)
			{
				cout << "存在连续的红节点,违反规则" << endl;
				return false;
			}

			//统计黑节点
			if (root->_col == BLACK)
				k++;
			//统计完根,在依次统计左右子树
			return _IsRBTree(root->_left, blackNum, k)
				&& _IsRBTree(root->_right, blackNum, k);
		}
  • 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

4. 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多

5.完整代码

namespace my
{
	//颜色
	enum Color
	{
		RED = 0,
		BLACK
	};

	template<class K, class V>
	struct TreeNode
	{
		pair<K, V>  _kv;
		TreeNode<K, V>* _left;
		TreeNode<K, V>* _right;
		TreeNode<K, V>* _parent;//前驱节点
		Color _col;

		TreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)//默认新节点为红色的
		{}
	};

	template<class K,class V>
	class RBTree
	{
		typedef TreeNode<K, V> Node;
	public:
		RBTree()
			:_root(nullptr)
		{}
		RBTree(const RBTree<K, V>& tree)
		{
			this->_root = Copy(tree._root);
		}
		RBTree<K, V>& operator=(RBTree<K, V> tree)
		{
			swap(this->_root, tree._root);//现代写法
			return *this;
		}
		~RBTree()
		{
			Destroy(_root);
		}

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点,需要遵守规则2(根是黑的)
				//需要默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}

			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			//检查是否违反红黑树的规则
			//如果父亲存在且为红,则违反规则
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					//根据爷爷节点找叔叔
					Node* uncle = grandfather->_right;

					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//然后继续向上调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑,需要旋转+变色
					else
					{
						//判断单旋(直树)还是双旋(弯树)
						//单旋
						if (parent->_left == cur)
						{	
							//       g
							//     p   u
							//	c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//双旋
						else
						{
							//        g
							//     p     u
							//	     c
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

						}
						break;//旋转后已经符合规则,无需再调整了
					}
				}
				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑,需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
			}
			//父亲不存在,或者父亲为黑时,无需判断,直接将根变黑
			_root->_col = BLACK;
			return true;
		}

		Node* find(const pair<K, V>& kv)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_kv.first < kv.first)
					cur = cur->_right;
				else if (cur->_kv.first > kv.first)
					cur = cur->_left;
				else
					return  cur;
			}
			return nullptr;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		bool IsRBTree()
		{
			Node* root = _root;
			if (root == nullptr)//空树也是
				return true;
			
			if (root->_col == RED)
			{
				cout << "根节点为红色,违反规则" << endl;
				return false;
			}

			//先统计最左侧路径上有多少黑节点作为标准
			Node* cur = root;
			int blackNum = 0;
			while (cur)
			{
				if (cur->_col == BLACK)
					blackNum++;
				cur = cur->_left;
			}
			//k用来记录路径中黑节点的个数
			int k = 0;
			//在依据标准黑节点的个数,比较其它路径
			return _IsRBTree(root, blackNum, k);
		}

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

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

	private:
		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;
			int leftH = _Height(root->_left);
			int rightH = _Height(root->_right);

			return leftH > rightH ? leftH + 1 : rightH + 1;
		}

		int _Size(Node* root)
		{
			if (root == nullptr)
				return 0;

			return 1 + _Size(root->_left) + _Size(root->_right);
		}

		bool _IsRBTree(Node* root, int blackNum, int k)
		{
			//一条路径走完,比较黑节点的个数
			if (root == nullptr)
			{
				if (blackNum != k)
				{
					cout << "路径黑节点个数不相等,违反规则" << endl;
					return false;
				}
				return true;
			}
			Node* parent = root->_parent;
			if (parent && root->_col == RED && parent->_col == RED)
			{
				cout << "存在连续的红节点,违反规则" << endl;
				return false;
			}

			//统计黑节点
			if (root->_col == BLACK)
				k++;
			//统计完根,在依次统计左右子树
			return _IsRBTree(root->_left, blackNum, k)
				&& _IsRBTree(root->_right, blackNum, k);
		}

		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;

			//降级连兵
			parent->_left = SubLR;
			if (SubLR)
				SubLR->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubL->_right = parent;
			parent->_parent = SubL;

			//将连将
			SubL->_parent = parentParent;
			if (parentParent == nullptr)
			{
				_root = SubL;
			}
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubL;
				else
					parentParent->_right = SubL;
			}
		}

		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;

			//降级连兵
			parent->_right = SubRL;
			if (SubRL)
				SubRL->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubR->_left = parent;
			parent->_parent = SubR;

			//将连将
			SubR->_parent = parentParent;
			if (parentParent == nullptr)
				_root = SubR;
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubR;
				else
					parentParent->_right = SubR;
			}
		}
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			_root->_left = Copy(root->_left);
			_root->_right = Copy(root->_right);
			return _root;
		}

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

		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
  • 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
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/1019381
推荐阅读
相关标签
  

闽ICP备14008679号