C++ AVLTree高度平衡的二叉搜索树深入分析

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树

左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子= 右子树高度-左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log2N) ，搜索时间复杂度O(log2N)

二、AVL树节点的定义

节点结构：三叉链结构（左、右、父），以及平衡因子bf+构造函数（左右为空，平衡因子初始化为0）

三、AVL树的插入

AVL树在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。步骤过程：

找到插入的位置：根据二叉搜索树的做法

进行插入：判断插入的位置是parent的左还是右

更新平衡因子：如果不平衡的话，就要进行旋转

找到插入位置（比较节点大小即可）：

• 插入的节点key值 > 当前位置的key值，往右子树走
• 插入的节点key值 < 当前位置的key值，往左子树走
• 插入的节点key值等于当前位置的key值，不能插入，返回false

插入之后，与二叉搜索树不同的是：我们还需要去进行平衡因子的更新，调平衡：

如果新增加的在右，平衡因子加加

如果新增加的在左，平衡因子减减

更新一个结点之后我们需要去进行判断，子树的高度是否发生了变化：

1.如果parent的平衡因子是0：说明之前parent的平衡因子是1或-1，说明之前parent一边高、一边低；这次插入之后填入矮的那边，parent所在的子树高度不变，不需要继续往上更新

2.如果parent的平衡因子是1或者-1：说明之前parent的平衡因子是0，两边一样高，插入之后一边更高，parent所在的子树高度发生变化，继续往上更新

3.平衡因子是2或-2，说明之前parent的平衡因子是1或-1，现在插入严重不平衡，违反规则，需要进行旋转处理

最坏的情况下：需要一直更新到根root：

我们更新平衡因子时第一个更新的就是parent,如果parent->_bf1或parent->_bf-1需要继续往上进行平衡因子的更新，向上迭代，直到parent为空的情况：

当parent->_bf = 2或parent->_bf==-2时，我们就需要进行旋转了：