C++AVL树详解

2401_84541745

806人浏览 · 2025-09-21 15:11:41

2401_84541745 · 2025-09-21 15:11:41 发布

1.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查

找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii

和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

1.它的左右子树都是AVL 树

2.左右子树高度之差( 简称平衡因子 ) 的绝对值不超过 1(-1/0/1)。(平衡因子等于右子树的高度减左子树的高度)

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

$log_2 n$ ，搜索时间复杂度 $log_2 n$ 。

例：

2.AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么

AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

如何调整平衡因子：

1.新增节点在左，父亲节点平衡因子减减。

2.新增节点在右，父亲节点平衡因子加加。

3.更新后父亲节点的平衡因子 == 0，说明父亲节点所在的子树的高度不变，不会再影响祖先，不用再继续沿着到root（根）的路径往上更新平衡因子，插入结束。

4.更新后父亲节点的平衡因子 == 1 or -1，说明父亲节点所在的子树的高度变化，会影响祖先，需继续沿着root的路径向上更新平衡因子。

5.更新后父亲节点的平衡因子 == 2 or -2，说明父亲节点所在的子树的高度变化且不平衡，需要对父亲节点所在的子树进行旋转，让他平衡，平衡后插入结束。

6.更新到根节点，插入结束。

3.AVL树的旋转

AVL树失去平衡后进行调整的规律可以归纳为四种情况：

3.1.LL型（右单旋）

单纯的左边高：

这里的h是可以为（0，1，2...等）对应着各种复杂的情况：

3.2.RR（左单旋）

单纯的右边高：

这里的h是可以为（0，1，2...等）对应着各种复杂的情况：

3.3.RL（左右双旋）

左边高，但是左子树的右边高：

这里有两种情况，可以在b节点的下面插入，也可以在c节点的下面插入。

1.在b节点的下面插入：

2.在c节点的下面插入：

两者的区别就是平衡因子更新的不同。

3.如果h==0，60节点就会引起不平衡，旋转后，平衡因子结果如下。

3.4.RL（右左双旋）

右边高，但是右子树的左边高。

这里同样有两种插入方法。

1.在c节点的下面插入：

2.在b节点的下面插入：

这两种的插入方法最后的平衡因子的更新结果不同，但是旋转的方法都是一样的。

3.但是如果h==0时，那么60这个新增节点就会引起不平衡，更新后的结果如下：

4.代码实现

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;


template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	int _bf;
	pair<K, V> _kv;

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

};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

	AVLTree() : _root(nullptr) {}

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

		Node* cur = _root;
		Node* parent = nullptr;
		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
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		
		//调整平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				return true;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上调整平衡因子
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//AVL树不平衡 需要进行调整旋转
				//左树高，右单旋
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
					
				}
				//右树高，左单旋
				else if(parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
					return true;
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node *curRight = cur->_right;
		Node* ppNode = parent->_parent;

		//进行链接
		parent->_left = curRight;
		if (curRight)
			curRight->_parent = parent;

		cur->_right = parent;
		parent->_parent = cur;
		
		if (ppNode == NULL)
		{
			_root = cur;
			cur->_parent = nullptr;
		}	
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = cur;
			}
			else
			{
				ppNode->_right = cur;
			}
			cur->_parent = ppNode;
		}
		
		parent->_bf = cur->_bf = 0;

	}

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curLeft = cur->_left;
		Node* ppNode = parent->_parent;
		parent->_right = curLeft;
		if (curLeft)
		{
			curLeft->_parent = parent;
		}
		cur->_left = parent;
		parent->_parent = cur;
		if (ppNode == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = cur;
			}
			else
			{
				ppNode->_right = cur;
			}
			cur->_parent = ppNode;
		}
		cur->_bf = parent->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curLeft = cur->_left;
		int bf = curLeft->_bf; //需要提前保存 因为后面的旋转会改变curRight的平衡因子


		RotateR(cur);
		RotateL(parent);

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

	}

	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curRight = cur->_right;
		int bf = curRight->_bf; //需要提前保存 因为后面的旋转会改变curRight的平衡因子

		RotateL(cur);
		RotateR(parent);

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

	int Height()
	{
		return Height(_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;
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

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

		int leftHight = Height(root->_left);
		int rightHight = Height(root->_right);

		if (rightHight - leftHight != root->_bf)
		{
			cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
			return false;
		}

		return abs(rightHight - leftHight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}
private:
	Node* _root;
};