数据结构总结

（未完待续）

基本概念

数据结构：

• 是数据项的结构化集合。
• 结构性的表现
  • 数据项之间的相互联系和作用
  • 或者理解为定义于数据项之间的某种逻辑次序
• 依据逻辑次序的复杂程度划分：
  • 线性结构
  • 半线性结构
  • 非线性结构

序列（sequence）

序列（sequence）：最基本的线性结构的统称。
序列（sequence）依据数据项之间的逻辑次序与其物理存储的对应关系不同，又可以进一步划分向量和列表：

向量（vector）

向量（vector）:所有数据项之间物理存储位置与逻辑次序完全吻合。此时的逻辑次序也称为秩（rank）

• 循秩访问（call-by-rank），静态存储策略。

列表（list）

列表（list）:所有数据项之间物理存储位置与逻辑次序不一定吻合。采用间接定址的方法通过封装后的位置（position）相互引用。

• 循位置访问（call-by-position）或者称为循链接访问（call-by-link），动态存储策略。

栈（stack）

栈（stack）：线性数据结构的一种，视作向量与列表的特例。对象的插入和删除限制在栈的一端。禁止操作的一端称为盲端。
栈顶（stack top）：可操作（插入和删除）的一端。入栈（push）与出栈（pop）。
栈底（stack bottom）：无法直接操作的盲端。

栈与递归

函数调用栈

调用栈（call stack）和执行栈（execution）:大部分操作系统中，每个运行的二进制程序都都配有一个调用栈，用来跟踪属于同一个程序的所有函数，记录它们之间的调用关系，并保证在每一个调用实例执行完毕之后，可以准确返回。
帧（frame）：调用栈的基本单位，每次函数调用时，都会相应的创建一帧：

• 记录了函数实例在二进制程序中的返回地址，局部变量，传入参数，还有上一帧的栈中地址。

逆序输出

进制转换

递归嵌套

栈混洗（stack permutation）：栈的数据从stackA——>stackS——>stackB。

括号匹配：

延迟缓冲：

逆波兰表达式（reverse Polish notation，RPN）：

试探回溯法

剪枝
试探
回溯

八皇后

迷宫寻径

队列（queue）

视作向量与列表的特例

基本概念

队列（queue）：线性数据结构的一种，对象的插入和删除限制在队列的两端。
队头（front）：允许取出元素的一端。出队（dequeue）:元素的删除操作。
队尾（rear）：允许插入元素的一端。入队（enqueue）：元素的插入操作。

队列应用

循环分配器

银行服务模拟

树

• 半线性结构（semi-linear structure）
• 其中的元素之间并不存在天然的直接后继或者直接前驱关系。但是只要附加某种约束（比如遍历），就可以在树的元素之间确定某种线性次序关系。因此树属于半线性结构

叶节点（leaf）：无孩子的节点。
树的高度（height）:树的所有节点深度的最大值称作该树的高度。教材中约定，单个节点的树高度为0，空树的高度为-1。

• 如果根结点第0，层数=深度=高度-1
• 如果根结点第1，层数=深度=高度

节点的高度：任一节点V的高度对应于子树的高度subtree（V）。

多叉树（k-ary tree）

k叉树（k-ary tree）：每个节点的孩子均不超过k个的有根树。

多叉树的表示法

父节点表示法：一个向量表，存两个属性，一个是data，一个是parent
孩子节点表示法：一个向量表，存两个属性，一个是data，一个是children（组织成vector或者list）
父亲+孩子节点表示法：一个向量表，存三个属性，一个是data，一个是parent，最后一个是children（组织成vector或者list）

有序树（ordered tree）

有序树（ordered tree）：同一节点的所有孩子之间必须具有某一线性次序。这个约束条件使得作为多叉树特例的二叉树有足够的能力表示任何一颗多叉树。

长子+兄弟转换法

同一列的是长子，同一行的是兄弟

二叉树（binary tree）

