本文将介绍AVL树及其插入、删除操作，最后使用C编程语言实现基于平衡因子（balance factor）的AVL树。
什么是AVL树？
AVL树（AVL tree）是前苏联计算机科学家Adelson-Velsky和Landis发明的一种自平衡二叉查找树（self-balancing binary search tree）。它有两大属性，一个是继承自二叉查找树的查找属性（binary search property），另一个是AVL树特有的平衡因子属性（balance factor property）。
节点的平衡因子是节点两个子树的高度差
BalanceFactor(N) = Height(RightSubtree(N)) – Height(LeftSubtree(N))
AVL树限定任意节点两个子树的高度差最大为1
BalanceFactor(N) ∈ {–1,0,+1}
由于AVL树是一种二叉查找树，所以它只能维持大体平衡，无法达到完全平衡。AVL树通过限定任意节点两个子树的高度差最大为1来保证二叉查找树的大体平衡，如果高度差大于1，则需要重新平衡。
AVL树只能大体平衡，2-3-4树通过可变的元素数量可完全平衡。
1
/ \ (1)
5 9 / \
/ (5) (6 9)
6
AVL树 2-3-4树
插入、删除操作
插入、删除操作后需要更新所有被影响的节点的平衡因子，稍作观察就能发现这些节点一定在从根节点到被插入、删除节点的路径上，这些节点都是被插入、删除节点的祖先节点（ancestors）。如何更新这些节点的平衡因子？如果更新后的平衡因子为+2或-2，如何重新平衡（rebalance）？
为了更好的描述，我们把根节点到被插入、删除节点的路径称作查找路径（search path），这条路径贯穿被插入、删除节点的所有祖先节点。
插入6的查找路径为1,9
1
/ \
5 9
删除6的查找路径为1,9
1
/ \
5 9
/
6
所以插入、删除操作只会影响查找路径上节点的平衡因子，而不会影响别的节点的平衡因子。
AVL树的插入操作
插入操作可能会导致查找路径上节点的高度增大，所以需要更新查找路径上节点的平衡因子，如果更新平衡因子后节点违背了平衡因子属性，则需要通过旋转进行重新平衡。过程如下：
- 从被插入节点的父节点开始，按照查找路径原路返回直到根节点，返回过程中更新当前节点的平衡因子，如果发现当前节点更新后的平衡因子绝对值大于1，则使用旋转操作进行重新平衡；
- 达到以下任一条件则完成所有操作。
a. 节点高度保持不变；
b. 旋转操作（该节点必然恢复原高度）；
c. 到达根节点。
AVL树的删除操作
与插入操作类似，删除操作可能会导致查找路径上节点的高度减小，所以需要更新查找路径上节点的平衡因子，如果更新平衡因子后节点违背了平衡因子属性，则需要通过旋转进行重新平衡。过程如下：
- 从被删除节点的父节点开始，按照查找路径原路返回，返回过程中更新当前节点的平衡因子，如果发现当前节点更新后的平衡因子绝对值大于1，则使用旋转操作进行重新平衡；
- 达到以下任一条件则完成更新和修复操作。
a. 节点高度保持不变；
b. 旋转操作且旋转后节点恢复原高度；
c. 到达根节点。
综上，AVL树的插入操作最多只需要一次旋转操作就能重新平衡，而删除操作则可能需要多次旋转操作才能重新平衡。
AVL树的实现
经过较长时间的学习和分析，使用C编程语言实现了一个完整的基于平衡因子的AVL树，源码链接为https://github.com/xieqing/avl-tree，该实现通过了较完整的测试用例的验证，README.md对AVL树的实现做了详尽的分析，另外，通过一个简单的使用示例avl_example.c，您可以快速了解它的使用方法。
欢迎大家指正。
/*
* Copyright (c) 2019 xieqing. https://github.com/xieqing
* May be freely redistributed, but copyright notice must be retained.
*/
