trinkle

平衡二叉搜索树有诸多变种，以下将介绍其中几位成员。首先，鉴于数据访问的局部性在实际应用中普遍存在，按照最常用者优先的策略引入伸展树。接下来，通过对平衡二叉树的推广，引入平衡多路搜索树，并着重讨论其中比较典型的B树。对照4阶B树，引入红黑树，红黑树不仅仅能保证全树的适度平衡，从而有效地控制单次操作的时间成本并可将每次重平衡操作的时间复杂度控制在常数时间范围内。

此前我们涉及了诸多排序算法，针对向量和列表的起泡排序、归并排序以及选择排序等算法，基于散列的桶排序算法，借助堆的性质的就地堆排序算法。在此外，排序算法还有快速排序算法，希尔排序算法，其构思和技巧各具特色，在不同应用中的效率也各有千秋。

串或字符串属于线性结构，但字符串作为数据结构，结构简单，规模庞大，元素重复率高。所谓结构简单，是指字符表本身的规模不大，甚至可能极小。以生物信息序列为例，参与蛋白质合成的氨基酸只有20种，而构成DNA序列仅有4种。因此，以字符串形式表示的海量文本处理技术，一直都是相关领域的研究重点。

此前的搜索树和词典结构都支持覆盖全集的访问和操作，其中存储的每一数据对象都可作为查找和访问目标。搜索树结构需要在所有元素之间定义并维护一个显式的全序关系，而词典结构从内部强制地在对象和对应的秩之间建立起某种关联关系，隐式地定义了一个全序关系。优先级队列将操作对象限定于当前的全局极值者。比如，在所有鸟类中，查找种群规模最小者。这一访问方式称为循优先级访问。

借助数据结构来表示和组织的数据结构，将所有数据视作一个整体统筹处理，进而提高信息访问的规范性及其处理的效率。例如，借助关键码查找和访问数据元素，其中最典型的例子即为词典。逻辑上的词典，为由一组数据构成的集合，其中各元素都是由关键码和数据项合成的词条。

任何词条之间可相互比较大小是有序向量得以定义，以及二分查找赖以成立的基本前提。通过对二分查找策略的抽象和推广，定义和实现二叉搜索树结构。二叉搜索树有诸多变种，各具特色，各有所长，也有各自适用范围。为有效控制树高，二叉树的性能主要取决于树高，故应在节点数目一定的情况下尽可能地减小树高，相应地，尽可能使兄弟子树地高度彼此接近，即全树尽可能地平衡。平衡二叉搜索树通过对树中每一局部增加某种性质来保证二叉树的适度平衡性。

在城市交通图中联接于各公交站之间的街道，或者在互联网中联接于IP之间的二元关系，这类信息往往可表述为定义于一组对象之间的二元关系。相互之间均可能存在二元关系的一组对象，属于非线性结构。图结构是描述这类信息的典型结构，通过遍历将其转化为半线性结构，进而借助树的相关算法解决问题。

树是一种分层结构，而层次化这一结构几乎蕴含于所有事物及其联系中，称为其本质属性之一。从文件系统、互联网域名系统，一直到地球生态系统乃至人类社会系统，层次化特征和层次化结构均无所不在。二叉树不再是简单的线性结构，但确定某种次序后具有线性特征，故树属于半线性结构。

树等价于无环联通图，因此与一般的图相同，树也由一组顶点和联接于其间的若干条边组成，故任一节点与根节点之间存在着唯一路径。

相对于一般序列结构，栈和队列的操作仅限于逻辑上特定的某端，二者元素接受操作的次序不同，简而言之，栈是先进后出，而队列为先进先出。在信息处理领域，栈和队列的身影随处可见，不少程序设计语言即建立在栈结构之上，我们日常生活中对自然资源和社会资源分配、调度银行和医院服务窗口可借助队列实现合理和优化的分配。

根据是否修改数据结构，所有操作分为两类方式

• 静态：仅读取，数据结构的内容和组成不变
• 动态：需写入，数据结构的局部或整体将改变

与操作方式相对应的，数据元素的存储和组织形式也分为两种

• 静态：数据空间整体创建和销毁
• 动态：为各个数据元素动态地分配和回收的物理空间，相邻元素记录彼此的物理地址，在逻辑上形成一个整体，可支持高效的动态操作。

列表是采用动态存储的典型结构，循位置访问，通过节点之间的相互引用找到特定的节点。借助列表设计算法时，应更多地借助逻辑上相邻元素之间的位置索引。