【ONE·C++ || set和map（二）：AVL树和红黑树】

总言

  主要介绍AVL树和红黑树的部分框架结构和特性

1、AVL树

1.1、基本概念介绍

  1）、AVL树是什么
  AVL树实际是对二叉搜索树的特化，又被称为高度平衡二叉搜索树。

  二叉搜索树问题说明： 数据有序或接近有序时，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，从而使得效率低下。
  解决方法： 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
  
  介绍： 一棵AVL树，其要么是空树，要么是具有以下性质的二叉搜索树：
  1、它的左右子树都是AVL树
  2、左右子树高度之差(简称平衡因子)的绝对值不超过1(-1、0、1)
  
  注意事项：
  1、当前根节点的平衡因子 = 右子树高度 - 左子树高度。平衡因子为非必需配置，可实现也可不实现。

  平衡因子==0，说明左右子树高度相等，平衡因子=1、-1，说明左右子树存在一边高一边低的现象。
  
  2、需要理解这里高度差的含义：这里必须保证任意一颗子树的高度差都不超过1。错误示范如下：

  3、由于结点个数原因，AVL树的高度平衡控制不能时刻保证左右子树高度随时相等，才有了这里平衡因子的存在。
  4、如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有$N$个结点，其高度可保持在$O(lo{g}_{2}N)$，搜索时间复杂度O($lo{g}_{2}N$)。
  
  
  

1.2、重要框架与特性实现

1.2.1、如何搭建AVL树的结点 ：AVLTreeNode，引入三叉链

  1）、三叉链
  介绍：结点中不仅存储左右孩子结点，还存储父结点。

  三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。

  说明：三叉链的这种存储方式，使得我们在实现AVL树的高度平衡时带来一定便捷，但同理的也会存在一些缺陷。（此部分可在后续实现时感受到）
  
  
  2）、AVLTreeNode实现
  AVL树的结点以三叉链实现，注意它的成员变量_bf，平衡因子不是非必须实现的。

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left; //左孩子指针
	AVLTreeNode<K, V>* _right; //右孩子指针
	AVLTreeNode<K, V>* _parent; //父节点指针

	pair<K, V> _kv;//当前结点值
	int _bf;//平衡因子：balance factor

	AVLTreeNode(const pair<K,V>& kv)//构造函数
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)//新增一个结点，其平衡因子初始时为0
	{}
};

1.2.2、如何搭建AVL树

  1）、框架搭建
  基本框架如下：

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//其它函数实现
	
private:
	Node* _root = nullptr;
};

1.2.3、AVL树插入讲解

  与二叉搜索树相比，AVL树在其基础上引入了平衡因子。在插入数据后，AVL除了要满足二叉搜索树的基本特性(左子树比根结点小，右子树比根结点大)，也要满足自己的特性(每个结点的左右子树高度之差的绝对值不超过1)。
  考虑到上述情况，AVL树的插入过程可以分为两步：
  1、按照二叉搜索树的方式插入新节点；
  2、调整节点的平衡因子；
  
  
  

1.3、AVL树插入

1.3.1、step1：按照二叉搜索树的方式插入新节点

  1）、基础说明
  AVL树插入新结点整体思路与二叉搜索树一致，但在细节上有一定区别。
  1、待插入值左右子树的位置判断：const pair<K, V>& kv，可以看到，我们给定的参数是一个键值对，其含有两个变量参数first、second。根据我们之前对set、map的学习，在pair判断左右子树时，我们同一看第一参数first，即key值。故而比较的是cur->_kv.first 和kv.first。
  2、三叉链带来的链接关系变化：对单个结点，当前新增结点的左右孩子指针_left和_right在构造函数中已经处理完成，但需要处理其父节点指针_parent与原先树的关系。同理，也要处理父节点中左右孩子与新增结点的关系。

	bool Insert(const pair<K, V>& kv)
	{
		//step1:按照二叉搜索树的方式插入新节点
		Ⅰ、查找合适的插入位置
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;		
		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//cur->kv.first==kv.first，key值已存在
			{
				return false;
			}
		}

		Ⅱ、当出了循环，说明cur==nullptr,找到合适位置，开始插入
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else//parent->_kv.first > kv.first
			parent->_left = cur;


		//step2：调整节点的平衡因子
		//此部分后续讲述
	}

