二叉平衡树 AVLtype
status
date
slug
summary
tags
category
icon
password
Property
平衡二叉搜索树（Self-balancing binary search tree），又称AVL树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。具有以下性质：
- 左右子树都是AVL树
- 左右子树高度差（又称平衡因子）的绝对值不超过1
A树不为满足AVL树的规则，因为节点3的
|右子树的高度-左子树的高度|>1- 如果一颗二叉搜索树是高度平衡的，他就是AVL树，如果他有n个节点，其高度可保持在 ，搜索时间复杂度
二叉平衡树的实现
节点类和树类
定义二叉平衡树节点类模板：
定义二叉平衡树类模板：
插入节点
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为3步：
- 插入新节点
- 更新树的平衡因子
- 如果插入在「新节点父亲」的右边，父亲的平衡因子++（
_bf++） - 如果插入在「新节点父亲」的左边，父亲的平衡因子–（
_bf--） - 如果更新以后，平衡因子是 1 或者 -1（则之前一定为 0），说明父亲所在子树高度变了，需要继续往上更新。（最坏情况：往上一直更新到根节点）
- 如果更新以后，平衡因子是 0（则之前一定为 1 或者 -1），说明父亲所在子树高度没变（因为把矮的那边给填补上了），不需要继续往上更新
- 如果更新以后，平衡因子是 2 或者 -2，说明父亲所在子树出现了不平衡，需要旋转处理，让它平衡。
插入「新节点」，从该节点到根所经分支上的所有节点（即祖先节点）的平衡因子都有可能会受到影响，根据不同情况，更新它们的平衡因子：
「新节点父亲」的平衡因子更新以后，又会分为 3 种情况：
- 根据更新后树的平衡因子的情况，来控制树的平衡（旋转操作）
平衡化操作
右单旋 - 新节点插入较高左子树的最左侧
将新的节点插入到了 parent 左孩子的左子树上，导致的不平衡的情况：
引发右单旋的条件：
左单旋 - 新节点插入较高右子树的最右侧
将新的节点插入到了 parent 右孩子的右子树上，导致的不平衡的情况。
左右双旋 - 新节点插入较高左子树的右侧
将新的节点插入到了 parent 左孩子的右子树上，导致的不平衡的情况。这时需要的是先对 parent 的右孩子进行一次左旋，再对 parent 进行一次右旋。
h=0时：
右左双旋 - 新节点插入较高右子树的左侧
将新的节点插入到了 parent 右孩子的左子树上，导致的不平衡的情况。这时需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋。
h=1时：