【C++进阶05】AVL树的介绍及模拟实现

一、AVL树的概念

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

AVL树便是解决此问题

向二叉搜索树中插入新结点
并保证每个结点的左右子树
高度之差的绝对值不超过1
(需要对树中的结点进行调整)
即可降低树的高度，从而减少
平均搜索长度

AVL树或空树
或是具有以下性质的二叉搜索树

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

AVL树不一定有平衡因子
平衡因子只是其中一种实现方式

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

二、AVL树实现的基本框架

2.1 AVL树节点的定义

template <class K, class V>
struct AVLTreeNode
{
	 // 三叉链
	AVLTreeNode<K, V>* _left; 
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	
	//存储的键值对 
	pair<K, V> _KV;
	
	// balance factor 平衡因子
	int _bf; 

	// 构造函数
	AVLTreeNode(const pair<K, V>& kv)
		, left(nullptr)
		, right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

2.2 AVL树的基本结构

template <class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	Node* _root = nullptr; // 根节点
};

2.3 AVL树的插入

AVL树插入步骤：

1. 按二叉搜索树的方式插入新节点
2. 更新平衡因子
3. 若平衡因子失衡，需要旋转处理

平衡因子失衡后的旋转处理

1. 更新完, 平衡因子没问题(|bf| <= 1)
   平衡因子结构未受影响, 不需要处理

2. 更新完，平衡因子有问题(|bf| > 1)
   平衡结构受影响，需要处理(旋转)

原因：

插入新增节点
会影响祖先的平衡因子(全部或部分)
当前节点平衡因子等于
右树节点个数减左树节点个数

1. cur == parent->right 则parent->bf++
2. cur == parent->left 则parent->bf–

parent所在子树高度发生变化
则需要继续往上更新爷爷节点
否则就不更新

parent->bf == 1 || parent->bf == -1 
// 则说明parent所在子树变了, 继续更新

插入节点更新平衡因子后分为三种情况

1. 插入前parent->bf == 0
   说明插入前左右两边高度相等
   插入后有一边高1
   说明parent一边高，一边低，高度变了

2.

parent->bf == 2 || parent->bf == -2

则说明parent所在子树不平衡
需要处理这颗子树(旋转处理)

3. parent->bf == 0
   parent所在子树高度不变
   不用继续往上更新，这一次插入结束
   说明插入前parent->bf == 1 or -1
   插入前一边高，一边低
   插入节点填上矮的那边，高度不变

三、AVL树的旋转

旋转的原则：
保持它是搜索树

旋转的目的：

1. 让这棵子树平衡
2. 降低这棵子树的高度

左旋过程

1. 30的左子树25变成20的右子树
2. 20变成30的左子树
   30变成整棵树的根

实际旋转中的节点值可能不是这些值
但也是按这些点位去旋转的

根据节点插入位置的不同
AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧—左左：
右单旋
图中h为子树的高度

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

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

将双旋变成单旋后再旋转，即：
先对30进行左单旋
然后再对90进行右单旋

图中只展示了b插入引发双旋的场景
本质有三种引发双旋的场景：

1. 在b插入，b的高度变化+1
2. 在c插入，c的高度变化+1
3. 60本身就是新增节点

旋转完成后再考虑平衡因子的更新
不同场景的插入，60的平衡因子也不同
分别为-1，1，0
且每种场景的插入旋转完后90和30的
平衡因子都不一样
代码的实现通过记录60这个点位的平衡因子
旋转完后
根据不同场景的插入更新90和30的平衡因子

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

参考先左单旋再右单旋

四、插入代码的实现

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

	// new的节点的parent还指向空
	cur->_parent = parent;

	// 1. 更新平衡因子
	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) // parent->right是cur
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == -1) // parent->
			{
				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; // 处理完，break，否则会一直循环
		}
		else
		{
			// 如果插入之前就有问题
			assert(false);
		}
	}
	
	return true;
}

五、AVL树旋转代码实现

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

	parent->_right = subRL;
	if (subRL) // subRL可能为空
		subRL->_parent = parent;

	// 旋转的不一定是整棵树
	Node* pparent = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

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

		subR->_parent = pparent;
	}

	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* pparent = parent->_parent;

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

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

		subL->_parent = pparent;
	}

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

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

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

	subLR->_bf = 0; // subLR的左一定等于0
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

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

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

	subRL->_bf = 0;
	if (bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

六、全部代码实现

AVL树模拟实现全部代码：gitee链接