C++之AVLTree

不会就选b

555人浏览 · 2026-05-11 18:19:26

不会就选b · 2026-05-11 18:19:26 发布

AVL树的概念

1.AVL树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
2. 在AVL树的模拟过程中，我们将要引入平衡因子的概念平衡因子=右子树的高度-左子树的高度也就是说任何结点的平衡因子等于0/1/-1。
3. AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 (log n)，那么增删查改的效率也可以控制在O(log n) ，相比二叉搜索树有了本质的提升。

在这里插入图片描述

AVL树的实现

节点结构

相对于二叉搜索树，这里多了指向父亲节点的指针和balance factor平衡因子。
在这里插入图片描述

_parent用于后面更bf
在这里插入图片描述

树结构

与之前二叉搜索树是或相似的，typedef避免忘记传入k,v。
在这里插入图片描述

insert

1.AVL树的插入操作和二叉搜索是很相似的，要添加bf，和parent的变化
2.新插入节点会改变祖先的平衡因子，因此我们需要更新祖先的平衡因子。
3.观察平衡因子有没有绝对值大于1，有就要进行旋转，没有就结束。

插入时平衡因子的变化(还未进行旋转调整)

如果是在右子树插入平衡因子+1，在左子树插入平衡因子-1
如果插入后平衡因子=0，说明原来是-1或者1
如果插入后平衡因子=-1或者1，说明原来是0
如果插入后平衡因子=-2或者2，说明原来是-1或者1

在这里插入图片描述
需要判断插入的位置是左子树还是右子树
在根据平衡因子的数字来进行下一步要怎么做
插入后
1.当插入位置的父亲节点平衡因子为0时，此时平衡因子就不需要在向上更新

2.当插入位置的父亲节点平衡因子为1/-1时，此时平衡因子就需要在向上更新

在这里插入图片描述
3.当插入位置的父亲节点或者更新的父亲节点平衡因子为2/-2时，此时要对树进行旋转

4.当平衡因子出现其他情况就是不对的

初步实现的代码框架

bool Insert(const pair<K,V> kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur != nullptr)
	{
		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 (cur->_kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
		
	}
	cur->_parent = parent;
	
	//更新平衡因子
	while (parent)//可能祖先一直要更新到跟的位置parent为空就结束
	{
		if (cur == parent->_right)
		{//右侧插入++
			parent->bf++;
		}
		else
		{//左侧插入--；
			parent->bf--;
		}

		if (parent->bf == 0)
		{//平衡因子的值来判断要不要修改
			break;
		}
		else if (parent->bf == 1 || parent->bf == -1)
		{//继续网上更新平衡因子
			cur = parent;
			parent = cur->_parent;
		}
		else if (parent->bf == 2|| parent->bf == -2)
		{//进行旋转

		}
		else
		{
			assert(false);
		}
	}
	return true;
}

旋转逻辑

旋转一共有四种
1.右单旋
2.左单旋
3.左右双旋
4.右左双旋

右单旋

在这里插入图片描述
简单来说就是5<b<10,那么可以将b变成10的左子树，将10变成5的右子树
我们也可以看到调整完之后的5和10的平衡因子变成0；

在这里插入图片描述
若只是单纯的看图是可以的，但是没有考虑到parent是不是根的情况，_parent的更新，bf更新的情况，还有b如果为空的情况，可能会有空指针解引用的问题

在这里插入图片描述

void RotateR(Node* parent)
{
	Node* subl = parent->_left;
	Node* sublr = subl->_right;
	Node* parentparent = parent->_parent;
	parent->_left = sublr;
	subl->_right = parent;

	//_parent指针的更新
	if(sublr!=nullptr)
	sublr->_parent = parent;

	parent->_parent = subl;
	
	//如果parent不是根节点
	if (_root!= parent)
	{
		if (parentparent->_kv.first > parent->_kv.first)
		{
			parentparent->_left = subl;
			subl->_parent = parentparent;
		}
		else
		{
			parentparent->_right = subl;
			subl->_parent = parentparent;
		}
	}
	else {
		//如果parent是根节点
		subl->_parent = nullptr;
		_root = subl;
	}
	//平衡因子的更新
	parent->_bf = subl->_bf = 0;

}

左单旋

与右单旋的逻辑是相似的
在这里插入图片描述

void RotateL(Node* parent)
{
	Node* subr = parent->_right;
	Node* subrl = subr->_left;
	Node* parentparent = parent->_parent;
	parent->_right = subrl;
	subr->_left = parent;

	//_parent指针的更新
	if (subrl != nullptr)
		subrl->_parent = parent;

	parent->_parent = subr;

	//如果parent不是根节点
	if (_root != parent)
	{
		if (parentparent->_kv.first > parent->_kv.first)
		{
			parentparent->_left = subr;
			subr->_parent = parentparent;
		}
		else
		{
			parentparent->_right = subr;
			subr->_parent = parentparent;
		}
	}
	else {
		//如果parent是根节点
		subr->_parent = nullptr;
		_root = subr;
	}
	//平衡因子的更新
	parent->_bf = subr->_bf = 0;

}

左右双旋

面对下面这张图来说，单纯的左单旋和右单旋是无法解决的。
那应该怎么办呢？
在这里插入图片描述
我们要将b进行拆封

我们可以对在左侧插入的先进性左旋转，然后在进行右旋，如下图紫色箭头
当然我们也可以这样认为将b进行拆分后，左侧给他的父亲，右侧·给他的父亲的父亲，将自己变成父亲和父亲的父亲的父亲，如下图绿色箭头。
总共有以下为三种
1.
在这里插入图片描述
2.

