[数据结构与算法]数据结构--AVL树与红黑树

我们在上一章中初步认识到了set与map，了解了他们的使用，但是仅仅隐约的窥见了他们的底层实现，而这一章我们一起了解下他们的底层实现，以及数据结构较为复杂的部分，AVL树与红黑树

set与map的底层结构

前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是： 其底层都是按照二叉搜索树来实现的 ，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N) ，因此 map 、 set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

AVL 树

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当 于在顺序表中搜索元素，效率低下 。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之 差的绝对值不超过 1( 需要对树中的结点进行调整 ) ，即可降低树的高度，从而减少平均搜索长度。

它的左右子树都是 AVL 树

左右子树高度之差 ( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)

AVL树节点的定义

template<class K, class V>
struct AVTreeNode
{
	AVTreeNode<K, V>* _left;
	AVTreeNode<K, V>* _right;
	AVTreeNode<K, V>* _parent;

	int _bf;  // balance factor  平衡因子

	pair<K, V> _kv;//定义节点
	
	AVTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

根据上面的AVLTree，我们给出了左指针，右指针，以及父亲指针，还有我们的平衡因子

AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

3.判断平衡因子是否合法，合法则完成插入，不合法则进行旋转处理，之后完成插入

1.我们的AVLTree本质上还是二叉搜索树，所以我们可以先进行二叉搜索树的插入，而后进行调整，从而完成AVLTree的插入

2.我们在完成原始插入之后，还需要更新平衡因子，也就是更新当前树左右两边高度差，我们一起来看看是如何进行更新的

?对于这种情况而言，我们插入一个节点到8的左边，平衡了8左右两边的高度，使8的平衡因子变为了0，7的平衡因子因为插入节点后并没有增加右树高度，所以不变，这样的情况是不需要进行旋转的，正常插入即可

?对于这种情况，我们在树的缺口处6的右边插入了一个节点，此时6的平衡因子因为右树加了一个节点所以变为了1，7的平衡因子因为左树高度加了1，所以7平衡因子减一变为了0，证明7左右两边平衡了，而其他节点的平衡因子不变，平衡因子没有超过2/-2的，所以这种情况也是正常的，直接插入即可

?那我们再来看看这样的情况，在9的右边再插入了一个结点，我们可以发现，此时的二叉树已经出现了不平衡，8的左右高度差值变成了2，我们来分析一下，在9的右边插入结点，9的平衡因子+1，向上更新，8的平衡因子+1，此时8的平衡因子变为了2，说明8的右树高度比左树高度大了2，不平衡，所以要进行旋转调整位置使其平衡，我么一会再说如何进行旋转调整，我们先来总结下这三种插入方式

1.cur是parent的左，parent->bf--，cur是parent的右，parent->bf++

2.更新完parent的bf，如果parent->bf==0，说明parent高度不变，更新结束，插入完成，解释：说明更新之前，parent的bf为1或者-1，现在变为了0，说明把矮的那一边填上了，说明我们的高度不变，不对上层造成影响

3.更新完parent的bf，如果parent->bf==1or-1，说明parent的高度变了，需要继续向上更新，解释：说明更新前，parent的bf为0，现在变成了1or-1，说明变高了，对上层有影响，需要向上更新

4.更新完parent的bf，如果parent->bf==2or-2，则说明parent所在的子树出现了不平衡，需要旋转处理

bool Insert(const pair<K, V>& kv)
	{
		// 1、先按搜索树的规则进行插入，这里不一样的地方是每次移动之后还需要更新父指针
		if (_root == nullptr)//若树为空，则直接插入
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;//初始化父指针
		Node* cur = _root;//初始化cur
		while (cur)//循环cur，开始寻找插入位置
		{
			if (cur->_kv.first > kv.first)//向左找
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)//向右找
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)//链接插入的节点与原来的树
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 2.更新平衡因子
		while (parent)//循环父节点
		{
			if (cur == parent->_right)//当插入在了parent的右边
				parent->_bf++;//平衡因子++
			else
				parent->_bf--;//左边则--

			if (parent->_bf == 0)//当平衡因子更新为0时
			{
				// 说明parent所在的子树的高度不变，更新结束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)//当平衡因子更新为-1or1时
			{
				// 说明parent所在的子树的高度变了，继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// parent所在的子树出现不平衡了，需要旋转处理。
				// 1、旋转前提是保持它依旧是搜索二叉树
				// 2、旋转成平衡树
				if (parent->_bf == 2)//当父节点的平衡因子变为2时，进行旋转
				{
					if (cur->_bf == 1)//子节点的平衡因子变为1
					{
						RotateL(parent);
					}
					else if (cur->_bf == -1)
					{
						RotateRL(parent);
					}
				}
				else if (parent->_bf == -2)//-2也进行旋转
				{
					if (cur->_bf == -1)
					{
						RotateR(parent);
					}
					else if (cur->_bf == 1)
					{
						RotateLR(parent);
					}
				}

				// 旋转完成后，parent所在的树的高度恢复到了，插入节点前高度
				// 如果是子树，对上层影响，更新结束。
				break;
			}
		}

		return true;
	}

AVL树的旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL 树的旋转分为四种：

左单旋

左单旋是针对新节点插入在右子树的右边，需要向左旋转调整的情况

?我们将结点插入在了c的下面，此时30的平衡因子变为2，不平衡了，所以就要对30进行旋转处理，具体做法是将60的左孩子变为30的右孩子，而后将30链到60的左边，此时便完成了旋转，在保证平衡因子绝对值小于等于1的情况下维持了搜索树左孩子小于根，右孩子大于根的特性

?那么我们体现在代码上是如何实现的呢

首先，我们通过相对关系，设置了3个指针，parent，subR，subRL，去操作这颗树，去链接相应的结点，链接过后去处理parent结点，而后分之前的parent是否为根两种情况，为根则直接置subR为新根，不为根则向上移动，链接到整棵树中，随后更新平衡因子

void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;//初始化subR指针
		Node* subRL = subR->_left;//初始化subRL指针
		//开始旋转
		parent->_right = subRL;//让parent的右指针指向subRL

