说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
动态集合：数学中的集合是不变的，而算法中操作的集合却可以随着时间的改变增大、缩小或产生其他变化。本部分的10-14章介绍在计算机上表示和操纵有穷动态集合的一些基本技术。
动态集合的常见操作包括：查找、插入、删除、最大、最小、按序下一个、按序前一个。执行一个集合操作的时间通常是通过作为参数给出的集合的大小来度量的。
常见集合该要说明如下：
2、栈、队列、链表以及有根树：在第10章说明
3、散列表：在第11章说明。这种结构支持字典操作，即插入、删除、查找。在最坏情况下为做一次散列查找操作需要Θ(n)的时间；散列操作的期望时间为O (1)。对散列操作的分析要用到概率论，不过本章只注重应用、整理结论。
4、二叉查找树：在第12章说明。它支持前面列出的所有动态集合操作。在最坏情况下，在一个有n个元素的树上每个操作所需的时间为Θ(n)，但对一棵随机构造的二叉查找树，每个操作的期望时间是O (lgn)。二叉查找树是很多其他数据结构的基础。
5、红黑树：在第13章说明。它是二叉查找树的一种变形。和一般的二叉查找树不同，红黑树始终有着良好的性能：在最坏情况下，它所支持的操作运行时间为O (lgn)。红黑树是平衡二叉查找树。第18章将介绍另一种平衡查找树，称为B树。
6、增强型红黑树：第14章介绍。红黑树增强后，使其可以支持不在上述基本操作中的一些操作。首先对红黑树进行增强，使其能支持动态维护一个关键字集合的顺序统计量。然后，做另一种增强，使之支持对实数区间的动态维护。
网友评论