二叉树（binary tree）：每个节点的读书均不超过2。
有序二叉树（ordered binary tree）：同一父节点的孩子都可以左右相互切分。
真二叉树（proper binary tree）：不含一度节点的二叉树

完全二叉树（complete binary tree）

完全二叉树（complete binary tree）：

• 对于使用队列操作的层次遍历，前(n/2向下取整）次迭代中都有左孩子入队，前(n/2向上取整然后-1）次迭代中都有右孩子入队
• 叶节点只出现在最底部的两层。
• 高度为：h=（log n）的向下取整 //根节点设置为高度0的情况下
• 规模介于2^h与2^(h+1)-1
• 根节点为1，左孩子编号等于2v,右孩子编号2v+1

满二叉树（full binary tree）

• 规模2^(h+1)-1

遍历

递归式遍历
迭代版先序遍历
迭代版中序遍历
迭代版后续遍历
层次遍历

编码树

编码
解码
前缀无歧义编码（PFC）
huffman编码

二叉编码树

根通路串（root path string）

搜索树

对线性数据结构查找性能的改进。
如果既要求对象集合的组成可以高效率地动态调整，同时也要求能够高效率的查找，对于向量和列表这类线性结构是难以胜任的。
兼顾高效率的动态修改和高效率的静态查找，可以使用搜索树。
理想平衡和适度平衡，引入平衡二叉树结构，比如AVL树即使在最坏情况下，单次动态查找和静态查找也均在O（log n）时间内完成。

理想平衡和适度平衡

理想平衡：如果树的高度恰好为log n，向下取整，则成为理想平衡树 ，比如完全二叉树和满二叉树

适度平衡：渐进意义下适当放松标准的平衡性。渐进的不超过O(log n)
下面介绍的红黑树，AVL树，伸展树，kd-树都是适度平衡的变种。也可以归入平衡二叉搜索树之列。

搜索树的局部性

1. 刚刚被访问的节点，可能不久后就能访问到
2. 将被访问的下一个顶点，极可能就在不久之前被访问的某个节点附近

二叉搜索树（BST）

二叉搜索树（binary search tree）：处处都满足顺序性——任一节点r的左（右）子树中，所有节点均不大于（不小于）节点r
二叉搜索树的判定:任何一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降。

复杂度分析：
insert，remove，search时间：线性正比于查找路径的长度或者最终返回节点的深度。最坏情况下可能退化成为链表。

等价二叉搜索树

若两个二叉搜索树的中序遍历相同，则称它们彼此等价。
概括一下就是：上下可变，左右不乱。也就是说节点的左右相对关系是不变的，但是上下关系是可以改变的。
局部性：

1. 经过单词动态修改操作，至多只有O(log n)处局部不再满足限制条件。
2. 可以在O(log n)时间内，使这O(log n)处局（乃至全树）重新满足限制条件。

旋转调整（修复）

zig 顺时针旋转
zag 逆时针旋转

平衡二叉搜索树（BBST）

AVL树

平衡因子(balance factor)：其左，右子树的高度差。
各个节点的平衡因子绝对值不超过1。也就是各个节点左右子树高度差不超过1。

失重与重新平衡：
单旋与双旋：
统一重平衡算法：

伸展树（splay tree）

伸展树（splay tree）：

• 无须时刻都保持全树的平衡，但是却能够在任何足够长的序列上，保持分摊意义上的效率。
• 不需要对基本的二叉树节点结构，做任何附加的要求或者改动，不需要记录平衡因子或者高度之类的额外信息，故适用范围更广

利用了数据局部性，将刚刚被访问的节点，转移至树根附近。

伸展（splaying）：随着节点e的不断上升，两侧子树的结构也在不断的调整，这种过程也形象地称为伸展。

单层伸展树

节点e每次提升1层，直至成为树根

双层伸展树

节点e每次提升2层，直至成为树根。

zig-zig/zag-zag
zig-zig/zag-zag
zig/zag

复杂度分析：分摊的情况下，O（log n）

红黑数（red-black tree）

通过假想地引入外部节点（黑色），将二叉树真正扩展为真二叉树。

1. 根节点始终为黑色
2. 外部节点均为黑色
3. 其余节点若为红色，其孩子节点必为黑色
4. 从任一外部节点到根节点的沿途，黑节点的数目相等
5. 由1，2可知，红节点属于内部节点，且红节点的父节点和左右孩子肯定存在
6. 由3可知，红节点之父必为黑色，树的任一通路不会包含相邻的红节点。
   7 由4可知，所有外部节点的黑高度统一

所有外部节点的黑高度统一
特别的，根节点的黑高度也称为全树的黑高度，在数值上与外部节点的黑高度相等。
所有外部节点的黑高度为0.

双红修正
双黑修正

平衡多路搜索树

平衡二叉搜索树（BBST）的推广
当数据规模大到内存已经不足以容纳时候，常规平衡二叉搜索树的效率会大打折扣。其原因在于查找过程对外存的访问次数过多。

外部存储适合于批量式访问，不妨通过时间成本较低的多次内存操作，来替代时间成本相对较高的单次外存操作。

结合上面的思想，我们可以将通常的二叉树搜索树，改造为多路搜索树（等价变换）

四路搜索树：每个大节点拥有四个外部的分支。

• 通常是将二叉搜索树以两层为间隔合并。
• 一个大节点包含3个关键码和4个外部分支.

多路搜索树（multi-way search tree）：一般地，以k层为间隔如此重组，可以将二叉搜索树转化为等价的2^k路搜索树。

优点：

• 访问外存的方式相对于二叉搜索树已经发生了本质的变化，可以以大节点为单位读取一组（而不是一个）关键码。
• 这组关键码在逻辑上与物理上都彼此相邻，故可以以批量方式从外存一次性读出，且需要的时间与读取单个关键码几乎一样。
• 每组关键码的最佳数目，取决于不同外存的批量访问特性。可以根据扇区的容量等因素来计算。

B- 树

平衡多路搜索树的典型代表
B-树（B-tree）：m阶B-树，也就是m路平衡搜索树

所有外部节点的深度都相等，每个内部节点都存有不超过m-1个关键码，以及用以指示对应分支不超过m个引用。
各个节点的分支数应该介于m/2（向上取整）与m之间，故也称为(m/2向上取整，m)-树
B-树的外部节点：
B-树的宽度
B-树的叶节点

• 非常适合在相对较小的内存中，实现对大规模数据的高效操作。

复杂度：O(log_mN)

kd-树（k-dimensional tree）

四叉树与八叉树的一般性推广
递归定义的平衡二叉树
一维范围查询（range query）：给定直线L上的点集P={p₀,p_n-1},对于任一区间R=[x₁,x₂],P中的哪些顶点落在其中？
离线方式和在线方式
输出敏感（output sensitive）的算法
平衡二叉搜索树解决一维度范围i查询问题， 找到最低共同祖先，忽略
分割成为矩形，举行左边底边开，右边和顶边封闭
每次切分都在中位点（对应的坐标排序居中者）。 以保证全树的高度不超过O(log n)
复杂度O（根号n）

图

非线性结构

邻接矩阵

邻接表

BFS

DFS

拓扑排序

优先级队列与堆

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。
最大堆:，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
最小堆:，任何一个父节点的值，都小于或等于它左、右孩子节点的值。

完全二叉堆

上滤与下滤

左式堆

串

字符串

串匹配

散列表

看这篇文章即可：哈希表（散列表）详解

注解

偏序只对部分元素成立关系R，全序对集合中任意两个元素都有关系R。

• 集合的包含关系是偏序，因为两个集合可以互不包含。
• 复数中的大小就是偏序，其中虚数不能比较大小。
• 实数中的大小关系是全序，两个实数必有一个大于等于另一个。

参考资料

数据结构 邓俊辉