		if (subRL)//当subRL存在时，也就是subR存在左子树时
		{
			subRL->_parent = parent;//处理subRL的父指针，使其指向parent
			                        //若subRL不存在，则不需要处理
		}
		subR->_left = parent;//将parent连到subR的左边
		Node* ppNode = parent->_parent;//定义ppNode，为parent的上层parent
		parent->_parent = subR;//将subR赋给ppNode

		//1.原来parent是这棵树的根，现在subR为根
		//2.parent为根的树只是整棵树的子树，改变连接关系，那么subR要顶替他的位置

		if (_root == parent)//当parent为根节点
		{
			_root = subR;//则subR变为根
			subR->_parent = nullptr;//subR的parent置空
		}
		else//当parent不为空，应继续向上
		{
			if (ppNode->_left == parent)//当parent为ppNode的左树
			{
				ppNode-> _left = subR;//上移ppNode
			}
			else
			{
				ppNode->_right = subR;//上移ppNode
			}
			subR->_parent = ppNode;//上移ppNode
		}
		parent->_bf = subR->_bf = 0;//将平衡因子置0
	}

右单旋

?我们为了旋转，引入subL，subLR，parent指针

?右单旋和左单旋原理一致，只是右单旋的条件变为了在左子树插入，同样的，将b链到60的左子树再将60链到30的右子树即可

void RotateR(Node* parent)
		{
			Node* subL = parent->_left;//初始化subL
			Node* subLR = subL->_right;//初始化subLR

			parent->_left = subR;//subR链到parent左边
			if (subLR)//当subLR存在时
			{
				subRL->_parent = parent;//更新parent连接关系
			}
			subL->_right = parent;//parent链接到subL的右边
			Node* ppNode = parent->_parent;//定义ppNode
			parent->_parent = subL;//subL赋给ppNode

			if (_root == parent)//当之前的parent为根时
			{
				_root = subL;//让subL为根
				subL->_parent = nullptr;
			}
			else//与整棵树的链接
			{
				if (ppNode->left == parent)//
				{
					ppNode->left = subL;
				}
				else
				{
					ppNode->_right = subL;

				}
				subL->_parent = ppNode;
			}
			subL->_bf = parent->_bf = 0;//平衡因子置空
		}

左右双旋

左右双旋这种情况针对的就是将新节点插入到了左子树的右侧，形成了折线形插入的情况

?我们引入parent，subR，subRL,指针来进行操作

?先对30进行左旋，再对90进行右旋，即可完成

也有可能是这种情况

?只是插入位置略有差异，这棵树也是先对30进行左旋，再对90进行右旋

b或者c的插入导致高度变化都会引发双旋，结构都是一样的，但最终平衡因子不一样

也有可能为这样

?当我们左子树右侧没有结点，插入的结点就插在左子树的右侧本身时，同样的，也是先对30进行左旋，再对90进行右旋，即可完成旋转，总的来说，当我们将parent，subL，subLR指针赋给各个结点时，总是先对subL指针所在节点左旋，subLR指针右旋，最后进行平衡因子的调整，即可完成

