排序二叉树, 数据结构中的hello world

今年把两年前写的这篇文章重写了一遍。作为AlgoXY的第一章。
重写后，不要求读者懂任何一门特定的编程语言。全部算法提供了两种描述：
  伪代码描述和数学函数描述。

有些地方给出了C++, Python, Haskell的代码片段，但是读者可以完全不懂这些具体的编程语言。

这一章主要希望说，BST实际上可以认为是数据结构这个世界中的 Hello world内容。
有些读者可能认为Array和Linked List这样更为基础的数据结构才是 Hello World，而轮不到二叉树。
这主要是由于，Array的纯函数实现是基于树的，其实比较难。所以我不得不把Array放到后继章节。

大致outline一下这章的内容：
  - 通过一个10行的程序，展示Balanced BST如何把圣经中的所有词汇统计出来，使得读者感性认识BST的威力。
  - 描述BST的逻辑数据结构
  - BST的插入，为什么我们说BST是数据结构中的hello world
  - 前序遍历，以及树排序，并给出一个很著名的面试题：给出BST的前序遍历和中序遍历结果，重建树
  - 查找操作，包括lookup, min/max,以及succ/pred，并指出后者为imperative only的问题。前阵我在TL给
出过讨论；
  - 删除操作，给出一个特别简洁的递归删除算法，并提出一个对称练习题。
  - 随机构建，简述了随机构建的思路，并作为练习题留给读者。
  - 附录和参考文献。

PDF可以从这里下载：https://sites.google.com/site/algoxy/bstree/bstree-en.pdf
web: https://sites.google.com/site/algoxy/bstree

评论

1 楼 liuxinyu95 2011-04-21  

GitHub上公开了原稿：
https://github.com/liuxinyu95/AlgoXY
内容由GNU FDL保护，源代码由GNU GPLv3保护。