AVL tree，比红黑树更朴素
AVL树发明于上世纪60年代，比红黑树早了近十年。

上一章里，我展示了用pattern matching实现的红黑树。本章我展示同样策略实现的AVL tree。相比于传统的基于旋转的解法，这一解法再次展示了简单一致的特点。

本章内容如下：
- 简单介绍；给出AVL树的高度与节点数的证明；
- 类比红黑树的思路；
- 解：
- pattern matching 的形式分析
- 子问题一： 如何更新平衡因子和增加的高度？
- 子问题二； 4个case中的平衡因子如何变化的推导和证明；
- Haskell实现
- 验证
- 删除算法作为习题留给读者
- 和传统旋转解法的对比，给出了算法描述和Python实现
- 对比和红黑树的差异。

原文连接和PDF (墙外)：
https://sites.google.com/site/algoxy/avltree

PDF:
https://sites.google.com/site/algoxy/avltree/avltree-en.pdf

源代码：
https://github.com/liuxinyu95/AlgoXY 1 楼 liuxinyu95 2011-08-15 PDF放了一份在github:
https://github.com/downloads/liuxinyu95/AlgoXY/avltree-en.pdf