【数据结构】AVL树

目录

一.AVL树的概念

二.AVL树的实现

1.框架

2.插入的实现

3.更新平衡因子, 更新后有三种情况

4.四种旋转, 左单旋, 右单旋, 左双旋, 右双旋

1).左单旋

2).右单旋

3).左双旋

4).右双旋 

5.双旋后需手动更新平衡因子, 每种双旋三种更新情况

三.AVL树的检验

四.AVL树的效率

---

一.AVL树的概念

AVL树又称高度平衡二叉搜索树

具有以下两点性质的二叉搜索树, 被称为AVL树

1.左右子树的高度差的绝对值小于2

2.左右子树也是AVL树

二.AVL树的实现

1.框架

由于要考虑到向上更新平衡因子, 所以AVL树采用三叉链, 新增了一个_parent指针指向当前节点的父节点

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	pair _kv;
	int _bf;//平衡因子
 
	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};
 
template<class K, class V>
class AVLTree
{
public:
	typedef AVLTreeNode Node;
    //插入
	bool insert(const pair& kv);
 
private:
    //四种旋转
	void RotateL(Node* prev);
	void RotateR(Node* prev);
	void RotateRL(Node* prev);
	void RotateLR(Node* prev);
    //中序遍历
	void _InOrder(Node* root);
    //判断是否为AVL树
	bool _isBalance(Node* root);
	int Height(Node* root);
 
    //成员变量
	Node* _root = nullptr;
};

2.插入的实现

template<class K, class V>
bool AVLTree:: insert(const pair& kv)
{
	//如果是一棵空树
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	//树不为空, 一直遍历到空节点, 插入
	Node* cur = _root;
	Node* prev = nullptr;
	while (cur)
	{
		if(cur->_kv.first > kv.first)
		{
			prev = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			prev = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (prev->_kv.first < kv.first)
	{
		prev->_right = cur;
	}
	else//prev->_kv.first > kv.first
	{
		prev->_left = cur;
	}
	cur->_parent = prev;
	//此时已插入成功, 开始控制平衡因子, 并且旋转
	//一.更新平衡因子
	//规则:
	//1.如果有一个节点得_bf更新到1或-1, 一定是由0更新得来, 此时持续向上更新, 更新到cur->_parent == nullptr为止
	//2.如果有一个节点的_bf更新到0, 一定是由-1或1更新得来的, 此时可以停止向上更新, 并且无需旋转
	//3.如果有一个节点的_bf更新到2或-2, 一定是由-1或1更新得来, 此时需要旋转
	while (prev)
	{
		if (cur == prev->_left)
		{
			prev->_bf--;
		}
		else
		{
			prev->_bf++;
		}
 
		if (prev->_bf == 0)//情况1
		{
			break;
		}
		else if (abs(prev->_bf) == 1)//情况2
		{
			cur = prev;
			prev = prev->_parent;
		}
		else if(abs(prev->_bf) == 2)//情况3
		{
			//二.旋转
			//旋转一共分为四种情况, 分别为:左单旋, 右单旋, 左双旋, 右双旋
			if (cur->_bf == 1 && prev->_bf == 2)//左单旋
			{
				RotateL(prev);
			}
			else if (cur->_bf == -1 && prev->_bf == -2)//右单旋
			{
				RotateR(prev);
			}
			else if (cur->_bf == -1 && prev->_bf == 2)//左双旋
			{
				RotateRL(prev);
			}
			else if (cur->_bf == 1 && prev->_bf == -2)//右双旋
			{
				RotateLR(prev);
			}
			else
			{
				//不存在的情况, 平衡因子出现问题
				assert(false);
			}
			break;
		}
		else//不存在的情况, 平衡因子出现问题
		{
			assert(false);
		}
	}
	return true;
}

3.更新平衡因子, 更新后有三种情况

//1.如果有一个节点得_bf更新到1或-1, 一定是由0更新得来, 此时持续向上更新, 更新到cur->_parent == nullptr为止
//2.如果有一个节点的_bf更新到0, 一定是由-1或1更新得来的, 此时可以停止向上更新, 并且无需旋转
//3.如果有一个节点的_bf更新到2或-2, 一定是由-1或1更新得来, 此时需要旋转

对于以上三句话的解读:

在插入之前, 该树一定是一棵AVL树, 因为在下一次插入前, 如果不符合AVL树的条件的话, 一定会旋转成为一棵AVL树

所以在插入的新节点之前, 所有节点的平衡因子一定是0, -1, 1, 即所有节点的平衡因子都一定是平衡的

那么我们插入了新节点, 对于之前所有节点的平衡因子的改动, 无非就是+1和-1的操作, 所以改动之后的平衡因子范围一定在-2 ~ 2之间

情况1: 由0        ---  +1或-1  ---  成为1或-1

如果更新后成为了1或-1, 那么之前一定是0, 说白了插入之前两边一定是高度相等的, 插入新节点之后, 变为了一边偏高, 此时孩子一边偏高了, 那么父亲一定受到影响, 故一直向上更新平衡因子

情况2: 由1或-1 ---  -1或+1  ---  成为0

如果更新后成为了0, 那么之前一定是1或-1, 说白了插入之前两边一边偏高, 但在插入新节点之后, 将矮的那一边补齐了, 补齐之后两边高度相等了, 说明孩子高度相等了, 对父亲是没有影响的, 就不需要继续向上更新了, 并且也没出现高度为-2或2的情况, 也就不需要旋转, break即可

情况3: 由1或-1 ---  +1或-1  ---  成为2或-2

如果更新后变成了2或-2, 那么之前一定是1或-1, 说白了插入之前两边一边偏高, 但是这次插入很不凑巧, 插入在了偏高的一边, 让高的更高了, 高度差大于1即变得不平衡了, 需要进行旋转修正!

当插入新节点之后, 更新平衡因子出现了情况3的时候, 需要对树进行旋转

旋转一共总结为四大类: 左单旋, 右单旋, 左双旋, 右双旋

4.四种旋转, 左单旋, 右单旋, 左双旋, 右双旋

1).左单旋

void RotateL(Node* prev)
{
	Node* subR = prev->_right;
	Node* subRL = subR->_left;
	Node* ppNode = prev->_parent;
 
	prev->_right = subRL;
	if (subRL)
	{
		subRL->_parent = prev;
	}
 
	subR->_left = prev;
	prev->_parent = subR;
 
	if (_root == prev)
	{
		_root = subR;
	}
	else
	{
		if (ppNode->_left == prev)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
	}
	subR->_parent = ppNode;
	subR->_bf = prev->_bf = 0;
}

2).右单旋

