【数据结构】AVL树相关知识详细梳理

1. AVL树的概念

AVL的全称是Adelson-Velsky-Landis，其名称来源于其发明者Adelson、Velsky和Landis，

是平衡二叉树搜索树。

它的出现是由于二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这个解决办法就是AVL树。

AVL树是具有以下性质的二叉搜索树：

1. 它的左右子树都是AVL树。
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1。

AVL树是高度平衡的二叉搜索树。如果它有n个结点，其高度可保持在 $log_2N$ ,搜索的时间复杂度O（ $log_2N$ ）。并且克服了普通二叉搜索树可能退化，导致搜索效率大大降低的缺点。

2. AVL树原理

2.1 节点结构

AVL树是通过对节点进行调整来控制树的高度以达到两端平衡，那么它是如何调整节点的呢？

当插入节点打破了AVL树的规则----左右子树高度之差的绝对值超过1后，就会对节点进行旋转来降低子树的高度，来达到左右子树的相对平衡，避免树结构退化。

为了方便对节点进行调整和检测，我们引入平衡因子的概念，即在每个树节点中增加一个int类型的变量来记录左右子树的高度差（这里是右子树高度减左子树高度），这样一来，通过分析平衡因子的大小，我们就可以判断节点是否需要旋转处理。

显然，平衡因子的更新很多时候是牵一发而动全身的，例如：

因此，通过平衡因子维护树结构的平衡既带来了便利，又带来了麻烦，我们往往需要从插入节点开始向上不断更新平衡因子，为了解决二叉树在向上遍历时的麻烦，我这里将节点设置为三叉，即一个节点同时拥有父节点，左子树节点，右子树节点的指针。

2.2 更新平衡因子

在对节点进行调整前，首先要维护平衡因子，每次插入或旋转节点后，都要对相关平衡因子进行更新，旋转操作也是当发现平衡因子值异常（绝对值大于1）时才执行的。

首先，二叉搜索树的插入节点一定是叶节点，插入节点为父节点的左子树的时候，父节点的平衡因子 -1，插入节点为父节点的右子树时，父节点的平衡因子 +1。

然后，为了向上不断更新平衡因子，我们需要总结平衡因子更新的规律：

1. 更新后的平衡因子为 1 或 -1（说明插入节点前，父节点的平衡因子为0），说明子树的高度变高，需要继续向上更新平衡因子。

2. 更新后的平衡因子为 0（说明插入节点前，父节点的平衡因子为-1或1，插入节点在较矮的树那边），说明子树的高度不变，不需要再向上更新平衡因子了。

3. 更新后的平衡因子为2 或 -2（说明插入节点前，父节点的平衡因子为-1或1，且插入节点在较高的子树那边），此时破坏了平衡规则，需要进行旋转调整。

情况1：

情况2：

情况3：

2.3 旋转（插入）

二叉平衡搜索树通过旋转操作来改变节点之间的连接关系以降低数的高度，保持平衡，同时不破坏搜索树的规则。那么是如何旋转的呢？

首先，旋转分为四种：

1. 右单旋。

2. 左单旋。

3. 右左双旋。

4. 左右双旋。

下面通过概括图来分别描述这几种旋转对应的情况，以及如何完成旋转：

右单旋：

从图中可以看出，当根节点平衡因子为-2（此时左子树必定存在），且其左子树平衡因子为-1时，要进行右单旋，调整完毕后，subL和pRoot的平衡因子皆更新为0，此时子树的高度等于插入前的高度，不需要再向上更新。

左单旋：

类似于右单旋，当根节点平衡因子为2（此时右子树必定存在），且其左子树平衡因子为1时，要进行左单旋，调整完毕后，subL和pRoot的平衡因子皆更新为0，此时子树的高度等于插入前的高度，不需要再向上更新。

右左双旋：

左右双旋：

和右左双旋是镜像的操作，这里不再详细说明。

看到这里，想必你以及懂得了什么叫做旋转，也就是把下面的节点“转”到上面来，把上面的“转”下去，以到达平衡左右子树，缩小左右子树高度差的效果。

2.4 删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，最差情况下一直要调整到根节点的位置，原理比插入更加繁琐，但也是基于旋转的原理之上的，我们只理解插入时的情况就够用了，感兴趣可以自行了解AVL树删除的实现原理。

3. AVL树结构模拟实现

总体结构：

template<class T>//AVLTree节点
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);//AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot);}//AVL树的遍历//void Inorder()//{//	return _Inorder(_pRoot);//}private://AVL树的遍历//void _Inorder(Node* pRoot);//根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* pRoot);//获取树高度size_t _Height(Node* pRoot);//右单旋void RotateR(Node* pParent);//左单旋void RotateL(Node* pParent);//右左双旋void RotateRL(Node* pParent);//左右双旋void RotateLR(Node* pParent);Node* _pRoot;//根节点
};

获取树高：

//获取树高度
template<class T>
size_t AVLTree<T>::_Height(Node* pRoot)
{if (pRoot == nullptr)return 0;size_t leftsize = _Height(pRoot->_pLeft)+1;size_t rightsize = _Height(pRoot->_pRight)+1;return leftsize >= rightsize ? leftsize : rightsize;
}

插入节点：

