【C++进阶】AVL树的模拟实现（附源码）

C/C++
143
0
0
2024-05-03
【C++】复杂的菱形继承 及 菱形虚拟继承的底层原理
上一篇
【初阶数据结构与算法】——手撕八大经典排序算法
下一篇

一.AVL树的概念

我们知道，二叉搜索树的效率很高，如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下，为了解决这个问题，AVL树（平衡二叉树）就出现了。

AVL树的性质：

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

上图就是一个AVL树，每个节点上的数字为这个节点的平衡因子，绝对值不超过1 ；

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log N)，搜索时间复杂度O(logN)。

接下来让我们来模拟实现AVL树。

有两种方法可以模拟实现AVL树：

  • 使用平衡因子控制高度
  • 使用高度函数控制高度

本文将采用平衡因子的方法控制高度。

二.AVL树的模拟实现

AVL树的节点

这里我们使用三叉链的结构，便于找到父节点

  • 左指针（_left）
  • 右指针（_right）
  • 父指针（_parent）
  • 平衡因子（balance factor，简写 _bf）

代码语言：javascript

复制

template <class K,class V>   //这里我们采用KV模型
struct AVLTreeNode
{
	pair<K,V> _kv;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;

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

};

AVL树的插入 Insert

首先就是找到新插入节点的位置，这和二叉搜索树的操作是一样的，插入完成后，不要忘记更新cur的parent指针。

插入完成后要更新平衡因子，下图说明了如何更新平衡因子

接下来将会详细说明如何旋转。

旋转一共分为四种情况：

  1. 左单旋
  2. 右单旋
  3. 左右双旋
  4. 右左双旋
左单旋

左单旋的条件是：cur的平衡因子为1并且parent的平衡因子为2，也就是单纯的右边高；

具体看下图：

代码语言：javascript

复制

void RotateL(Node*parent)  //左旋
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
        Node* ppnode = parent->_parent;   //提前保存parent的父节点，便于后续cur父指针的更新

		parent->_right = curleft;  //核心操作1
        cur->_left = parent;  //核心操作2
		if (curleft)  //当curleft不为nullptr时
		{
			curleft->_parent = parent;
		}

		parent->_parent = cur;   //parent的父指针指向cur
        //链接ppnode和cur
		if (ppnode == nullptr)  //当ppnode为nullptr时，即parent是根节点，旋转的是整个子树
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			//当ppnode不为nullptr时，即parent不是根节点，旋转的是局部子树，此时要链接ppnode和子树
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}

		parent->_bf = cur->_bf = 0;  //调整平衡因子

	}
 右单旋

右单旋的条件是：cur的平衡因子为-1并且parent的平衡因子为-2，也就是单纯的左边高

代码语言：javascript

复制

void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
        Node* ppnode = parent->_parent;  //提前保存好parent得父节点，便于后续cur父指针的更新

		parent->_left = curright;   //核心操作1
        cur->_right = parent;    //核心操作2
		if (curright)   //更新curright的父指针，注意要判断是否为空
		{
			curright->_parent = parent;
		}
		
		parent->_parent = cur;   //更新parent的父指针
        //链接cur与ppnode
		if (ppnode == nullptr)
		{
			_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;   //调整平衡因子
	}
 左右双旋

左右双旋的条件为：cur的平衡因子为1并且parent的平衡因子为-2

此时可以复用前面的左单旋和右单旋，但是要特别注意curleft（或是curright），parent，cur的平衡因子的更新。

代码语言：javascript

复制

void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		RotateL(parent->_left);
		RotateR(parent);
		//调整平衡因子
		if (curright->_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (curright->_bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (curright->_bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else
			assert(false);
	}
 右左双旋

右左双旋的条件为：cur的平衡因子为-1并且parent的平衡因子为2

代码语言：javascript

复制

void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		RotateR(parent->_right);
		RotateL(parent);
		//调整平衡因子
		if (curleft->_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (curleft->_bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (curleft->_bf == -1)
		{
			parent->_bf = 0;
			cur->_bf = 1;
			curleft->_bf = 0;
		}
		else
			assert(false);
	}

三.AVL树的验证

  • 首先验证是否是二叉搜索树，即中序遍历一趟是否是有序序列
  • 检查平衡因子是否正确

代码语言：javascript

复制

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 isBlance()
{
	return isBlance(_root);
}

bool isBlance(Node* root)
{
	if (root == nullptr)  //空树也是AVL树
		return true;
	int leftHeight = Height(root->_left);
	int rightHeight = Height(root->_right);

	if (abs(rightHeight - leftHeight) > 1)   //检查平衡因子是否正确
		return false;
	return isBlance(root->_left) && isBlance(root->_right);
}

四.AVL树的性能

  • AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN
  • 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
  • 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

五.源码

AVLTree.h

代码语言：javascript

复制

template <class K,class V>
struct AVLTreeNode
{
	pair<K,V> _kv;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;

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

};


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* 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
				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 (cur == parent->_left)   //左子树增高，平衡因子--
				parent->_bf--;
			else if (cur == parent->_right)  //右子树增高，平衡因子++
				parent->_bf++;

			if (parent->_bf == 0)   //平衡因子==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)  //左旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)  //右旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)  //右左双旋
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)  //左右双旋
				{
					RotateLR(parent);
				}
				else
					assert(false);
			
			}
			else
				assert(false);
		}

		return true;

	}

	void RotateL(Node*parent)  //左旋
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;  //核心操作1
		if (curleft)  //当curleft不为nullptr时
		{
			curleft->_parent = parent;
		}
		cur->_left = parent;  //核心操作2

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

		if (ppnode == nullptr)  //当ppnode为nullptr时，即parent是根节点，旋转的是整个子树
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			//当ppnode不为nullptr时，即parent不是根节点，旋转的是局部子树，此时要链接ppnode和子树
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}

		parent->_bf = cur->_bf = 0;  //调整平衡因子

	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}
		cur->_right = parent;
		Node* ppnode = parent->_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;
		}

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

	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		RotateR(parent->_right);
		RotateL(parent);
		//调整平衡因子
		if (curleft->_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (curleft->_bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (curleft->_bf == -1)
		{
			parent->_bf = 0;
			cur->_bf = 1;
			curleft->_bf = 0;
		}
		else
			assert(false);
	}

	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		RotateL(parent->_left);
		RotateR(parent);
		//调整平衡因子
		if (curright->_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (curright->_bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (curright->_bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else
			assert(false);
	}
private:
	Node* _root=nullptr;
};
【C++】复杂的菱形继承 及 菱形虚拟继承的底层原理
上一篇
【初阶数据结构与算法】——手撕八大经典排序算法
下一篇