详谈平衡二叉搜索树（AVL树）

南桥

发布于 2024-08-24 13:45:22

210

发布于 2024-08-24 13:45:22

文章被收录于专栏：南桥谈编程

文章目录

AVL树的概念
AVL树节点
AVL树的插入
AVL树的旋转
- 新节点插入较高左子树的左侧---左左：右单旋
- 新节点插入较高右子树的右侧---右右：左单旋
- 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
- 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
AVL树的验证
AVL树性能

AVL树的概念

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

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

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O(log_2 n)

，搜索时间复杂度O(

log_2 n

)

AVL树节点

与搜索二叉树不同的是，这里需要三个节点，多一个父亲节点，为了我们后面对平衡因子进行调整。

template<class K, class V>
struct AVLreeNode
{
	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)
	{}
};

AVL树的插入

按照搜索树的原则插入
更新插入节点的祖先节点的平衡因子 a、插入在父亲的左边，父亲的平衡因子-- b、插入在父亲的右边，父亲的平衡因子++ c、父亲的平衡因子等于0，父亲所在的子树高度不变，不再往上更新，插入结束 d、父亲的平衡因子等于1或者-1，父亲所在的子树的高度变了，继续往上更新 e、父亲的平衡因子等于2或者-2，父亲所在的子树已经不平衡，需要旋转处理注意：更新中不可能出现其他值，插入前这个数是AVL树，平衡因子是1，-1，0，进行++或者--时只可能是上述cde三种情况。

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(key, value);
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_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;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	//更新平衡因子
	while (parent)
	{
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}

		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//需要旋转

			break;
		}
		else
		{
			//理论而言不可能出现的情况
			assert(false);
		}

	}

	return true;
}

AVL树的旋转

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

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

30节点的右孩子可能存在，也可能不存在
60可能是根节点，也可能是子树如果是根节点，旋转完成后，要更新根节点，如果是子树，可能是某个节点的左子树，也可能是右子树。

右旋的条件：

if (parent->_bf == -2 && cur->_bf == -1)
{
	RotateR(parent);
}

void RotateR(Node* parent)
{
	//subL 是 parent 节点的左子节点，subLR 是 subL 的右子节点。
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	//将 parent 的左子节点指向 subLR。如果 subLR 存在，更新 subLR 的父节点为 parent
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	//将 subL 的右子节点设置为 parent，完成旋转的主要操作
	subL->_right = parent;
	//记录 parent 的父节点 ppNode，然后将 parent 的父节点更新为 subL
	Node* ppNode = parent->_parent;
	parent->_parent = subL;
	//如果 parent 是树的根节点，则将树的根节点更新为 subL，并将 subL 的父节点设为 nullptr
	if (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	//如果 parent 不是根节点，则更新 ppNode 的子节点指针，指向 subL，并将 subL 的父节点设为 ppNode。
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}

		subL->_parent = ppNode;
	}

	parent->_bf = subL->_bf = 0;
}

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

和右旋需要考虑的问题一致，只不过旋转的方式不一样。

左旋的条件：

else if (parent->_bf == 2 && cur->_bf == 1)
{
	RotateL(parent);
}

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	subR->_left = parent;
	Node* ppNode = parent->_parent;

	parent->_parent = subR;

	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (ppNode->_right == parent)
		{
			ppNode->_right = subR;
		}
		else
		{
			ppNode->_left = subR;
		}
		subR->_parent = ppNode;
	}

	parent->_bf = subR->_bf = 0;
}

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

条件：

else if (parent->_bf == -2 && cur->_bf == 1)
{
	RotateLR(parent);
}

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

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

条件：

else if (parent->_bf == 2 && cur->_bf == -1)
{
	RotateRL(parent);
}

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
}

AVL树的验证

封装一个计算树的高度函数：

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return max(_Height(root->_left), _Height(root->_right)) + 1;
}

判断是否是平衡二叉树：只需要计算左右子树高度差是否小于等于1即可：

bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	//不平衡
	if (abs(leftHeight - rightHeight) >= 2)
	{
		return false;
	}
	//检查平衡因子是否正确
	if (rightHeight - leftHeight != root->_bf)
	{
		cout << root->_kv.first << endl;
		return false;
	}

	return _IsBalance(root->_left) && _IsBalance(root->_right);
}