void RotateR(Node* prev)
{
	Node* subL = prev->_left;
	Node* subLR = subL->_right;
	Node* ppNode = prev->_parent;
 
	subL->_right = prev;
	prev->_parent = subL;
 
	prev->_left = subLR;
	if (subLR)
	{
		subLR->_parent = prev;
	}
 
	if (_root == prev)
	{
		_root = subL;
	}
	else
	{
		if (ppNode->_left == prev)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
	}
	subL->_parent = ppNode;
	subL->_bf = prev->_bf = 0;
}

3).左双旋

void RotateRL(Node* prev)
{
	Node* subR = prev->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	//先右旋, 再左旋
	RotateR(prev->_right);
	RotateL(prev);
	//需要手动更新平衡因子
	//三种情况
	//1.新插入节点在subRL->_left
	//2.新插入节点在subRL->_right
	//3.新插入节点就是subRL本身
	subRL->_bf = 0;
	if (bf == -1)
	{
		subR->_bf = 1;
		prev->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		prev->_bf = -1;
	}
	else if (bf == 0)
	{
		subR->_bf = 0;
		prev->_bf = 0;
	}
	else
	{
		//正常情况下, 不存在其他情况
		assert(false);
	}
}

4).右双旋 

void RotateLR(Node* prev)
{
	Node* subL = prev->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	//先左旋, 再右旋
	RotateL(prev->_left);
	RotateR(prev);
	//需要手动更新平衡因子
	//三种情况
	//1.新插入节点在subLR->_left
	//2.新插入节点在subLR->_right
	//3.新插入节点就是subLR本身
	subLR->_bf = 0;
	if (bf == -1)
	{
		prev->_bf = 1;
		subL->_bf = 0;
	}
	else if (bf == 1)
	{
		prev->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == 0)
	{
		prev->_bf = 0;
		subL->_bf = 0;
	}
	else
	{
		//正常情况下, 不存在其他情况
		assert(false);
	}
}

5.双旋后需手动更新平衡因子, 每种双旋三种更新情况

以左双旋为例, 一共有三种情况

三.AVL树的检验

template<class K, class V>
bool AVLTree:: isBalance()
{
	return _isBalance(_root);
}
 
template<class K, class V>
bool AVLTree:: _isBalance(Node* root)
{
	if (root == nullptr)
	{
		return true;
	}
	int leftH = Height(root->_left);
	int rightH = Height(root->_right);
	int subH = rightH - leftH;//当前节点左右子树高度差
	if (subH != root->_bf)
	{
		cout << "键值为: " << root->_kv.first << "的平衡因子出现问题" << endl;
		return false;
	}
	return abs(subH) < 2 && _isBalance(root->_left) && _isBalance(root->_right);
}
 
//求树的高度
template<class K, class V>
int AVLTree:: Height(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int leftHeight = Height(root->_left);
	int rightHeight = Height(root->_right);
	return max(leftHeight, rightHeight) + 1;
	//return max(Height(root->_left), Height(root->_right)) + 1;
}

四.AVL树的效率

AVL树是二叉搜索树的优化版本, 二叉搜索树不稳定, 效率在O(logN)与O(N)之间, 在极端情况下会退化成单枝树且时间复杂度为O(N), AVL树改进了这一缺点, 使左右子树高度差的绝对值小于2, 且每棵子树也都遵守这个规则, 使得AVL树在形式上非常接近一棵满二叉树, 在任何情况下都保证了查找效率是O(logN), 非常稳定.

AVL树的查找效率极高, 插入涉及到维护平衡性的问题需要旋转但一般旋转1~2次就可以达到平衡了, 但对于删除而言, 效率相对较低, 有可能需要多次旋转, 甚至一直旋转到根的位置

AVL树为了保证其稳定性, 也付出了相应的代价 -- 旋转, 所以AVL树更适用于存储一些数据个数为静态的数据(即数据个数不经常发生修改), 这样对AVL树而言, 结构不会经常发生修改, 也就不会经常发生插入和删除操作, 旋转的次数相对减少