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