第4章 树

对于大规模输入，链表的线性访问时间是不可接受的。

在本章里，我们先介绍二叉搜索树这种简单的数据结构，其大部分操作的平均访问时间是。接着，我们从理论上给出了对二叉搜索树的第一种简单修改，保证了在最坏情形下的运行时间上界是。再接着，我们给出了对二叉搜索树的第二种修改，从本质上保证了对长指令的每种操作的运行时间都是。

二叉搜索树是实现两个库集合类TreeSet和TreeMap的基础，这两个库集合类被许多应用使用。由于树这种结构在计算机科学中是一种非常有用的抽象，所以我们会讨论如何在其他更普遍的应用中使用树的，比如

• 如何应用树来实现几种流行的操作系统的文件系统。
• 如何使用树来计算表达式的值。
• 如何使用树来支持平均情形的的搜索时间，及如何优化为最坏情形下的上界，及当数据保存在硬盘上时，如何实现才能保证最坏情形下有的搜索时间上界。
• 讨论如何使用集合类TreeSet和TreeMap。