3. 在这里插入图片描述

	void RotateLR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		int bf = sublr->_bf;

		RotateL(subl);
		RotateR(parent);
		if (bf == -1)
		{
			parent->_bf = 1;
			subl->_bf = 0;
			sublr->_bf = 0;

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

	}

在这里插入图片描述

void RotateRL(Node* parent)
{
	Node* subr = parent->_right;
	Node* subrl = subr->_left;
	int bf = subrl->_bf;

	RotateR(subr);
	RotateL(parent);
	if (bf == -1)
	{
		parent->_bf =0;
		subr->_bf = 1;
		subrl->_bf = -1;

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

}

测试与调整

简单来说我们要先测式看看是不是我们的逻辑是否错误。
我们加了一个中序遍历，算高度的函数，在增加了一个递归调用的函数来算平衡因子。

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	bool IsBalanceTree()
	{
		_IsBalanceTree(_root);
		return 1;
	}
private:
	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 _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
	
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		//cout << root->_kv.first << " "<< root->_kv.second<<endl;
		cout << root->_kv.first << " ";
		_Inorder(root->_right);

	}

1.平衡因子有问题
在这里插入图片描述
接下来我们要学会调试，打断点。
根据上图我们发现是14插入后对5的平衡因子产生了影响

我们可以按照下图的方式打断点然后进入监视窗口看看，然后画出图片

在这里插入图片描述
发现每个条件都一个一个进去，是没有break的原因。

AVLTree.h

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

template <class K,class V>
struct AVLNode
{
	pair<K, V> _kv;
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;
	int _bf;
	
	AVLNode(const pair<K, V> kv)
		:_kv(kv)
		,_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		, _bf(0)
	{ }
	
};

template <class K, class V>
class AVLTree
{
	typedef AVLNode<K,V> Node;

public:
	bool Insert(const pair<K,V> kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur != nullptr)
		{
			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 (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
			
		}
		cur->_parent = parent;
		
		//更新平衡因子
		while (parent)//可能祖先一直要更新到跟的位置parent为空就结束
		{
			
			if (cur == parent->_right)
			{//右侧插入++
				parent->_bf++;
			}
			else
			{//左侧插入--；
				parent->_bf--;
			}

			if (parent->_bf == 0)
			{//平衡因子的值来判断要不要修改
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{//继续网上更新平衡因子
				cur = parent;
				parent = cur->_parent;
			}
			else if (parent->_bf == 2|| parent->_bf == -2)
			{//进行旋转
				if (cur->_bf == -1 && parent->_bf == -2)
				{
					RotateR(parent);
					break;
				}
				else if (cur->_bf == 1 && parent->_bf == 2)
				{
					RotateL(parent);
					break;

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

				}
				else
				{
					/*cout << "Error: Unhandled balance factor case!" << endl;
					cout << "parent->_bf = " << parent->_bf << endl;
					cout << "cur->_bf = " << cur->_bf << endl;*/
					assert(false);
				}
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	bool IsBalanceTree()
	{
		_IsBalanceTree(_root);
		return 1;
	}
private:
	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 _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
	
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		//cout << root->_kv.first << " "<< root->_kv.second<<endl;
		cout << root->_kv.first << " ";
		_Inorder(root->_right);

	}
	


	void RotateR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		Node* parentparent = parent->_parent;
		parent->_left = sublr;
		subl->_right = parent;
		int bf = subl->_bf;
		//_parent指针的更新
		if(sublr!=nullptr)
		sublr->_parent = parent;

		parent->_parent = subl;
		
		//如果parent不是根节点
		if (_root!= parent)
		{
			if (parentparent->_kv.first > parent->_kv.first)
			{
				parentparent->_left = subl;
				subl->_parent = parentparent;
			}
			else
			{
				parentparent->_right = subl;
				subl->_parent = parentparent;
			}
		}
		else {
			//如果parent是根节点
			subl->_parent = nullptr;
			_root = subl;
		}
		//平衡因子的更新
		parent->_bf = subl->_bf = 0;
	}

	void RotateL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		Node* parentparent = parent->_parent;
		parent->_right = subrl;
		subr->_left = parent;

		//_parent指针的更新
		if (subrl != nullptr)
			subrl->_parent = parent;

		parent->_parent = subr;

		//如果parent不是根节点
		if (_root != parent)
		{
			if (parentparent->_kv.first > parent->_kv.first)
			{
				parentparent->_left = subr;
				subr->_parent = parentparent;
			}
			else
			{
				parentparent->_right = subr;
				subr->_parent = parentparent;
			}
		}
		else {
			//如果parent是根节点
			subr->_parent = nullptr;
			_root = subr;
		}
		//平衡因子的更新
		parent->_bf = subr->_bf = 0;

	}

	void RotateLR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		int bf = sublr->_bf;

		RotateL(subl);
		RotateR(parent);
		if (bf == -1)
		{
			parent->_bf = 1;
			subl->_bf = 0;
			sublr->_bf = 0;

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

	}

	void RotateRL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		int bf = subrl->_bf;

		RotateR(subr);
		RotateL(parent);
		if (bf == -1)
		{
			parent->_bf =0;
			subr->_bf = 1;
			subrl->_bf = -1;

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

	}
private:
	Node* _root = nullptr;
};

test.cpp

#include"AVLTree.h"

void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试用例
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试用例
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		if (e == 3)
		{
			int x = 10;
		}
		t.Insert({ e, e });
		t.Inorder();
		t.IsBalanceTree();
	}
	t.Inorder();
	cout << t.IsBalanceTree() << endl;
}
int main()
{
	//AVLTree<int, int>t;
	TestAVLTree1();
	return 0;
}