深入探索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;}}