【数据结构】AVL树和旋转

本章要分享的内容是AVL树，所有代码会放在最后。

目录

1.AVL树的概念

2.AVL树的实现

2.1结点的设计

2.2插入

?2.3更新平衡因子

2.3.1左单旋

2.3.2右单旋

2.3.3.双旋

3.AVL树测试

4.全部代码

?4.1.AVL.h

4.2.test.h?

---

在之前我们接触过二叉树和二叉搜索树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率便会降低。

1.AVL树的概念

AVL树的要求是一颗树中的左右高度差的绝对值不超过1，包括这颗树中所有的子树。

上图为简单的AVL树，左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。

平衡因子也就是右树减去左树的高度，格局上图中所标识的0、1、-1即为平衡因子。

引入平衡因子的概念意在可以简单的判断这棵树是否为AVL树，树中的平衡因子若都为0、1、-1那即为AVL树。

注意：平衡因子只是一种AVL树的实现方式，并不是必须的。

所以在了解这样的树之后它的时间复杂度为O(logN)，因为AVL树控制了高度差，所以插入的数据基本上都是在最后两层，与最开始我们接触过的完全二叉树相似。

2.AVL树的实现

2.1结点的设计

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

在这里我的代码是将每个结点存放了五个值，分别为左右结点和父亲节点（其都为<key,value>的结构）、pair值、平衡因子。

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

private:
	Node* _root = nullptr;

};

将以上AVL树的结点都重定义为Node方便我们后续的使用，并且使用重定义的结点定义根节点。

我们只需在public中添加我们需要对AVL树的操作即可。

2.2插入

AVL的插入与二叉搜索树的插入逻辑大致上相同，但是还是有一点不同

这里的代码只是为了梳理逻辑，并不完全，后续还会涉及到结点旋转的问题。

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//如果根节点为空，就让根节点成为插入的第一个结点
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;//新开结点parent
		Node* cur = _root;//新开结点cur，并初始化为根结点

		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为空
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}


		return true;
	}

可以看到逻辑上分为两个部分，一个是cur的结点中有值，一个是cur结点没有值；

这里插入时使用的是三叉链表的结构

?2.3更新平衡因子

AVL树中可以引入平衡因子来实现，并且不能超过1的绝对值，所以我们需要讨论如何更新平衡因子。

新增结点可能会影响祖先

1.如果子树的高度不变，就不会继续向上影响祖先

2.如果子树高度变化，就会继续向上影响祖先

首先新增的结点可能会影响祖先，不会影响到旁支结点。?

如果新插入的结点在如下红色圆圈的位置，那么 值为8的结点的平衡因子要从1更新为0

如果我们没有将结点插入在左树，而是插入在右树（如下图）

此时结点为9的高度发生变化，平衡因子也发生变化（p为parent，c为cur）

9的高度发生变化，它的祖先节点的平衡因子也发生变化

就这样一路更新上去每个结点的平衡因子都会更新。

但是我们发现8这个结点的平衡因子已经出现了问题，它的绝对值超过了1，所以我们需要对这颗子树进行处理。

那我们有如下结论

1.新增结点在左子树，父亲的平衡因子减一（bf--），如下图

?2.新增结点在右子树，亲的平衡因子加一（bf++），如下图

那么如何将平衡因子继续向下更新呢？

有如下判断方法

1.在更新后，父亲的平衡因子等于0，父亲所在的子树高度不变，就不用继续向上更新，插入结束。

ps:再插入节点前，父亲的平衡因子等于 1 或者?-1 ，一边高一边低，新插入的结点填上了低的一部份

2.如果父亲的平衡因子更新之后等于 1?或者? -1，父亲所在的高度变化，必须继续向上更新

ps:插入结点前，父亲的平衡因子两边一样高，插入导致高度变化

