移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.AVL树

用户11286441

发布于 2024-09-23 19:40:42

640

发布于 2024-09-23 19:40:42

文章被收录于专栏：学习

1.AVL 树

1.1AVL 树的概念

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

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

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

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

2.AVL树节点的定义

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！


	AVLtreenode(const pair<K, V>& _kv)    //初始化列表
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,kv(_kv)
		,bf(0)
	{}
};

3.AVL树的插入！！！！！！！

3.1初步插入

初步插入与bst的插入一致，不过里面的数据类型是pair<first,second>,并且是根据first进行比较

if (root == nullptr)
{
	root = new node(_kv);
	return true;
}
node* parent = nullptr; //比bst多了一个parent
node* cur = root;       //

while (cur)
{
	parent = cur;
	if (cur->kv.first < _kv.first)
	{
		cur = cur->_right;
	}
	else if (cur->kv.first > _kv.first)
	{
		cur = cur->_left;
	}
	else
	{
		return false;
	}
}
cur = new node(_kv);
if (parent->kv.first < _kv.first)
{
	parent->_right = cur;
}
else
{
	parent->_left = cur;
}
cur->_parent = parent;    //记得连接parent和cur

3.2调整平衡因子

while (cur != root)
{
	if (cur == parent->_left)
		parent->bf--;//第一次！！！检查parent左边原来必为空
	else {
		parent->bf++;//第一次！！！检查parent右边原来必为空
	}

	if (parent->bf == 0) //相当于bf没改变，可直接退出
	{
		break;
	}

	else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   
	{
		cur = parent;
		parent = parent->_parent;
	}

	else if(parent->bf == -2 || parent->bf == 2)
	{          //-2||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);//先左旋再右旋
		}


		//旋转让子树变得平衡
		//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响
		break;//1次旋转完成后不需要再调整了
	}
}

3.3旋转调整！！！！！！

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

由上述可知，c必定是x类型的avl树，如果是其他类型的，可能60这个节点的平衡因子就变成-2或2了，（当然，这只是单独举一个例子分析，便于分析代码，不代表所有情况）

void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右
{
	node* subr = parent->_right;
	node* subrl = subr->_left;

	parent->_right = subrl;
	subr->_left= parent;

	node* ppnode = parent->_parent;
	parent->_parent = subr;

	if (subrl) //subrl可能为空！！！！！！！！！！！！！！！
	{
		subrl->_parent = parent;
	}

	if (parent == root) // 即如果parent->_parent==nullptr
	{
		root = subr;
		subr->_parent = nullptr;
	}

	else
	{
		if (ppnode->_left == parent)   //需要再查找一下放左边还是右边
		{
			ppnode->_left = subr;
		}
		else if (ppnode->_right == parent)
		{
			ppnode->_right = subr;
		}

		subr->_parent = ppnode;
	}
	parent->bf = subr->bf = 0;   //重置平衡因子
}

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

和左单旋分析方法一致

void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左
{

	node* subl = parent->_left;
	node* sublr = subl->_right;
	parent->_left = sublr;


	if (sublr)               //sublr可能为空！！！！！！！
	sublr->_parent = parent;
	
	node* ppnode = parent->_parent;

	subl->_right = parent;
	parent->_parent=subl;

	if (root == parent)
	{
		root = subl;
		subl->_parent = nullptr;
	}

	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subl;
		}
		else if (ppnode->_right == parent)
		{
			ppnode->_right = subl;
		}

		subl->_parent = ppnode;
	}
	 

	subl->bf = parent->bf = 0;//重置平衡因子

}

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

十分巧妙的是：经过一次左旋(parent->_left)后，就变成左左类型了，这样就能复用右单旋(parent)达成平衡

void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子
{

	node* subl = parent->_left;
	node* sublr= subl->_right;
	int _bf = sublr->bf;

	rotateL(parent->_left);
	rotateR(parent);

	if (_bf == 0)
	{
		//sublr自己就是新增加的节点
		parent->bf = subl->bf = sublr->bf = 0;
	}

	else if (_bf == 1)
	{
		//sublr的右子树新增
		parent->bf = 0;
		subl->bf = -1;
		sublr->bf = 0;
	}

	else if (_bf == -1)
	{
		//sublr的左子树新增
		parent->bf = 1;
		subl->bf = 0;
		sublr->bf = 0;
	}
}

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

与上方分析方法一致

void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子
{
	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;
	    subr->bf = 1;
	    subrl->bf = 0;
	}

	else if (_bf == 1)
	{   
		//subrl的左子树新增
		parent->bf = -1;
		subr->bf = 0;
		subrl->bf = 0;
	}
}

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

4.AVL树的判断

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

1. 验证其为二叉搜索树：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树（1）每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) （2）节点的平衡因子是否计算正确

void inorder()
{
	_inorder(root);
}

void _inorder(node* root)
{
	if (root == nullptr)
		return;
	_inorder(root->_left);
	cout << root->kv.first << " ";
	_inorder(root->_right);
}

int _height(node* root)//取得高度
{
	if (root == nullptr)
		return 0;

	int lh = _height(root->_left);
	int rh = _height(root->_right);

	return lh > rh ? lh + 1 : rh + 1;//记得+1
}