1.3.2、step2：调整节点的平衡因子

1.3.2.1、更新平衡因子的相关规则

  1）、为什么要更新平衡因子
  说明： 当新结点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性。
  PS： 只有新增结点的祖先结点，其平衡因子可能会受到影响(父节点的平衡因子一定受到影响，需要调整，再往上的祖先结点不一定受影响)。所以我们需要沿着当前新增结点，往上找其祖先结点(包含父结点)，不断更新平衡因子。

  
  2）、如何更新平衡因子
  1、对单次结点进行更新：
  ①若新增结点在左，则parent->_bf--;
  ②若新增结点在右，则parent->_bf++;

  
  2、判断是否沿祖先迭代更新：
  ①更新后，若parent->_bf==0，则不必向上更新。 该情况说明在插入前parent的平衡因子为-1 or 1，即左右子树一边高一边低。新结点插入在了低的子树上，使得插入后parent左右子树高度不变，故而不用往上更新。

  ②更新后，若parent->_bf ==1 or -1，则需要向上更新。 该情况说明在插入前parent的平衡因子为0，即左右子树高度相等。新结点的插入使得parent左右子树高度改变。

  ③ 更新后，若parent->_bf== 2 or -2, 则平衡打破，需要旋转。 该情况说明在插入前parent的平衡因子是1 or -1, 已经处于平衡临界值，新节点的插入使得平衡因子变为 2 or -2，故而需要对当前parent所在的子树进行旋转处理，以维持高度平衡。

  ④更新后，若parent->_bf >2 or <-2，不存在。若我们得到结果如此，只能说明之前AVL树的平衡操作出了问题，需要进行检查。

  
  
  3）、相关代码实现（总体框架搭建）
  代码如下:

		//step2：调整节点的平衡因子
		while (parent)
		{
			Ⅰ、对单次结点进行更新
			if (parent->_left == cur)
				parent->_bf--;//新增在左
			else
				parent->_bf++;//新增在右

			Ⅱ、判断是否需要沿祖先迭代更新
			if (0 == parent->_bf)
			{	//更新后，若parent->_bf==0，则不必向上更新。
				break;
			}
			else if (1 == abs(parent->_bf))
			{
				//更新后，若parent->_bf == 1 or -1，则需要向上更新。
				cur = parent;
				parent = parent->_parent;
			}
			else if (2 == abs(parent->_bf))
			{
				//更新后，若parent->_bf== 2 or -2, 则平衡打破，需要旋转。
				//此部分后续讲述
			}
			else
			{
				assert(false);//直接断言报错
			}

		}

1.3.2.2、AVL树旋转模式(四类)

  根据之前小节分析，AVL树中插入一个新节点，在有些情况下会使得当前树不平衡，此时就必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种。

1.3.2.2.1、左单旋：新结点插入较高右子树的右侧(右右)

  相关代码如下：

				if (parent->_bf == 2 && cur->_bf == 1)//左单旋：新结点插入较高右子树的右侧，导致其祖先节点中有节点的平衡因子达到2，需要旋转调整。
				{
					RotateL(parent);
					break;
				}

  左单旋函数实现如下：

private:
	void RotateL(Node* parent) //parent->_bf==2的节点
	{
		//1、关于左单旋涉及到的节点
		Node* subR = parent->_right;
		Node* subRtoL = subR->_left;
		Node* grendparent = parent->_parent;

		//2、修改链接关系以达成旋转
		//2.1、修改parent的链接关系（右孩子、父亲）
		parent->_right = subRtoL;
		parent->_parent = subR;
		
		//2.2、修改subRtoL的链接关系（父亲）
		if (subRtoL)//h>=0，subRtoL可能不存在(nullptr)。只有其存在时才修改其父节点指向
			subRtoL->_parent = parent;

		//2.3、修改subR的链接关系（左孩子、父亲）
		subR->_left = parent;
		if (_root == parent)//若parent为原先AVL树的根节点
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		else//若parent为原先AVL树的分支节点
		{
			subR->_parent = grendparent;
			if (grendparent->_left == parent)//用于判断原先parent为grendparent的哪一个孩子
				grendparent->_left = subR;
			else
				grendparent->_right = subR;
		}

		//3、处理修改后的平衡因子
		subR->_bf = parent->_bf = 0;
	}

  示意图：

  
  
  
  

