AVL树深度解析

小灵蛇

发布于 2024-06-06 21:31:25

620

发布于 2024-06-06 21:31:25

文章被收录于专栏：文章部

一. AVL树的概念

我们上一篇博客讲了，二叉搜索树在极端情况下会退化为单支树的情况（具体可以看上一篇博客：http://t.csdnimg.cn/o7PiL）。那我们该如何解决这种问题呢？

诶，还真有这种方法，是由著名的两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年提出的。如果让左右子树的高度差的绝对值不超过1，那我们就可以避免这种单支树的情况。

那我们将具有以下特征的二叉搜索树叫做AVL树：

左右子树的高度差（这里简称平衡因子）的绝对值不超过1
左右子树都是AVL树

如果一棵树是高度平衡的，那它就是AVL树，如果这棵树有n个节点，那我们能把这棵树的高度维持在log2n，查找的时间复杂度可以维持在O(log2n)。

二. AVL树节点的定义

我们用代码来刻画这个定义：

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _pf;//平衡因子
	pair<K, V> _kv;
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_pf(0)
		,_kv(kv)
	{}
};

可以看见，我们引进了平衡因子这个变量，来显示左右子树的高度差。

特别说明：此处平衡因子是右边减去左边。

三. AVL树的基本操作

我们这里着重讲解AVL树的插入操作，其他操作与普通的二叉搜索树是一样的。