代码如下

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 < key)//判断我们定义的k,v结构中所在树中的k是否小于我们所插入的key
			{
				parent = cur;
				cur = cur->_right;//如果key大于树中结点的值就走右边
			}
			else if (cur->_kv.first > key)
			{
				parent = cur;
				cur = cur->_left;//key小于树中结点的值就走左边
			}
			else
			{
				return false;//相等时结束
			}
		}

		//运行至当前位置时则说明cur为空
		cur = new Node(kv);
		if(parent->_kv.first < key)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else if (parent->_kv.first > key)
		{
			parent->_left = cur;
			cur->_parent= parent;
		}


		while (parent)
		{
			//更新平衡因子
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;//注意cur和parent都是指针，这里是改变指针的指向
				parent = parent->_parent;
			}
			else if(parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转调整
				
			}
			else
			{
				assert(false);
			}
		}

		return true;

	}

3.如果父亲的平衡以你在更新后，等于 2 或者 -2 ，父亲所在的子树违反规则，需要旋转调整处理

可以看到这里的平衡因子出现了2，违反了AVL树的规则，这时就要进行旋转操作

首先我们要明确旋转的目的

1.使树的左右均衡

2.保持搜索树的规则

所以我们可以对以上树进行以下旋转

2.3.1左单旋

此树旋转较为简单，只需要用二叉搜索树的知识来判断谁来做父亲节点

也就是将2的左树（为空），放到了1的右树，同时将1又作为2的左树

如果我们增加一些难度，将树多添加一些结点

我们对其进行旋转后会得到以下结构图

这里的结点13比9大，但是比15小，13更是和添加到9的左树当中

和上面三个结点的树相似，将15的左结点13变成了9的右节点，同时将结点为9的树一并作为了15的左子树。

这样的旋转规律就被称为左单旋。

如下都是左单旋的抽象图。

抽象图就代表了一类问题的解决的大体思想，实际的h有很多情况，一一列举出来显然是非常困难。

以下是左单旋调整的代码

，图为以下代码中结构的命名。

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

		parent->_right = subRL;
		subR->_left = parent;
	}

?当如上代码运行之后，结构会更新成下图所示

此时我们还需要处理parent和根结点，完整的代码如下

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

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentPARENT = parent->_parent; 

		parent->_parent = subR;
		if (subR)
			subR->_parent = parent;

		if (_root = parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentPARENT->_left == parent)
			{
				parentPARENT->_left = subR;
			}
			else
			{
				parentPARENT->_right = subR;
			}
			subR->_parent = parentPARENT;
		}
		parent->_bf = subR->_bf = 0;
	}

上面代码中我们不仅要考虑到根节点_root是否为空的情况，还需要考虑到如何保留并找到根节点，如何对根节点进行旋转和交换，此时我们需要新开一个节点方便对旋转的结点进行操作

?同时，还需要保留三叉链表的思想，以防止我们修改指针的指向。

2.3.2右单旋

可以看到结构图和左单旋只是左右互换，并没有太多本质上的差异，所以代码的逻辑也没有特别困难

代码如下

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

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right  = parent;
		parent->_parent = subL;

		Node* parentPARENT = parent->_parent;

		parent->_parent = subR;
		if (subR)
			subR->_parent = parent;

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

?我们旋转的最终目的是要将不平衡的树变成平衡树，同时降低了树的高度

此时我们就可以带入到更新平衡因子的代码中

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 < key)//判断我们定义的k,v结构中所在树中的k是否小于我们所插入的key
			{
				parent = cur;
				cur = cur->_right;//如果key大于树中结点的值就走右边
			}
			else if (cur->_kv.first > key)
			{
				parent = cur;
				cur = cur->_left;//key小于树中结点的值就走左边
			}
			else
			{
				return false;//相等时结束
			}
		}

		//运行至当前位置时则说明cur为空
		cur = new Node(kv);
		if(parent->_kv.first < key)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else if (parent->_kv.first > key)
		{
			parent->_left = cur;
			cur->_parent= parent;
		}


		while (parent)
		{
			//更新平衡因子
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;//注意cur和parent都是指针，这里是改变指针的指向
				parent = parent->_parent;
			}
			else if(parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转调整
				if (parent->_bf == 2 && cur->_bf == 1)//左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;

	}

2.3.3.双旋

当我们的插入出现了以下情况时该如何旋转呢？

可以看到我们新插入的结点在在60结点的左树，并且在旋转之后平衡因子显示并不能使这棵树为AVL树，所以左单旋无法解决问题。