1.3.2.2.2、右单旋：新结点插入较高左子树的左侧(左左)

  相关代码如下：

				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
				{
					RotateR(parent);
				}

	void RotateR(Node* parent)
	{
		//1、右单旋涉及到的节点
		Node* subL = parent->_left;
		Node* subLtoR = subL->_right;
		Node* grendparent = parent->_parent;

		//2、处理链接关系
		//2.1、对parent：左孩子、父亲
		parent->_left = subLtoR;
		parent->_parent = subL;
		
		//2.2、对subLtoR：父亲
		if (subLtoR)
			subLtoR->_parent = parent;
	
		//2.3、对subL：右孩子、父亲
		subL->_right = parent;
		if (_root = parent)//若parent为原先AVL树的根节点
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		else//若parent为原先AVL树的分支节点
		{
			subL->_parent = grendparent;
			if (grendparent->_left == parent)
				grendparent->_left = subL;
			else
				grendparent->_right = subL;
		}
		
		//3、处理平衡因子
		subL->_bf = parent->_bf = 0;
	}

  示意图：

1.3.2.2.3、左右双旋：新结点插入较高左子树的右侧(左右)

  即先左单旋再右单旋。如下图，在b、c位置插入，b or c 的高度改变，都是改变较高左子树的右侧，其都会引发双旋。

  
  相关代码如下：

				else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
				{
					RotateLR(parent);
				}

	void RotateLR(Node* parent)
	{
		//1、左右双旋涉及到的节点
		Node* subL = parent->_left;
		Node* subLtoR = subL->_right;
		int bf = subLtoR->_bf;

		//2、进行左右双旋:先左旋，再右旋（此处需要注意传入的节点是谁）
		RotateL(subL);
		RotateR(parent);
		
		//3、判断情况，调整平衡因子
		subLtoR->_bf = 0;
		if (bf == 0)//新插入节点即subLtoR节点本身
		{
			parent->_bf = subL->_bf = 0;
		}
		else if (bf = -1)//新插入的节点在subLtoR左子树
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if (bf = 1)//新插入的节点在subLtoR右子树
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}

  
  示意图：

  
  关于平衡因子的调节解释：

  
  
  
  

1.3.2.2.4、右左双旋：新结点插入较高右子树的左侧(右左)

  先右单旋再左单旋

  相关代码如下：

				else if(parent->_bf==2 && cur->_bf==-1)//右左双旋
				{
					RotateRL(parent);
				}

	void RotateRL(Node* parent)
	{
		//1、右左双旋涉及到的节点
		Node* subR = parent->_right;
		Node* subRtoL = subR->_left;
		int bf = subR->_bf;

		//2、右左双旋：先右单旋再左单旋（注意旋转的节点是谁）
		RotateR(subR);
		RotateL(parent);

		//3、判断情况，调节平衡因子
		subRtoL->_bf = 0;
		if (bf == 0)//新插入的节点为subRtoL节点本身
		{
			subR->_bf = parent->_bf = 0;
		}
		else if (bf == -1)//新插入的节点在subRtoL的左子树
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)//新插入的节点在subrtoL的右子树
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

  
  示意图：

  关于平衡因子的调节解释：

1.3.3、整体实现总览与遍历检查

1.3.3.1、遍历检查

  
  1）、中序遍历检查是否满足二叉搜索树
  说明：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。但是不能证明其一定就满足AVL树。

void testAV01()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	t1.InOrder();
}

  
  
  2）、检查是否满足AVL树
  说明：我们可以实现一个求当前结点树的高度的函数，用于获取每个结点的高度差，即平衡因子，若其绝对值不超过2，则说明树是平衡树。
  注意：
  1、此处不能直接使用平衡因子来判断，因为上述实现中，平衡因子是我们手动更新的，无符保证真实实现的树和我们理论上的值相同(即当我们实现错误的时候)。
  2、如果我们实现了平衡因子，那么可以顺带检查一下我们手动更新的平衡因子是否计算正确。
  
  相关代码如下：

