深入探索C++中的AVL树

引言

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

一、AVL树的基本概念

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

二、AVL树的性质

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

三、AVL树的旋转操作

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

右旋转（RR）：当某个节点的右子树的高度比左子树高2时，需要进行右旋转。
左旋转（LL）：当某个节点的左子树的高度比右子树高2时，需要进行左旋转。
左右旋转（LR）：当某个节点的左子树的右子树高度过高时，需要先进行左旋转，再进行右旋转。
右左旋转（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;
		}
	}