【算法学习】AVL平衡二叉搜索树原理及各项操作编程实现（C++）

AVLTree即（Adelson-Velskii-Landis Tree），是加了额外条件的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(nLogn)。平衡条件是任何节点的左右子树的高度相差不超过1.

在下面的代码中，编程实现了AVL树的建立、查找、插入、删除、遍历等操作。采用C++类封装。

AVL树中比较复杂的操作时插入和删除操作。在这里对插入和删除操作进行讲解。

AVL树的插入操作

向AVL树中插入元素可能会导致树失去平衡。但是，我们只需要调整插入点至根节点的路径上不满足平衡状态的各节点中深度最大的那个即可。假设该最深节点为X。导致X失去平衡可能有四种情况：

（1）插入点位于X的左子结点的左子树-左左。

（2）插入点位于X的左子结点的右子树-左右。

（3）插入点位于X的右子结点的左子树-右左。

（4）插入点位于X的右子结点的左子树-右右。

情况1和4是对称的，成为外侧插入，可以通过单旋转解决。而情况2和3也是对称的，成为内侧插入。通过双旋转解决。

针对情况1实施单旋转示例：

针对情况2实施双旋转示例：

AVL树的删除操作

删除操作也分为几种情况：

首先在树中搜寻是否有节点的元素值等于需要删除的元素。如未搜索到，直接返回。否则执行以下操作。

（1）要删除的节点是当前根节点T。

如果左右子树都非空。在高度较大的子树中实施删除操作。

分两种情况：

A、左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。

B、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。

如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。

（2）要删除的节点元素值小于当前根节点T值，在左子树中进行删除。

递归调用，在左子树中实施删除。

这个是需要判断当前根节点是否仍然满足平衡条件，

如果满足平衡条件，只需要更新当前根节点T的高度信息。

否则，需要进行旋转调整：

如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。

（3）要删除的节点元素值大于当前根节点T值，在右子树中进行删除。

过程与上述步骤类似。

具体请看代码。

这里仅列出我编程实现的代码，如发现bug，还有包涵和指正！

AVLTree.h：

关于上述树操作的画图讲解如下（手机拍摄，有点不清楚）：