public:
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	
private:

	bool _IsBalance(Node* root)
	{
		//若树为空，满足AVL树
		if (root == nullptr)
			return true;

		//判断当前节点的平衡因子是否满足(左右子树高度差<2)
		int leftHeight = Height(root->_left);//求左子树高度
		int rightHeight = Height(root->_right);
		int diff = rightHeight - leftHeight;

		if (diff != root->_bf)
		{//这是为了判断实际树的平衡因子和我们手动更新的平衡因子是否匹配
			cout << root->_kv.first << "：当前结点平衡因子异常" << endl;
			return false;
		}

		//AVL树要满足每个结点的平衡因子都满足高度之差的绝对值不超过1
		return (abs(diff) < 2) 
			&& (_IsBalance(root->_left)) 
			&& (_IsBalance(root->_right));
	}

	int Height(Node* root)//求树的高度
	{
		if (root == nullptr)
			return 0;
		return max(Height(root->_left), Height(root->_right)) + 1;
	}

  
  

//可以使用随机值测试：丰富测试用例
void testAV02()
{
	size_t N = 10000;
	srand(time(0));
	AVLTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		int x = rand();
		t1.Insert(make_pair(x, i));
	}
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

1.3.3.2、整体展示

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;

template<class K,class V>
struct AVLTreeNode
{


	AVLTreeNode<K, V>* _left; //左孩子指针
	AVLTreeNode<K, V>* _right; //右孩子指针
	AVLTreeNode<K, V>* _parent; //父节点指针

	pair<K, V> _kv;//当前结点值，注意这里是键值对
	int _bf;//平衡因子：balance factor

	AVLTreeNode(const pair<K,V>& kv)//构造函数
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)//新增一个结点，其平衡因子初始时为0
	{}
};



template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:


	
	bool Insert(const pair<K, V>& kv)
	{
		//step1:按照二叉搜索树的方式插入新节点
		Ⅰ、查找合适的插入位置
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;		
		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//cur->kv.first==kv.first，key值已存在
			{
				return false;
			}
		}

		Ⅱ、当出了循环，说明cur==nullptr,找到合适位置，开始插入
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else//parent->_kv.first > kv.first
			parent->_left = cur;


		//step2：调整节点的平衡因子
		while (parent)
		{
			Ⅰ、对单次结点进行更新
			if (parent->_left == cur)
				parent->_bf--;//新增在左
			else
				parent->_bf++;//新增在右

			Ⅱ、判断是否需要沿祖先迭代更新
			if (0 == parent->_bf)
			{	//更新后，若parent->_bf==0，则不必向上更新。
				break;
			}
			else if (1 == abs(parent->_bf))
			{
				//更新后，若parent->_bf == 1 or -1，则需要向上更新。
				cur = parent;
				parent = parent->_parent;
			}
			else if (2 == abs(parent->_bf))
			{
				//更新后，若parent->_bf== 2 or -2, 则平衡打破，需要旋转。
				
				if (parent->_bf == 2 && cur->_bf == 1)//左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}

				break;

			}
			else
			{
				assert(false);
			}

		}
		return true;

	}

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

	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:

	bool _IsBalance(Node* root)
	{
		//若树为空，满足AVL树
		if (root == nullptr)
			return true;

		//判断当前节点的平衡因子是否满足(左右子树高度差<2)
		int leftHeight = Height(root->_left);//求左子树高度
		int rightHeight = Height(root->_right);
		int diff = rightHeight - leftHeight;

		if (diff != root->_bf)
		{//这是为了判断实际树的平衡因子和我们手动更新的平衡因子是否匹配
			cout << root->_kv.first << "：当前结点平衡因子异常" << endl;
			return false;
		}

		//AVL树要满足每个结点的平衡因子都满足高度之差的绝对值不超过1
		return (abs(diff) < 2) 
			&& (_IsBalance(root->_left)) 
			&& (_IsBalance(root->_right));
	}

	int Height(Node* root)//求树的高度
	{
		if (root == nullptr)
			return 0;
		return max(Height(root->_left), Height(root->_right)) + 1;
	}

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

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

		//修改链接关系以达成旋转
		parent->_right = subRtoL;
		parent->_parent = subR;

		if (subRtoL)//h>=0，subRtoL可能不存在
			subRtoL->_parent = parent;

		subR->_left = parent;
		if (_root == parent)//parent为原先AVL树的根节点
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		else//parent为原先AVL树的分支节点
		{
			subR->_parent = grendparent;
			if (grendparent->_left == parent)
				grendparent->_left = subR;
			else
				grendparent->_right = subR;
		}
		//处理修改后的平衡因子
		subR->_bf = parent->_bf = 0;
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLtoR = subL->_right;
		Node* grendparent = parent->_parent;

		//处理链接关系
		parent->_left = subLtoR;
		parent->_parent = subL;

		if (subLtoR)
			subLtoR->_parent = parent;

		subL->_right = parent;
		if (_root == parent)
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		else
		{
			subL->_parent = grendparent;
			if (grendparent->_left == parent)
				grendparent->_left = subL;
			else
				grendparent->_right = subL;
		}
		//处理平衡因子
		subL->_bf = parent->_bf = 0;
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLtoR = subL->_right;
		int bf = subLtoR->_bf;

		//左右双旋:先左旋，再右旋
		RotateL(subL);
		RotateR(parent);
		
		//判断情况，调整平衡因子
		subLtoR->_bf = 0;
		if (bf == 0)//插入subLtoR节点本身
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == -1)//插入在subLtoR左子树
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else if (bf == 1)//插入在subLtoR右子树
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}
	

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRtoL = subR->_left;
		int bf = subRtoL->_bf;

		//右左双旋：先右单旋再左单旋
		RotateR(subR);
		RotateL(parent);

		//判断情况，调节平衡因子
		subRtoL->_bf = 0;
		if (bf == 0)//插入subRtoL节点本身
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == -1)//插入在subRtoL的左子树
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)//插入在subrtoL的右子树
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	Node* _root = nullptr;
};