template<class T>
bool AVLTree<T>::Insert(const T& data)
{//树为空，直接插入if (_pRoot == nullptr){_pRoot = new Node(data);return true;}//根据比较规则找到插入位置Node* pcur = _pRoot;Node* parent = nullptr;while (pcur){if (data == pcur->_data)return false;parent = pcur;if (data > pcur->_data)pcur = pcur->_pRight;elsepcur = pcur->_pLeft;}//直接插入并更新平衡因子if (data > parent->_data){pcur = new Node(data);parent->_pRight = pcur;pcur->_pParent = parent;parent->_bf += 1;}else{pcur = new Node(data);parent->_pLeft = pcur;pcur->_pParent = parent;parent->_bf -= 1;}while (parent){// 如果插入位置子树的根平衡因子为0，则子树高度不变，不需要向上更新if (parent->_bf == 0){//插入完成，返回真return true;}// 违反avl树规则，需要旋转if (parent->_bf == 2){//右子树平衡因子为1，需要左单旋if (parent->_pRight->_bf == 1){RotateL(parent);//旋转后子树高度不变，不需要继续向上更新return true;}//右子树平衡因子为-1，需要右左双旋else if (parent->_pRight->_bf == -1){RotateRL(parent);//双旋后子树高度不变，不需要再向上更新return true;}}// 违反AVL树规则，需要旋转if (parent->_bf == -2){//左子树平衡因子为-1，需要右单旋if (parent->_pLeft->_bf == -1){RotateR(parent);//旋转后子树高度不变，不需要继续向上更新return true;}//左子树平衡因子为1，需要左右双旋else if (parent->_pLeft->_bf == 1){RotateLR(parent);//双旋后子树高度不变，不需要再向上更新return true;}}// 如果插入位置子树的根平衡因子为1/-1，则子树高度增加，需要向上更新if (parent->_bf == 1 || parent->_bf == -1){//如果parent不为根节点if (parent->_pParent){if (parent->_data > parent->_pParent->_data)parent->_pParent->_bf += 1;elseparent->_pParent->_bf -= 1;}}//向上更新parent = parent->_pParent;}
}

实现插入代码时，重点要理清插入以及旋转的逻辑，利用节点的三叉结构，循环向上更新平衡因子并进行旋转，这也是最难的部分。

右单旋：

//右单旋
template<class T>
void AVLTree<T>::RotateR(Node* pParent)
{Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;subL->_pParent = pParent->_pParent;//如果原pParent不为根节点if (pParent->_pParent){if (subL->_data > subL->_pParent->_data)subL->_pParent->_pRight = subL;elsesubL->_pParent->_pLeft = subL;}subL->_pRight = pParent;pParent->_pParent = subL;pParent->_pLeft = subLR;//如果subLR不为空if (subLR)subLR->_pParent = pParent;//更新平衡因子pParent->_bf = 0;subL->_bf = 0;//若subL为根节点，更新根节点if (subL->_pParent == nullptr)_pRoot = subL;
}

左单旋：

//左单旋
template<class T>
void AVLTree<T>::RotateL(Node* pParent)
{Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;subR->_pParent = pParent->_pParent;//如果原pParent不为根节点if (pParent->_pParent){if (subR->_data > subR->_pParent->_data)subR->_pParent->_pRight = subR;elsesubR->_pParent->_pLeft = subR;}subR->_pLeft = pParent;pParent->_pParent = subR;pParent->_pRight = subRL;//如果subRL不为空if (subRL)subRL->_pParent = pParent;//更新平衡因子pParent->_bf = 0;subR->_bf = 0;//若subL为根节点，更新根节点if (subR->_pParent == nullptr)_pRoot = subR;
}

右左双旋：

//右左双旋
template<class T>
void AVLTree<T>::RotateRL(Node* pParent)
{Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;//记录subRL原先的平衡因子int subRLbf = subRL->_bf;//先对subR右旋RotateR(subR);//再对pParent左旋RotateL(pParent);//更新平衡因子subRL->_bf = 0;//如果subRL原先的平衡因子为-1if (subRLbf == -1){pParent->_bf = 0;subR->_bf = 1;}//如果subRL原先的平衡因子为1else if (subRLbf == 1){pParent->_bf = -1;subR->_bf = 0;}//如果subRL原先的平衡因子为0else{pParent->_bf = 0;subR->_bf = 0;}//双旋后子树高度不变，不需要再向上更新
}

左右双旋：

//左右双旋
template<class T>
void AVLTree<T>::RotateLR(Node* pParent)
{Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;//记录subLR原先的平衡因子int subLRbf = subLR->_bf;//先对subL左旋RotateL(subL);//再对pParent右旋RotateR(pParent);//更新平衡因子subLR->_bf = 0;//如果subRL原先的平衡因子为-1if (subLRbf == -1){pParent->_bf = 1;subL->_bf = 0;}//如果subRL原先的平衡因子为1else if (subLRbf == 1){pParent->_bf = 0;subL->_bf = -1;}//如果subRL原先的平衡因子为0else{pParent->_bf = 0;subL->_bf = 0;}
}

验证用代码：

最后可以搭配两个验证AVL树的代码：

//AVL树的遍历（检测结果是否有序）
/*template<class T>
void AVLTree<T>::_Inorder(Node* pRoot)
{if (pRoot == nullptr)return;if (pRoot->_pLeft)_Inorder(pRoot->_pLeft);cout << pRoot->_data << ' ';if (pRoot->_pRight)_Inorder(pRoot->_pRight);
}*///根据AVL树的概念验证pRoot是否为有效的AVL树
template<class T>
bool AVLTree<T>::_IsAVLTree(Node* pRoot)
{//空树为AVL树，返回trueif(pRoot == nullptr)return true;//计算左右子树高度差int diff = _Height(pRoot->_pRight) - _Height(pRoot->_pLeft);if (diff != pRoot->_bf || (diff > 1 || diff < -1))//左右子树高度绝对值大于1，返回falsereturn false;else//继续向下检查左右子树是否是AVL树return true && _IsAVLTree(pRoot->_pRight) && _IsAVLTree(pRoot->_pLeft);
}

还可以依次插入以下节点同时画图验证正确性：

1. {16, 3, 7, 11, 9, 26, 18, 14, 15}
2. {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}