c++——map、set底层之AVL树（动图演示旋转）

在上一篇博客里面我们提到了set和map的使用；这篇博客重点介绍他们的底层逻辑

c++之set和map——关联容器（非顺序容器——list、vector）

---

前言

我们之前学了过二叉搜索树，二这里的AVL也是一种搜索树，当我们二叉搜索树发生偏移时，搜索时间就会边长，就不树logN了，变成N；而AVL就修复了这一点。

---

一、底层结构

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

二、AVL 树

1.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年

发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$，搜索时间复杂度O($log_2 n$)

2.AVL树节点的定义

代码如下（示例）：

template<class T>
struct AVLTreeNode
{
 AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
 , _data(data), _bf(0)
 {}
 AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
 AVLTreeNode<T>* _pRight;  // 该节点的右孩子
 AVLTreeNode<T>* _pParent; // 该节点的双亲
 T _data;
 int _bf;                  // 该节点的平衡因子
};

3、AVL树的插入

AVL的插入和搜索二叉树一样，只不过我们需要处理旋转问题，控制这棵树不要一边高一边低

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
 
// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
    // ...
    
    // 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
破坏了AVL树
    //   的平衡性
    
 
 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
  
 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
成0，此时满足
     AVL树的性质，插入成功
  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
新成正负1，此
     时以pParent为根的树的高度增加，需要继续向上更新
  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
行旋转处理
 
	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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
 
		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
 
			if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 需要旋转处理 -- 1、让这颗子树平衡 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;
	}

三、 AVL树的旋转

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

1. 新节点插入较高左子树的左侧---左左：右单旋

在插入之前我们的左侧是比较高的，也就是左节点高，以为我们定义这个平衡因子时是将左边高定义为负，右边高定义为正；

当左边高再在左边插入节点时，就会让左边更高了，原本左边高，这里的高度差为-1，当再次向左侧插入节点时，高度差就为-2了，这时我们就需要进行旋转这颗树了；如何旋转呢？

代码实现： 

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
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
 
	subL->_bf = parent->_bf = 0;
}

2. 新节点插入较高右子树的右侧---右右：左单旋

 左单旋就和右单旋反过来，但右边高时，在右边在插入节点，那么右边较左边的高度差就是2了，这个时候就需要进行左旋转；

代码实现：

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 (ppnode == nullptr)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
 
		subR->_parent = ppnode;
	}
 
	parent->_bf = subR->_bf = 0;
}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

1、subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2、subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3、经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树。

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
 
	RotateL(parent->_left);
	RotateR(parent);
 
	if (bf == 1)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋 

1. 由于插入新结点后，可能并不会立即进行旋转操作，而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作，因此用长方形表示下面的子树。
2. 动图中，在b子树当中新增结点，或是在c子树当中新增结点，均会引发右左双旋，动图中以在c子树当中新增结点为例。

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
 
	RotateR(parent->_right);
	RotateL(parent);
 
	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 0)
	{
		subR->_bf = 0;
		parent->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

 四、验证AVL树

void Test_AVLTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		/*	if (e == 14)
			{
			int x = 0;
			}
		 */
 
		t1.Insert(make_pair(e, e));
		cout << e << "插入：" << t1.IsBalance() << endl;
	}
 
	t1.InOrder();
	cout << t1.IsBalance() << endl;
}

通过高度变化验证是否平衡

int _Height(Node* root)
{
	if (root == NULL)
		return 0;
 
	int leftH = _Height(root->_left);
	int rightH = _Height(root->_right);
 
	return leftH > rightH ? leftH + 1 : rightH + 1;
}
 
bool _IsBalance(Node* root)
{
	if (root == NULL)
	{
		return true;
	}
 
	int leftH = _Height(root->_left);
	int rightH = _Height(root->_right);
 
	if (rightH - leftH != root->_bf)
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}
 
	return abs(leftH - rightH) < 2
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}

---

总结

假如以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为根的子树个高度降低，已经平衡，不需要再向上更新。