2、红黑树

2.1、基本概念与性质

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

  
  
  2）、红黑树的性质说明

  1、红黑树的每个结点不是红色就是黑色
  2、根节点必须是黑色
  3、红黑树中没有两个连续的红色结点。如果一个结点是红色的，则它的两个孩子结点必须是黑色。
  4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，黑色结点的数目相同。
  5、红黑树每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

  
  说明： 在确保上述性质后，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍 。

  原因：举例极端情况，假设最短路径结点总数为N，其全为黑色结点。那么其最长路径中，黑色结点数量最多有N个，此时，不违背性质3、4的情况下所获得的最长路径就是再插入N-1个红色结点，则最长路径总结点数为2N-1<2N。

2.2、重要框架与特性实现

2.2.1、如何搭建红黑树的结点

  1）、框架搭建
  基本说明：仍旧保持三叉链不变，只是此处我们需要引入结点颜色，这里以枚举来实现。

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)
	{ }

};

  问题：为什么 _col(RED) 默认结点为红色？

  回答：事实上新增一个结点，其为红色还是黑色都是由我们任意控制的。只是在红黑树中，新增一个结点，仍旧要满足红黑树的特性，如果结点是黑色，那么根据性质4，每条路径都将受到影响，后续调整起来相对不便；若新增结点为红色，整体影响范围相对较小。

2.2.2、如何搭建红黑树

  1）、框架搭建
  基本框架如下：

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;

public:
	//……

private:
	Node* _root = nullptr;//根节点
};

2.2.3、红黑树的插入讲解

  同AVL树，红黑树也是在二叉搜索树的基础上，加上一定特性，满足其平衡限制，因此红黑树的插入也可分为两步：
  1、按照二叉搜索树的方式插入新节点
  2、检测新节点插入后，红黑树的性质是否造到破坏
  
  
  

2.3、红黑树的插入

2.3.1、step1：按照二叉搜索树的方式插入新节点

  此处与AVL树实现基本一致，相关注意细节在该部分已说明。

	bool Insert(const pair<K, V>& kv)
	{
		//step1：按照二叉搜索树的方式插入新节点
		Ⅰ、寻找位置
		if (_root == nullptr)//单独处理：根节点为空时
		{
			_root = new Node(kv);
			_root->_col = BLACK;//根节点默认为黑色
			return true;
		}

		//根节点不为空：
		Node* cur = _root;
		Node* parent = nullptr;
		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//cur->kv.first==kv.first，key值已存在
			{
				return false;
			}
		}

		Ⅱ、插入值，调整链接关系
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first < kv.first)//cur插入在parent的右孩子处
			parent->_right = cur;
		else
			parent->_left = cur;//cur插入在parent的左孩子处
		cur->_col = RED;//将插入的结点设置为红色

		//step2:检查新增结点后，是否还满足红黑树性质
		//后续说明

	}