bool isbalance()
{
	return _isbalance(root);
}

bool _isbalance(node* root)
{
	if (root == nullptr)
		return true;

	int lh = _height(root->_left);
	int rh = _height(root->_right);

	if ((rh - lh) !=root->bf)//判断是否符合平衡因子计算公式
	{
		cout << "异常" << endl;
		return false;
	}

	return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);//递归判断左右子树
}

5.完整代码

AVL.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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！


	AVLtreenode(const pair<K, V>& _kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,kv(_kv)
		,bf(0)
	{}
};

template<class K, class V>
class AVLtree
{
public:
	typedef AVLtreenode<K, V> node;

	bool insert(const pair<K,V>& _kv)
	{
		if (root == nullptr)
		{
			root = new node(_kv);
			return true;
		}
		node* parent = nullptr; //比bst多了一个parent
		node* cur = root;       //

		while (cur)
		{
			parent = cur;
			if (cur->kv.first < _kv.first)
			{
				cur = cur->_right;
			}
			else if (cur->kv.first > _kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new node(_kv);
		if (parent->kv.first < _kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//开始调整

		//调整平衡因子
		while (cur != root)
		{
			if (cur == parent->_left)
				parent->bf--;//第一次！！！检查parent左边原来必为空
			else {
				parent->bf++;//第一次！！！检查parent右边原来必为空
			}

			if (parent->bf == 0) //相当于bf没改变，可直接退出
			{
				break;
			}

			else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   
			{
				cur = parent;
				parent = parent->_parent;
			}

			else if(parent->bf == -2 || parent->bf == 2)
			{          //-2||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);//先左旋再右旋
				}


				//旋转让子树变得平衡
				//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响
				break;//1次旋转完成后不需要再调整了
			}
		}
	
		return true;
	}

	void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右
	{
		node* subr = parent->_right;
		node* subrl = subr->_left;

		parent->_right = subrl;
		subr->_left= parent;

		node* ppnode = parent->_parent;
		parent->_parent = subr;

		if (subrl) //subrl可能为空！！！！！！！
		{
			subrl->_parent = parent;
		}

		if (parent == root) //即如果parent->_parent==nullptr
		{
			root = subr;
			subr->_parent = nullptr;
		}

		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subr;
			}
			else if (ppnode->_right == parent)
			{
				ppnode->_right = subr;
			}

			subr->_parent = ppnode;
		}
		parent->bf = subr->bf = 0;   //重置平衡因子
	}


	void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左
	{

		node* subl = parent->_left;
		node* sublr = subl->_right;
		parent->_left = sublr;


		if (sublr)               //sublr可能为空！！！！！！！
		sublr->_parent = parent;
		
		node* ppnode = parent->_parent;

		subl->_right = parent;
		parent->_parent=subl;

		if (root == parent)
		{
			root = subl;
			subl->_parent = nullptr;
		}

		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subl;
			}
			else if (ppnode->_right == parent)
			{
				ppnode->_right = subl;
			}

			subl->_parent = ppnode;
		}
		 

		subl->bf = parent->bf = 0;

	}


	void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子
	{
		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;
		    subr->bf = 1;
		    subrl->bf = 0;
		}

		else if (_bf == 1)
		{   
			//subrl的左子树新增
			parent->bf = -1;
			subr->bf = 0;
			subrl->bf = 0;
		}
	}


	void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子
	{

		node* subl = parent->_left;
		node* sublr= subl->_right;
		int _bf = sublr->bf;

		rotateL(parent->_left);
		rotateR(parent);

		if (_bf == 0)
		{
			//sublr自己就是新增加的节点
			parent->bf = subl->bf = sublr->bf = 0;
		}

		else if (_bf == 1)
		{
			//sublr的右子树新增
			parent->bf = 0;
			subl->bf = -1;
			sublr->bf = 0;
		}

		else if (_bf == -1)
		{
			//sublr的左子树新增
			parent->bf = 1;
			subl->bf = 0;
			sublr->bf = 0;
		}
	}

	void inorder()
	{
		_inorder(root);
	}

	void _inorder(node* root)
	{
		if (root == nullptr)
			return;
		_inorder(root->_left);
		cout << root->kv.first << " ";
		_inorder(root->_right);
	}

	int _height(node* root)
	{
		if (root == nullptr)
			return 0;

		int lh = _height(root->_left);
		int rh = _height(root->_right);

		return lh > rh ? lh + 1 : rh + 1;
	}


	bool isbalance()
	{
		return _isbalance(root);
	}

	bool _isbalance(node* root)
	{
		if (root == nullptr)
			return true;

		int lh = _height(root->_left);
		int rh = _height(root->_right);

		if ((rh - lh) !=root->bf)
		{
			cout << "异常" << endl;
			return false;
		}

		return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);
	}

private:
	node* root = nullptr;
};

test.c:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>

using namespace std;

#include"AVL.h"

int main()
{
	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLtree<int, int> it;
	for (auto i : arr)
	{
		it.insert(make_pair(i,i));
	}
	it.inorder();
	cout << endl<<it.isbalance() << endl;

	return 0;
}

6.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$og_2 (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除

parent