C++数据结构之AVL树的实现

目录

• 1.概念
• (1)二叉搜索树的缺点
• (2)定义节点
• 2.插入
• (1)拆分
• (2)找节点与插节点
• (3)更新平衡因子与旋转
• 3.判断
• 4.完整代码及测试代码
• 完整代码
• 测试代码

1.概念

(1)二叉搜索树的缺点

要手撕AVL树，我们首先要知道什么是AVL树。AVL树是在二叉搜索树的基础之上改造的。当我们插入的是一个有序的序列的时候，二叉搜素树会使用一条直线来进行存储，这样并不利于查找。

当遇到这种情况的时候我们就需要对这棵树来进行调整。AVL树会通过旋转等操作，来规避这种情况。最终满足每一个节点的平衡因子的绝对值<=1，从而达到近似平衡的目的。

节点的平衡因子值=右子树的高度-左子树高度

(2)定义节点

在AVL树中，除了需要定义平衡因子bf之外，还需要定义指向节点父节点的指针。方便我们来进行平衡因子的更新。

struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

同时和map一样，我们使用pair类型来进行数据的存储。

2.插入

(1)拆分

AVL树的插入就是AVL树的精髓所在，我们在插入节点的同时还需要对平衡因子进行控制。

AVL树的插入我们可以拆分成五个函数，其中四个为旋转函数，一个为主要的插入函数。

而这个主要的插入函数，我们还可以将其分为三个部分：找节点，插节点，更新平衡因子。而更新平衡因子后就需要判断是否需要进行旋转的操作。

在进行插入之前，我们将插入的节点定义为kv。

(2)找节点与插节点

这一过程与二叉搜索树是相同的，这里就不多赘述了。二叉搜索树

直接上代码：

		//初始化头结点
		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->right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->left;
			}
			else
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}

(3)更新平衡因子与旋转

更新平衡因子

每当我们插入一个节点的时候，就需要对该节点的所有父辈节点来进行平衡因子的更新。注意，当插入节点后，只有其父辈节点的平衡因子才会受到影响，而其他节点的平衡因子不会被影响。

可以根据每个节点的parent来找到其父亲节点，从而逐渐向上更新平衡因子。

当遇到以下两种情况平衡因子的更新停止。

1.某一父辈节点的平衡因子为0。

2.更新到根节点。

旋转

当更新之后的平衡因子为2或者-2的时候，不符合AVL树的平衡因子在-1~1之间的定义，此时需要发生旋转。触发旋转的条件与当前节点cur和它的parent有关。

当parent和cur的平衡因子分别为：

(1)2和1，触发左旋

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

用一张图来表示一下这个过程：

h表示某树的高度，当在红色部分处插入一个节点时，60的平衡因子变为1，30的平衡因子变为2。

此时就需要发生旋转：

通过旋转使树重新变成一棵AVL树，整个过程分为三步：

• 1.60的左子树置为30,30的右子树置为60的左子树。
• 2.将30与更上层的父辈节点链接起来。
• 3.将30和60的平衡因子都更新为0。

注意，由于AVL树是三叉树，因此在链接的时候需要将父节点也链接起来。因此在将60的左子树链接到30的右子树的时候，需要进行判空来避免空指针的解引用：

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

(2)-2和-1，触发右旋

右旋同样分为三步：

• 1.将30的右链接到60的左子树。将60链接到30的右。
• 2.将30与上层节点链接起来。
• 3.将30和60的平衡因子都更新为0。

	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}

(3)-2和1，左右双旋

当为-2和1或者2和-1的时候，仅仅靠单旋是解决不了问题的，这个时候我们就需要进行双旋：

左单旋：

右单旋：

无论是在红色部分或者蓝色部分插入节点，都会导致发生左右双旋。

左右双旋分为三步：

• 1.对30节点进行左单旋。
• 2.对90节点进行右单旋。
• 3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。

	void RotateLR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR =subL->right;
		int bf = subLR->_bf;
		RotateL(parent->left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}

(4)2和-1，右左双旋

右单旋：

左单旋：

无论是在红色部分或者蓝色部分插入节点，都会导致发生右左双旋。

右左双旋分为三步：

• 1.对90节点进行右单旋。
• 2.对30节点进行左单旋。
• 3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。

	void RotateRL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		int bf = subRL->_bf;
		RotateR(parent->right);
		RotateL(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

3.判断

我们可以建立一个函数来判断一棵树是否为AVL树。

我们使用递归来进行这一过程，依次判断各个子树是否为AVL树。

要判断我们就需要知道每一棵树的高度，此时我们需要构造一个求树的高度的函数Height。它也由递归来实现。

	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		if ((rightHeight - leftHeight) != root->_bf)
		{
			cout << "现在是：" << root->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}

4.完整代码及测试代码

完整代码

#pragma once
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
	{
		_root = nullptr;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->right);
	}
	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		if ((rightHeight - leftHeight) != root->_bf)
		{
			cout << "现在是：" << root->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}
	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR =subL->right;
		int bf = subLR->_bf;
		RotateL(parent->left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		int bf = subRL->_bf;
		RotateR(parent->right);
		RotateL(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	bool InsertNode(pair<int, int> 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->right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->left;
			}
			else
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}
		//更新插入节点以上的平衡因子
		while (parent)
		{
			if (cur == parent->left)
			{
				parent->_bf--;
			}
			else if (cur == parent->right)
			{
				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)
			{
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);//右单旋
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);//左单旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
			}
			else
			{
				assert(false);
			}
		}
	}
private:
	Node* _root;
};

测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"AVLTree.h"
void TestRotateR()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(0, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRotateL()
{
	AVLTree t;
	t.InsertNode(make_pair(0, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(5, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void Testbf()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(7, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(8, 1));
	t.InsertNode(make_pair(9, 1));
	t.InsertNode(make_pair(6, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(11, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRL()
{
	AVLTree t;
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(80, 1));
	t.InsertNode(make_pair(70, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestLR()
{
	AVLTree t;
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(70, 1));
	t.InsertNode(make_pair(80, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
int main()
{
	//TestRotateR();
	//Testbf();
	//TestRotateL();
	//TestRL();
	TestLR();
}

以上就是C++数据结构之AVL树的实现的详细内容，更多关于C++ AVL树的资料请关注我们其它相关文章！