引言

在数据结构和算法的世界里,平衡二叉搜索树(Balanced Binary Search Tree, BST)是一种非常重要的数据结构。AVL树(Adelson-Velsky和Landis发明的树)就是平衡二叉搜索树的一种,它通过自平衡来维护其性质:任何节点的两个子树的高度差至多为1。这一特性使得AVL树在插入、删除和查找操作中都能保持相对稳定的性能。

一、AVL树的基本概念

AVL树是一种自平衡的二叉搜索树,它的每个节点都包含四个属性:键值、左子树指针、右子树指针和高度。高度是从该节点到其任一叶子节点的最长路径上边的数量。

二、AVL树的性质

  1. 二叉搜索树性质:对于任意节点N,其左子树上所有节点的键值都小于N的键值,而右子树上所有节点的键值都大于N的键值。
  2. 平衡性质:对于任意节点N,其左子树和右子树的高度差至多为1。

三、AVL树的旋转操作

当在AVL树中插入或删除节点时,可能会破坏其平衡性质。为了恢复平衡,我们需要进行旋转操作。旋转操作包括四种情况:右旋转(RR)、左旋转(LL)、左右旋转(LR)和右左旋转(RL)。

  1. 右旋转(RR):当某个节点的右子树的高度比左子树高2时,需要进行右旋转。
  2. 左旋转(LL):当某个节点的左子树的高度比右子树高2时,需要进行左旋转。
  3. 左右旋转(LR):当某个节点的左子树的右子树高度过高时,需要先进行左旋转,再进行右旋转。
  4. 右左旋转(RL):当某个节点的右子树的左子树高度过高时,需要先进行右旋转,再进行左旋转。

四、C++实现AVL树

在C++中,我们可以使用类和结构体来实现AVL树。以下是一个简化的AVL树节点结构定义和旋转操作的伪代码实现。

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data);
private:
	// 右单旋
	void RotateR(Node* pParent);// /
	// 左单旋
	void RotateL(Node* pParent);// '\'
	// 右左双旋
	void RotateRL(Node* pParent);//  >
	// 左右双旋
	void RotateLR(Node* pParent);//  <

private:
	Node* _pRoot;
};

 1增加

bool Insert(const T& data)
	{
		Node* newnode = new Node(data);
		if (_pRoot == nullptr)
		{
			_pRoot = newnode;
			return true;
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _pRoot;
			while (cur)
			{
				if (cur->_data < data)
				{
					parent = cur;
					cur = cur->_pRight;
				}
				else if (cur->_data > data)
				{
					parent = cur;
					cur = cur->_pLeft;
				}
				else
				{
					return false;
				}
			}
			if (parent->_data < data)
			{
				parent->_pRight = newnode;
			}
			else
			{
				parent->_pLeft = newnode;
			}
			newnode->_pParent = parent;
			//更新平衡因子
			cur = newnode;
			while (parent)
			{
				if (cur == parent->_pLeft)
				{
					parent->_bf++;
				}
				else
				{
					parent->_bf--;
				}
				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_pParent;
				}
				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
					{
						RotateRL(parent);
					}
					break;
				}
				else
				{
					assert(false);
				}
			}
			return true;
		}
	}

2右旋转

// 右单旋
	void RotateR(Node* pParent)//  /
	{
		Node* pchild = pParent->_pLeft;
		Node* pchildr = pchild->_pRight;
		Node* grandfather = pParent->_pParent;
		if (pchildr)
		{
			pchildr->_pParent = pParent;
		}
		pParent->_pLeft = pchildr;
		pParent->_pParent = pchild;
		pchild->_pRight = pParent;
		if (pParent == _pRoot)
		{
			_pRoot = pchild;
			pchild->_pParent = nullptr;
		}
		else
		{
			if (grandfather->_pLeft == pParent)
			{
				grandfather->_pLeft = pchild;
			}
			else
			{
				grandfather->_pRight = pchild;
			}
			pchild->_pParent = grandfather;
		}
		pParent->_bf = pchild->_bf = 0;
	}

3.右左双旋

	// 右左双旋
	void RotateRL(Node* pParent)//  >
	{
		Node* pchild = pParent->_pRight;
		Node* pchildl = pchild->_pLeft;
		int bf = pchildl->_bf;
		RotateR(pchild);
		RotateL(pParent);
		pchildl->_bf = 0;
		if (bf == 1)
		{
			pParent->_bf = 0;
			pchild->_bf = -1;
		}
		else if (bf == -1)
		{
			pchild->_bf = 0;
			pParent->_bf = 1;
		}
		else
		{
			pParent->_bf = pchild->_bf = 0;
		}
	}

五、AVL树的应用

AVL树在需要频繁进行插入、删除和查找操作的场景中非常有用。例如,在数据库索引、文件系统的目录树等地方,AVL树都能提供高效的数据访问能力。

六、总结

AVL树作为一种平衡二叉搜索树,在维护其平衡性质的同时,也保证了高效的查找、插入和删除操作。通过旋转操作,AVL树能够在插入或删除节点后迅速恢复其平衡状态。在C++中,我们可以使用类和结构体来方便地实现AVL树,并将其应用到各种需要高效数据访问的场景中。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部