3.1 插入操作：

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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first>kv.first)
		{
			parent->_left = cur;
		}
		else if(parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_pf--;
			}
			else if (cur == parent->_right)
			{
				parent->_pf++;
			}
			if (parent->_pf == 0)
			{
				break;
			}
			else if (parent->_pf == 1 || parent->_pf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_pf == 2 || parent->_pf == -2)
			{
				//旋转处理
				if (parent->_pf == 2 && cur->_pf == 1)
				{
					RotaleL(parent);
				}
				else if (parent->_pf == -2 && cur->_pf ==- 1)
				{
					RotaleR(parent);
				}
				else if (parent->_pf == -2 && cur->_pf == 1)
				{
					RotaleLR(parent);
				}
				else
				{
					RotaleRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

我们依次来解析需要特殊处理的情况：

3.1.1 parent->_pf = 0

当父节点的平衡因子为0时，证明左右子树是平衡的，不需要再做处理，直接跳出循环。

if (parent->_pf == 0)
{
	break;
}

3.1.2 abs(parent->_pf) = 1

当父节点的平衡因子的绝对值为1时，证明此父节点下的子树是平衡的，但是，由于我们前面改变了父节点的平衡因子，可能导致父节点的祖宗节点不平衡，所以我们要向上迭代，再次进行判断。

else if (parent->_pf == 1 || parent->_pf == -1)
{
	cur = cur->_parent;
	parent = parent->_parent;
}

3.1.3 abs(parent->_pf) = 2

当父节点的平衡因子绝对值为2时，我们为了保证树的平衡，需要进行一些旋转操作。此类情况比较复杂，又细分为以下几种情况：

3.1.3.1 parent->_pf = 2 && cur->_pf = 1

当父节点的平衡因子为2，而当前节点平衡因子为1时，是在当前节点是父节点的右子节点，并且插入节点是当前节点的右子节点发生的。

此时我们要进行左单旋：

if (parent->_pf == 2 && cur->_pf == 1)
{
	RotaleL(parent);
}

void RotaleL(Node* parent)
{
	totalSize++;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	subR->_left = parent;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	if (parent == _root)
	{
		_root = subR;
		subR->_parent == nullptr;
	}
	else
	{
		if (parent == ppnode->_left)
		{
			ppnode->_left = subR;
		}
		else if (parent == ppnode->_right)
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	parent->_pf = 0;
	subR->_pf = 0;
}

总结来说，此情况就是让当前节点的左子树变为父节点的右子树，而当前节点的左子树变为父节点，再改变当前节点和父节点的父节点指向并更新平衡因子即可。

3.1.3.2 parent->_pf = -2 && cur->_pf =- 1

当父节点的平衡因子为-2，而当前节点平衡因子为-1时，是在当前节点是父节点的左子节点，并且插入节点是当前节点的左子节点发生的。

此时我们要进行右单旋：

else if (parent->_pf == -2 && cur->_pf ==- 1)
{
	RotaleR(parent);
}

void RotaleR(Node* parent)
{
	totalSize++;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subL;
	if (parent == _root)
	{
		_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->_pf = 0;
	parent->_pf = 0;
}

总结来说，此情况就是让当前节点的右子树变为父节点的左子树，而当前节点的右子树变为父节点，再改变当前节点和父节点的父节点指向并更新平衡因子即可。

3.1.3.3 parent->_pf = -2 && cur->_pf = 1

当父节点的平衡因子为-2，而当前节点平衡因子为1时，是在当前节点是父节点的左子节点，并且插入节点是当前节点的右子节点发生的。

此情况比较复杂，单一的旋转已经不能满足树的平衡了，我们此时要先左旋再右旋：

else if (parent->_pf == -2 && cur->_pf == 1)
{
	RotaleLR(parent);
}

void RotaleLR(Node* parent)
{
	totalSize++;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int pf = subLR->_pf;
	RotaleL(parent->_left);
	RotaleR(parent);
	if (pf == 1)
	{
		subLR->_pf = 0;
		subL->_pf = -1;
		parent->_pf = 0;
	}
	else if (pf == -1)
	{
		subL->_pf = 0;
		subLR->_pf = 0;
		parent->_pf = 1;
	}
	else if (pf == 0)
	{
		subL->_pf = 0;
		subLR->_pf = 0;
		parent->_pf = 0;
	}
}

总结来说，可以复用前面的左旋与右旋函数，但是与前面不同的是需要分情况处理平衡因子。

3.1.3.4 parent->_pf = 2 && cur->_pf = -1

当父节点的平衡因子为2，而当前节点平衡因子为-1时，是在当前节点是父节点的右子节点，并且插入节点是当前节点的左子节点发生的。

此情况同样单一的旋转已经不能满足树的平衡了，我们此时要先右旋再左旋：

else
{
	RotaleRL(parent);
}

void RotaleRL(Node* parent)
{
	totalSize++;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int pf = subRL->_pf;
	RotaleR(parent->_right);
	RotaleL(parent);
	if (pf == 1)
	{
		subRL->_pf = 0;
		subR->_pf = 0;
		parent->_pf = -1;
	}
	else if (pf == -1)
	{
		subR->_pf = 1;
		subRL->_pf = 0;
		parent->_pf = 0;
	}
	else if (pf == 0)
	{
		subR->_pf = 0;
		subRL->_pf = 0;
		parent->_pf = 0;
	}
}

总结来说，可以复用前面的右旋与左旋函数，但是与前面同样不同的是需要分情况处理平衡因子。

四. 总体代码

整合一下代码，如下：

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _pf;//平衡因子
	pair<K, V> _kv;
	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_pf(0)
		,_kv(kv)
	{}
};
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first>kv.first)
		{
			parent->_left = cur;
		}
		else if(parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_pf--;
			}
			else if (cur == parent->_right)
			{
				parent->_pf++;
			}
			if (parent->_pf == 0)
			{
				break;
			}
			else if (parent->_pf == 1 || parent->_pf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_pf == 2 || parent->_pf == -2)
			{
				//旋转处理
				if (parent->_pf == 2 && cur->_pf == 1)
				{
					RotaleL(parent);
				}
				else if (parent->_pf == -2 && cur->_pf ==- 1)
				{
					RotaleR(parent);
				}
				else if (parent->_pf == -2 && cur->_pf == 1)
				{
					RotaleLR(parent);
				}
				else
				{
					RotaleRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
	void RotaleL(Node* parent)
	{
		totalSize++;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		subR->_left = parent;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* ppnode = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent == nullptr;
		}
		else
		{
			if (parent == ppnode->_left)
			{
				ppnode->_left = subR;
			}
			else if (parent == ppnode->_right)
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
		parent->_pf = 0;
		subR->_pf = 0;
	}
	void RotaleR(Node* parent)
	{
		totalSize++;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_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->_pf = 0;
		parent->_pf = 0;
	}
	void RotaleLR(Node* parent)
	{
		totalSize++;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int pf = subLR->_pf;
		RotaleL(parent->_left);
		RotaleR(parent);
		if (pf == 1)
		{
			subLR->_pf = 0;
			subL->_pf = -1;
			parent->_pf = 0;
		}
		else if (pf == -1)
		{
			subL->_pf = 0;
			subLR->_pf = 0;
			parent->_pf = 1;
		}
		else if (pf == 0)
		{
			subL->_pf = 0;
			subLR->_pf = 0;
			parent->_pf = 0;
		}
	}
	void RotaleRL(Node* parent)
	{
		totalSize++;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int pf = subRL->_pf;
		RotaleR(parent->_right);
		RotaleL(parent);
		if (pf == 1)
		{
			subRL->_pf = 0;
			subR->_pf = 0;
			parent->_pf = -1;
		}
		else if (pf == -1)
		{
			subR->_pf = 1;
			subRL->_pf = 0;
			parent->_pf = 0;
		}
		else if (pf == 0)
		{
			subR->_pf = 0;
			subRL->_pf = 0;
			parent->_pf = 0;
		}
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << "[" << root->_pf << "]" << endl;
		_Inorder(root->_right);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftheight = _Height(root->_left);
		int rightheight = _Height(root->_right);
		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	}
	int Height()
	{
		return _Height(_root);
	}
	//初始版本
	/*bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftheight = _Height(root->_left);
		int rightheight = _Height(root->_right);
		if (abs(leftheight - rightheight) >= 2)
		{
			cout << root->_kv.first << "不平衡" << endl;
			return false;
		}
		else if ((rightheight - leftheight) != root->_pf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}*/
	bool _IsBalance(Node* root,int& height)
	{
		if (root == nullptr)
		{
			height = 0;
			return true;
		}
		int leftheight = 0, rightheight = 0;
		if (!_IsBalance(root->_left, leftheight)
			||!_IsBalance(root->_right, rightheight))
		{
			return false;
		}
		if (abs(rightheight - leftheight) >= 2)
		{
			cout << root->_kv.first << "不平衡" << endl;
			return false;
		}
		else if ((rightheight - leftheight) != root->_pf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		height = leftheight > rightheight ? leftright + 1 : rightheight + 1;
		return true;
	}
	bool IsBalance()
	{
		int height = 0;
		return _IsBalance(_root,height);
	}
	size_t _size(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return _size(root->_left) + _size(root->_right) + 1;
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	size_t size()
	{
		return _size(_root);
	}
	int GettotalSize()
	{
		return totalSize;
	}
private:
	Node* _root = nullptr;
	int totalSize = 0;
};

总结

好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。

祝大家越来越好，不用关注我（疯狂暗示）

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

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

root