2.3.2、step2：检查新增结点后红黑树性质是否遭到破坏

  1）、三类模式分析

  情况一: cur为红，parent为红，grandparent为黑，uncle存在且为红。
  

  一些说明：
  1、parent为红，根据性质，grandparent一定为黑；
  2、cur可以是parent的左右任意孩子；
  3、cur为红存在两种情况，一是它本身即为新增的结点，二是它的子树中存在新增节点，不断调整迭代，到它这里变红。
  
  处理方法：
  1、将parent、uncle改为黑，grandparent改为红。
  2、判断当前grandparent，若为根，则变回黑色；否不是根，则迭代，把grandparent当成cur，继续向上调整。
  
  
  

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

  一些说明：
  1、若uncle不存在，则cur一定是新增结点，且abcde为空树。原因：反证，若cur不是新增结点，上述中cur、parent连续为红色，则二者必有一黑，以确保性质，但在uncle不存在的情况，这样又不满足性质。
  2、若uncle存在且为黑，则新增结点在cur的任意子树中。原因：uncle为黑，确保了每条路径黑结点必须有两个，新增结点我们设置为红色，若cur为新增，则不符合上述性质。即cur原先为黑结点，是由于其子树颜色迭代，导致它当前为红。
  
  处理方法： 旋转+变色。
  1、旋转grandparent：若parent为grandparent的左孩子，且cur为parent的左孩子(一条直线上)，则对grandparent进行右单旋；若parent为grandparent的右孩子，且cur为parent的右孩子，则对grandparent进行左单旋。
  2、变色： 将parent变黑，grandparent变红。
  

  PS：
  ①为什么情况一不适用：cur为红，若将parent变黑，无论uncle存在或者原先为黑，变相等于当前路径比其它路径多增加一个黑结点，违背了性质。(在情况一中，parent变黑，同时uncle也变黑，不会引发上述问题)
  ②上述这种情况处理完成后，实际上就不用继续向上迭代调整。因为此情况下调整结束后，就满足了红黑树的规则。
  
  
  

  情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

  
  一些说明：
  1、实则为情况二的变形，处理方法同样为旋转+变色，但与之区别在于此处需要双旋。
  2、uncle不存在，cur为新增，uncle存在且为黑，cur为黑，新增结点在cur任意孩子位置，向上迭代使得cur变红。
  
  处理方法： 旋转+变色。
  1、旋转grandparent：若parent为grandparent的左孩子，且cur为parent的右孩子，则对grandparent进行左右单旋；若parent为grandparent的右孩子，且cur为parent的右孩子，则对grandparent进行右左单旋。
  2、变色： 将cur变黑，grandparent变红。
  
  

  2）、相关代码实现
  依照上述，总结可得，红黑树的关键是看uncle：

若uncle存在且为红，变色继续往上处理；
若uncle不存在/存在且为黑，则旋转(四类)+变色。

  基本框架如下：

		//step2:检查新增结点后，是否还满足红黑树性质
		while (parent && parent->_col == RED)//新结点后，无论是cur本身，还是迭代后变色，如果parent、cur颜色皆红，则违反性质3：不能有连续的红结点，因此需要调整
		{
			//固定:
			Node* grandparent = parent->_parent;
			assert(grandparent && grandparent->_col == BLACK);//grandparent存在且为黑

			//关键看叔叔，此处对uncle和parent在不同位置分别处理
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				//……
				//三种情况分别处理
			}
			else//parent == grandparent->_right
			{
				Node* uncle = grandparent->_left;
				//……
				//三种情况分别处理
			}

		}

  详细实现见下述总览部分。
  
  
  

2.3.3、整体实现总览与遍历检查

2.3.3.1、遍历检查

  1）、如何检查当前树是否为红黑树？
  方案一：看高度。
  分析：如果使用最长路径和最短路径高度差不超过二倍来比较。存在一个问题，满足该高度差，不一定代表其结点颜色满足红黑树需求。
  
  方案二：看结点颜色。
  1、检查根节点颜色为黑。
  2、检查红色结点不连续：遍历结点，若当前结点为红色，则比较其与其孩子结点。
  3、检查每条路径的黑结点数量。
  
  2）、写法说明