void RotateLR(Node* parent)//左右双旋
		{
			Node* subL = parent->_left;//初始化subL
			Node* subLR = subL->_right;//初始化subLR
			int bf = subLR->_bf;//初始化bf，平衡因子，也为最后根节点的平衡因子

			RotateL(subL);//先对subL进行左旋
			RotateR(parent);//再对parent进行右旋

			if (bf == 1)//更新平衡因子，这里检查的是根节点的平衡因子，这里是第二种情况
			{
				parent->_bf = 0;
				subL->_bf = -1;
				subL->_bf = 0;
			}
			else if (bf == -1)//第一种情况
			{
				parent->_bf = 1;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
			else if (bf == 0)//最后一种情况
			{
				parent->_bf = 0;
				subL->_bf = 0;
				subLR->_bf = 0;
			}
		}

右左双旋

同我们的左右双旋类似，这种情况就是针对右子树的左端插入数据

?第一种情况

?第二种情况

?第三种情况

?在这种情况我们选择引入parent，subR，subRL指针

void RotateRL(Node* parent)//右左双旋
		{
			Node* subR = parent->_right;//初始化subR
			Node* subRL = subR->_left;//初始化subRL
			int bf = subRL->_bf;//根节点平衡因子

			RotateR(parent->_right);//对subR进行右旋
			Rotatel(parent);//对parent进行左旋

			if (bf == -1)//第一种情况更新平衡因子
			{
				parent->_bf = 0;
				subR->_bf = 1;
				subRl->_bf = 0;
			}
			else if (bf == 1)//第二种情况更新平衡因子
			{
				subR->_bf = 0;
				parent->_bf = -1;
				subRL->_bf = 0;
			}
			else if (bf == 0)//第三种情况更新平衡因子
			{
				subR->_bf = 0;
				parent->_bf = 0;
				subRL->_bf = 0;
			}
		}

上面便是AVLTree的旋转，总的来说旋转的精髓就在于改变连接关系，注意parent，最后更新平衡因子

总结：

假如以 pParent 为根的子树不平衡，即 pParent 的平衡因子为 2 或者 -2 ，分以下情况考虑

1. pParent 的平衡因子为 2 ，说明 pParent 的右子树高，设 pParent 的右子树的根为 pSubR

当 pSubR 的平衡因子为 1 时，执行左单旋

当 pSubR 的平衡因子为 -1 时，执行右左双旋

2. pParent 的平衡因子为 -2 ，说明 pParent 的左子树高，设 pParent 的左子树的根为 pSubL

当 pSubL 的平衡因子为 -1 是，执行右单旋

当 pSubL 的平衡因子为 1 时，执行左右双旋

旋转完成后，原 pParent 为根的子树个高度降低，已经平衡，不需要再向上更新

AVLTree的删除

AVL树的性能

AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1 ，这样可以保证

查询时高效的时间复杂度，即logN。但是如果要对AVL 树做一些结构修改的操作，性能非常低下，比如： 插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的( 即不会改变 ) ，可以考虑 AVL 树， 但一个结构经常修改，就不太适合

红黑树

红黑树的概念

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

?红黑树的性质

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

2. 根节点是黑色的?

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的?

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色点?

5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )

其实正是因为红黑树整体的两端节点黑色，中间节点才可能为红的特点，才使得红黑树的最长路不大于最短路的二倍

由此我们也可以看出，红黑树其实相对于AVLTree而言，AVLTree为严格的平衡搜索树，而红黑树则不是严格的平衡搜索树，仅满足最短路径不小于最长路径的一半

红黑树节点的定义

enum Colour
{
	BLACK,
	RED,
};

template<class K,class V>
class RBTreeNode
{
	RBTreeNode<K, V>* _left;//左指针
	RBTreeNode<K, V>* _right;//右指针
	RBTreeNode<K, V>* _parent;//父指针

	pair<K, V> _kv;//键值对
	Colour _col;//颜色
};

我们的红黑树与AVLTree的区别在于我们将平衡因子更换为了颜色，去通过改变颜色，满足红黑树的特性，来维持尽量平衡

红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点， pLeft 域指向红黑树中最小的节点，_pRight 域指向红黑树中最大的节点，如下

?红黑树的插入操作

第一点很简单，我们只需要像之前AVLTree一样，完成插入即可

第二点则需要分情况讨论

因为 新节点的默认颜色是红色 ，因此：如果 其双亲节点的颜色是黑色，没有违反红黑树任何性质 ，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点 ，此时需要对红黑树分情况来讨论

情况一: cur为红，p为红，g为黑，u存在且为红

?cur和p均为红，违反了性质三

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

