AVL树的插入

1.AVL树的定义和性质

定义

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

性质

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

2.AVL树结点的定义

avl树与二叉搜索树的结点不同的地方就在于avl树多了一个平衡因子。avl树的平衡控制实质上就是通过结点中的平衡因子来控制的。


template<class K, class V> 
struct AVLTreeNode
{
	pair _kv;
	AVLTreeNode* _parent;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
 
	int _bf;//左右子树高度差
 
	AVLTreeNode(const pair& kv)
		:_kv(kv),
		_parent(nullptr),
		_left(nullptr),
		_right(nullptr),
		_bf(0)
	{
 
	}
};

3.AVL树的插入

AVL树的插入可以分两步：

1.按照搜索二叉树的插入方法插入新结点；

2.控制更新平衡因子。

3.1 插入


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	bool insert(const pair& kv)
	{
		//1.保证搜索二叉树的特性 2.保证平衡
 
 
		// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}
 
		//找到并记录插入的位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (parent->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (parent->_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 = cur;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = cur;
		}

cur插入后，parent的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1，0, 1,

插入之后分以下两种情况：

1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可

2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

此时：parent的平衡因子可能有三种情况：0，正负1，正负2

1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足 AVL树的性质，插入成功

2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负 1，此时以parent为根的树的高度增加，需要继续向上更新

3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	bool insert(const pair& kv)
	{
		//1.保证搜索二叉树的特性 2.保证平衡
 
 
		// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_bf = 0;
			return true;
		}
 
		//找到并记录插入的位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (parent->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (parent->_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 = cur;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = cur;
		}
 
 
		// 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树平衡特性
 
		while (parent)
		{
            // 更新双亲的平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;
 
 
            
			if (parent->_bf == 0)
				break;
 
           // 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树
           // 的高度增加了一层，因此需要继续向上调整
			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);
 
				}
 
				else
				{
					assert("出错了");
				}
			}
			else
			{
				assert("出错啦");
			}
		}
	}

3.2 AVL树的旋转

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

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


/*上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增
加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加
一层，即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子
树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子
即可。在旋转过程中，有以下几种情况需要考虑：
 1. 30节点的右孩子可能存在，也可能不存在
 2. 60可能是根节点，也可能是子树
 如果是根节点，旋转完成后，要更新根节点
 如果是子树，可能是某个节点的左子树，也可能是右子树*/
	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.新节点插入较高右子树的右侧---右右：左单旋


//过程参考右单旋	
void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
 
		if(subRL)
			subRL->_parent = parent;//subRL可以为空
		parent->_right = subRL;
 
		Node* ppnode = parent->_parent;
 
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppnode->_left)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
 
		//更新平衡因子
		parent -> _bf = 0;
		subR -> _bf = 0;
 
	}

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

将双旋变成单旋后再旋转，即：先对subL进行左单旋，然后再对parent进行右单旋，旋转完成后再考虑平衡因子的更新。

a.插入到subLR的左子树

b.插入到subLR的右子树


	void RotateLR(Node* parent)//左右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
//旋转之前，保存SubLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
 
		RotateL(parent->_left);//复用之前的左右单旋函数
		RotateR(parent);
 
		// 更新平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			// subLR->_bf旋转前就有问题
			assert("出错了");
		}
	}

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

a.插入到subRL的右子树

b.插入到subRL的左子树


//实现过程参考左右旋
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为插入的数据时，那么其左右子树为空，bf为0
		{
			parent->_bf = subR->_bf = subRL->_bf;
		}
		else if (bf == 1)
		{
			subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			// subLR->_bf旋转前就有问题
			assert(false);
		}
	}

3.3 总结

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

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

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

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

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

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

特别注意：在代码中凡是条件含_bf的if语句，均要有单独的条件判断_bf是否是错误的！因为在平衡因子更新的时候防止因代码出错而导致的_bf更新错误。

4.验证AVL树

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

每个节点子树高度差的绝对值不超过1
节点的平衡因子是否计算正确


//提供函数
	int Heighth(Node* root)
	{
		if (root == nullptr)
			return 0;
		int hl = Highth(root->left);
		int hr = Highth(root->right);
 
		return hl > hr ? hl + 1 : hr + 1;
	}
 
 
    //判断是不是avl树
	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;
 
		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
 
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}
 
		if (diff != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
			return false;
		}
 
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left)
			&& _IsBalanceTree(root->_right);
	}

相关阅读:
基金的信息披露
 【零基础入门SpringMVC】第一期——开篇导论
 ssh连接失败，提示ssh: connect to host port 22: Connection refused
idea中遇到的一个问题
 申请前必知！关于「美国绿卡」的28个常见问题汇总！
网络防御--防火墙
 预约挂号系统技术点详解(一)
概率论的学习和整理9：超几何分布--未完成
 第三章简单静态网页爬取
 23.Visitor访问者（行为型模式）
原文地址：https://blog.csdn.net/weixin_60720508/article/details/126692734