写法一：

	bool IsBalance()
	{
		//1、检查根节点
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
		{
			cout << "根节点不满足黑色" << endl;
			return false;
		}
		
		//2、检查每条路径的黑色结点数目
		int blackNum = 0;//用于统计树中黑色结点数
		return PrevCheck(_root, blackNum);
	}

private:
	bool PrevCheck(Node* root, int blackNum)
	{
		if (root == nullptr)
		{
			cout << blackNum << endl;
			return true;
		}

		if (root->_col == BLACK)
			++blackNum;
		
		//3、检查红色结点是否连续	
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum)
			&& PrevCheck(root->_right, blackNum);
	}

  演示结果：

  问题说明：
  此处我们遍历到每条路径末尾时，将当前路径的黑色结点树统计并打印出来，这样存在一个问题，需要我们核对每条路径的黑色结点是否匹配，这样当路径很多时，我们手动核对处理起来麻烦，不具有自动和高效性。

		if (root == nullptr)
		{
			cout << blackNum << endl;
			return true;
		}

  因此需要对其修改。
  
  

写法二：

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
		{
			cout << "根节点不满足黑色" << endl;
			return false;
		}

		//以红黑树中任意一条路径的黑色结点数作为基准值，其余路径的黑色结点与其比较
		int basicalNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++basicalNum;
			cur = cur->_left;//此处这种写法是以红黑树中最左边的路径作为基准路径
		}
		int blackNum = 0;//用于统计树中黑色结点数
		return PrevCheck(_root, blackNum, basicalNum);
	}

private:
	bool PrevCheck(Node* root, int blackNum, int basicalNum)
	{
		if (root == nullptr)
		{
			if (blackNum == basicalNum)
				return true;
			else
				{
					cout << "某条路径黑色结点数不匹配" << endl;
					return false;
				}
		}

		if (root->_col == BLACK)
			++blackNum;
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, basicalNum)
			&& PrevCheck(root->_right, blackNum, basicalNum);
	}

写法三：

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
		{
			cout << "根节点不满足黑色" << endl;
			return false;
		}

		int BasicalNum = 0;//用于确定基准值：前序遍历时的第一条路径
		int blackNum = 0;//用于统计树中黑色结点数
		return PrevCheck(_root, blackNum, BasicalNum);
	}

private:
	bool PrevCheck(Node* root, int blackNum, int& basicalNum)
	{
		if (root == nullptr)
		{
			if (basicalNum == 0)
			{
				basicalNum == blackNum;
				return true;
			}
			else
			{
				if (blackNum == basicalNum)
					return true;
				else
				{
					cout << "某条路径黑色结点数不匹配" << endl;
					return false;
				}
			}
		}

		if (root->_col == BLACK)
			++blackNum;
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, basicalNum)
			&& PrevCheck(root->_right, blackNum, basicalNum);
	}

2.3.3.2、整体总览

#pragma once
#pragma once
#include<assert.h>
#include<iostream>
#include<utility>
using namespace std;



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>
class RBTree
{
	typedef RBTreeNode<K, V> Node;

public:
	bool Insert(const pair<K, V>& kv)
	{
		//step1：按照二叉搜索树的方式插入新节点
		Ⅰ、寻找位置
		if (_root == nullptr)//单独处理：根节点为空时
		{
			_root = new Node(kv);
			_root->_col = BLACK;//根节点默认为黑色
			return true;
		}

		//根节点不为空：
		Node* cur = _root;
		Node* parent = nullptr;
		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//cur->kv.first==kv.first，key值已存在
			{
				return false;
			}
		}