这种情况主要就是我们插入的cur上面是红色节点，插入会违反(红节点的两个子节点为黑色这一性质)，所以我们需要将p变为黑色，但是这样就违反了（每条路上黑色节点数量相同这一性质），所以我们还需要将u变为黑色，而此时我们完成了基本变化，又迎来了两种情况，这棵树g为根节点，直接将g变黑，完成插入；g不为根节点，上面还有，这种情况我们就需要像刚才一样，再上一层，将g理解为插入的结点，上层结点的p与u继续变红，直到最上层根，类似于递归，层层向上

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

p 为 g 的左孩子， cur 为 p 的左孩子，则进行右单旋转；相反，

p 为 g 的右孩子， cur 为 p 的右孩子，则进行左单旋转

p 、 g 变色 --p 变黑， g 变红

我们来看一下这种情况，当我们插入的结点cur的上层p为红色，u为黑或者空时，此时违反（红色结点的子节点为黑这一性质）但是我们又不能直接将p变黑，因为u本身就为黑，没法同p一起维持本层的黑节点个数相同，所以我们就需要想别的办法，进行旋转，上图我们进行了右单旋，并将最后处在根节点的p的颜色变为了黑，pg颜色更换，保持了右路的黑色节点数量与之前相同

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

?

这种情况其实也是情况2，就如同我们的AVLTree中的双旋是一样的，插入节点在折线部分，所以我们先需要进行一次旋转，图中就需要先进行一次左旋，变为了情况2，后进行右旋完成插入

其实我们还有一种cur上层的p为黑色的情况，因为我们如果是黑色的话，正好插入不影响其红黑树结构，所以我们不进行处理

接下来我们进行代码演示

?这对应的就是我们的第一种情况

?这是我们的第二种和第三种情况

?接下来是完整插入代码

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		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 = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//上面为一般搜索树的插入

		//新增红色节点
		cur->_col = RED;//新增节点为红色节点的原因是相对于插入的是黑色而言，
		//插入红色更贴近于不破坏红黑树的结构,插入黑色的话，破坏了每条道路黑色节点数量相等的条件
		//且若想弥补，耗费非常大，得不偿失,反倒插入红色，改变较小，所以这里选择红色
		while (parent&&parent->_col == RED)//当父节点存在且为红，开始循环，当parent节点为黑则直接完成插入
		{
			Node* grandfather = parent->_parent;//初始化爷爷节点
			if (grandfather->_left = parent)//当父节点在爷爷节点的左侧时
			{
				Node* uncle = grandfather->_right;//叔叔节点就在爷爷节点的右侧

				if (uncle&&uncle->_col = RED)//当叔叔节点存在且红时
				{
					parent->_col = uncle->_col = BLACK;//将父节点与叔叔节点变黑
					grandfather->_col = RED;//爷爷节点变红

					cur = grandfather;//向上循环
					parent = cur->_parent;
				}
				else//当叔叔节点不存在或者为黑时
				{
					if (cur == parent->_right)//当结点插入到右子树时
					{
						RotateL(parent);//进行左旋
						swap(parent, cur);//而后交换parent与cur
					}
					RotateR(grandfather);//对爷爷节点进行右旋，这种情况包含了右单旋
					grandfather->_col = RED;//对颜色进行调整
					parent->_col = BLACK;

					break;
				}

			}
			else{//当父节点在爷爷节点的右侧时
				Node* uncle = grandfather->_left;//叔叔节点就在爷爷节点的左侧
				if (uncle&& uncle->_col == RED)//叔叔结点存在且颜色为红
				{
					parent->_col = uncle->_col = BLACK;//父亲与叔叔颜色置黑
					grandfather->_col = RED;//爷爷颜色变红
					
					cur = grandfather;//向上移动
					parent = cur->_parent;
				}
				else//当叔叔节点不存在或者颜色为黑时
				{
					if (cur == parent->_left)//插入位置为parent的左侧
					{
						RotateR(parent);//parent右旋
						swap(parent, cur);//交换parent与cur
					}
					RotateL(grandfather);//grandfather左旋
					grandfather->_col = RED;//爷爷节点颜色变红
					parent->_col = BLACK;//父亲节点颜色变黑
				}
			}
		}
		_root->_col = BLACK;//始终保持根节点为黑色
		return true;//完成插入
	}

这就是我们红黑树的插入，其实相对于我们的AVLTree来说，红黑树反倒是更为简洁，且更为高效的，因为其旋转的次数得到了减少，没有平衡因子那么麻烦

红黑树与AVL树的比较

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

红黑树的应用

1. C++ STL 库 -- map/set 、 mutil_map/mutil_set

2. Java 库

3. linux 内核

4. 其他一些库