直击AVL树要害：插入过程详解（大厂面试常考：建议收藏）

直击AVL树要害：插入过程详解（大厂面试常考：建议收藏）

前言

AVL树是数据结构中效率比较高的结构，应用非常广泛，相比于顺序表和链表，在一亿个单词查找一个单词平均需要一亿次，AVL树只需要查找几十次，就能快速高效地在一亿个单词获得想要的单词。在实现AVL树数据结构的时候，我们会遇到很多的难题，这一节，我会就AVL树中插入数据过程所会遇到的难题进行详细分析。

本节重点

一、什么是AVL树？

二、AVL树的性质

三、AVL树结点的类型

四、查找

五、重头戏：插入（分类讨论）

一、什么是AVL树？

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

二、AVL树的性质

示意图

上图就是一棵AVL树

三、AVL树结点的类型（K_Val模型）

//结点类型
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;
    //构造函数
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{
   
//新节点由于没有左右子树，因此左右高度肯定是平衡的，那么平衡因子自然就是0
	}
};

四、查找

查找操作和二叉搜索树非常相似

代码示例

	bool Find(const pair<K,V>& kv)//插入一个kv类型的数据
	{
   
	//const:对kv进行保护，防止kv被改变
	//&:减少拷贝
		Node* cur = _root;
		while (cur)
		{
   
			if (cur->_kv.first < kv.first)
			{
   
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
   
				cur = cur->_left;
			}
			else
			{
   
				return true;
			}
		}
		return false;
	}

注意：

1. 这里可以不对树进行判空操作，因为，如果树为空，那么_root = nullptr，则cur = nullptr，那么下面的循环就不会进去，函数会直接返回false
2. 在比较的过程中不是比较kv的大小，而是比较kv中的first，因为kv中的