		Ⅱ、插入值，调整链接关系
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first < kv.first)//cur插入在parent的右孩子处
			parent->_right = cur;
		else
			parent->_left = cur;//cur插入在parent的左孩子处
		cur->_col = RED;//将插入的结点设置为红色

		//step2:检查新增结点后，是否还满足红黑树性质
		while (parent && parent->_col == RED)//新结点后，无论是cur本身，还是迭代后变色，如果parent、cur颜色皆红，则违反性质3：不能有连续的红结点，因此需要调整
		{
			//固定:
			Node* grandparent = parent->_parent;
			assert(grandparent && grandparent->_col == BLACK);//grandparent存在且为黑

			//关键看叔叔，此处对uncle和parent在不同位置分别处理
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				
				//情况一
				if (uncle&& uncle->_col == RED)//叔叔存在且为红
				{
					//处理方法：变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else //叔叔不存在或叔叔存在且为黑：情况二+情况三
				{
					//处理方法：旋转+变色（旋转有四类）

					//Ⅰ：情况二：p在g左，c在p左，成直线。右单旋+g变色为红，p变色为黑
					if (cur == parent->_left)
					{
						RotateR(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
					else//Ⅱ：情况三：p在g左，c在p右，成折线。左右双旋+g变色为红，c变色为黑
					{
						RotateL(parent);
						RotateR(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK;
					}
					break;//情况二、情况三完成调整后，满足红黑树规则，不必继续向上调整
				}
			}
			else//parent == grandparent->_right
			{
				Node* uncle = grandparent->_left;

				//情况一
				if (uncle&& uncle->_col == RED)//叔叔存在且为红
				{
					//处理方法：变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else //叔叔不存在或叔叔存在且为黑：情况二+情况三
				{
					//处理方法：旋转+变色（旋转有四类）

					//Ⅰ：情况二：p在g右，c在p右，成直线。左单旋+g变色为红，p变色为黑
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
					else//Ⅱ：情况三：p在g右，c在p左，成折线。右左双旋+g变色为红，c变色为黑
					{
						RotateR(parent);
						RotateL(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK;
					}
					break;//情况二、情况三完成调整后，满足红黑树规则，不必继续向上调整
				}
			}

		}
		_root->_col = BLACK;
		return true;

	}

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

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
		{
			cout << "根节点不满足黑色" << endl;
			return false;
		}

		写法一：
		以红黑树中任意一条路径的黑色结点数作为基准值，其余路径的黑色结点与其比较
		//int basicalNum = 0;
		//Node* cur = _root;
		//while (cur)
		//{
		//	if (cur->_col == BLACK)
		//		++basicalNum;
		//	cur = cur->_left;//此处这种写法是以红黑树中最左边的路径作为基准路径
		//}

		int BasicalNum = 0;//用于确定基准值：前序遍历时的第一条路径
		int blackNum = 0;//用于统计树中黑色结点数
		return PrevCheck(_root, blackNum, BasicalNum);
	}

private:
	bool PrevCheck(Node* root, int blackNum, int& basicalNum)
	{
		if (root == nullptr)
		{
			if (basicalNum == 0)
			{
				basicalNum == blackNum;
				return true;
			}
			else
			{
				if (blackNum == basicalNum)
					return true;
				else
				{
					cout << "某条路径黑色结点数不匹配" << endl;
					return false;
				}
			}
		}

		if (root->_col == BLACK)
			++blackNum;
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, basicalNum)
			&& PrevCheck(root->_right, blackNum, basicalNum);
	}

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

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

		//修改链接关系以达成旋转
		parent->_right = subRtoL;
		parent->_parent = subR;

		if (subRtoL)//h>=0，subRtoL可能不存在
			subRtoL->_parent = parent;

		subR->_left = parent;
		if (_root == parent)//parent为原先AVL树的根节点
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		else//parent为原先AVL树的分支节点
		{
			subR->_parent = grendparent;
			if (grendparent->_left == parent)
				grendparent->_left = subR;
			else
				grendparent->_right = subR;
		}
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLtoR = subL->_right;
		Node* grendparent = parent->_parent;

		//处理链接关系
		parent->_left = subLtoR;
		parent->_parent = subL;

		if (subLtoR)
			subLtoR->_parent = parent;

		subL->_right = parent;
		if (_root == parent)
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		else
		{
			subL->_parent = grendparent;
			if (grendparent->_left == parent)
				grendparent->_left = subL;
			else
				grendparent->_right = subL;
		}
	}

	Node* _root = nullptr;
};

  
  
  
  
  
  
  
  文章来源地址https://www.toymoban.com/news/detail-438528.html

到了这里，关于【ONE·C++ || set和map（二）：AVL树和红黑树】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！