所以我们需要对子树b进行拆解，拆解后图示如下

我们拆解后的树的特点使a和d都是高度为h的树（h>0）;

b和c是高度为h-1的AVL树or空树（h>=1）;

同样的我们也需要分情况来讨论分解的情况

1.h==0时，如下图

?2.当h==1时，如下图

?3.当h==2时，如下图

a和d结点可能时x、y、z中的任意一个子树，有3*3=9中可能；

那么插入的位置可以是b和c结点的任意位置，有四个可能插入位置；

合计组合有9*4=36种场景

当然我们上面也说过有无数种变形场景，所以我们在这里只需写出结论

双旋：

1.以90结点为旋转点进行右单旋

2.以30结点为旋转点进行左单旋?

以下图双旋为例

?先进行右单旋

?变成一边高后的树后在进行左单旋

这样平衡因子符合条件。

上述过程是在b结点的树插入，在c结点插入原理相同

同样可以达到AVL树的条件。?

?接下来用代码展示右左双旋的过程

此图是对各个结点的命名和平衡因子的标识

void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;//记录平衡因子；

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)//当平衡因子为0时，subRL自己就是新增的结点
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}

		else if (bf == -1)
		{
			//subL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else//此时不符合树的规则
		{
			assert(false);
		}

	}

如上代码参考上述右左双旋结构图变化。

3.AVL树测试

以下是对以上实现的AVL树的测试代码

int main()
{
	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> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder(); 

	return 0;
}

我们先循环遍历插入a数组种的内容，并用先序遍历

插入成功

这只能证明我们的插入没有问题，接下来我们需要测试平衡因子是否也会调整。

以下为判断平衡因子的更细

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

	int _Height(Node* root)//求树的高度函数
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        //三目运算符求高度
	}


	bool _IsBalance(Node* root)//
	{
		if (root == nullptr)//树为空返回空
			return true;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		if (rightHeight - leftHeight != root->_bf)//右树高度和左树高度差并不等于bf就抛异常
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

在main函数种调用并输出判平衡函数，观察值为1说明平衡。

我们不妨设置大量的数据再进行测试

?

int main()
{
	const int N = 100;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	cout << t.IsBalance() << endl;
}

我们设置了100个随机数并插入

可以看到平衡因子异常已经被检测出来了。

我们也可以观察是在插入谁的时候出现了问题，如下图

可以看到结果中我们在插入14604的时候出现了问题?

?

4.全部代码

?4.1.AVL.h

AVL.h中包括结点的设计，插入，左单旋，右单旋，右左双旋，先序遍历，中序边路，树的高度计算和结点的更新

#pragma once
#include<assert.h>
#include<vector>
#include<map>
#include<stdlib.h>
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)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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;
		}

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -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)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				// 1、旋转让这颗子树平衡了
				// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

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

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

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

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf = 0;
	}

	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;

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

			subL->_parent = parentParent;
		}

		subL->_bf = parent->_bf = 0;
	}

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

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			// subRL自己就是新增
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subRL->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subRL->_bf = 0;
			subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateLR(Node* parent)
	{
		//...
		RotateL(parent->_left);
		RotateR(parent);
	}


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

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

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

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

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

private:
	Node* _root = nullptr;
};

4.2.test.h?

?测试树的插入、节点更新和旋转

#include<iostream>
using namespace std;
#include"AVL.h"

//int main()
//{
//	map<string, string> dict;
//	dict.insert(make_pair("left", "左边"));
//	dict.insert(make_pair("left", "剩余"));
//	dict.insert(make_pair("left", "左边"));
//
//	for (auto& kv : dict)
//	{
//		cout << kv.first << ":" << kv.second << endl;
//	}
//
//
//
//	return 0;
//}

/*int main()
{
	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> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
	return 0;
}*/

int main()
{
	const int N = 100;
	vector<int> v;
	v.reserve(N);
	//srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
		cout << v.back() << endl;
	}

	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	cout << t.IsBalance() << endl;
}

?以上是有关AVL树的内容，因本人水平有限，有误之处请指出批评，如果对您有所帮助还请三连支持，感谢您的阅读。