简要记录数据结构的重要知识点。
前序遍历(preorder traversal)：对根节点的处理是在处理子节点之前进行的。以二叉树为例，先遍历根节点，再遍历左节点、右节点。
类比实例：遍历目录。其背后的逻辑可以用代码来解释：
def func(Root Node):
print(Root Node)
for each Child Node of Root Node:
func(Child Node)
中序遍历(inorder traversal)：对根节点的处理是在处理子节点之间进行的。以二叉树为例，先遍历左节点，再遍历根节点，最后遍历右节点。
类比实例：表达式树的读取。可以尝试将ab+cde+**的输入转换为(a+b) * (c*(d+e))。
后序遍历(preorder traversal)：对根节点的处理是在处理子节点之后进行的。以二叉树为例，先遍历左节点、右节点，再遍历根节点。
类比实例：统计目录内文件总容量。其背后的逻辑可以用代码来解释：
def size(Root Node):
for each Child Node of Root Node:
total_size += size(Child Node)
total_size += size(Root Node)
层序遍历(level-order traversal)：逐层处理节点，深度越小越优先。与以上三种遍历不同的是，层序遍历不采用递归时采用的栈结构，而是使用队列。
以上遍历在编码时，要注意应首先处理NULL的情形，再进行其余判断。
二叉树：二叉树的平均深度为。
二叉查找树(ADT)：对于二叉树中的任一节点X，X的左子树中所有的值均小于X的值，X的右子树中所有的值均大于X的值。易知二叉查找树的平均深度是O(logn)，增删查改的时间复杂度也为O(logn)。
AVL树(Adelson-Velskii和Landis)：由于二叉查找树在多次插入和删除后可能不平衡，故产生了带有平衡条件的二叉查找树--AVL树。AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树。实践中，若单次插入使AVL树失衡，通过单旋转/双旋转操作来在O(logN)内平衡树。
当然，二叉树还有很多分类，例如斜树、完全二叉树、满二叉树等。
伸展树(splay tree)：二叉查找树和伸展树的单次最坏运行时间均为O(N)，但二叉查找树的连续M次最坏运行时间为O(MN)，伸展树的连续M次最坏运行时间为O(MlogN)，即每次操作的摊还代价是O(logN)。
伸展树的基本想法是，当一个节点被访问后，它就要经过一系列AVL树的旋转放到根上。实际操作中，通过对之字形(zig-zag)和一字形(zig-zig)的不同展开，在将访问节点移动到根处的基础上，将访问路径上大部分节点的深度大致减少一半。
对于二叉树的基本知识，知乎上有一篇讲得很棒的博客。
阶为M的B树有如下结构特性：
1 树的根要么为一片树叶，要么其儿子数在2和M之间；
2 除根外，所有非树叶节点的儿子数在和M之间；
3 所有的树叶都在相同的深度上。
所有数据都存储在树叶上，每个内部节点上皆有指向该节点各儿子的指针P1，P2...，Pm和分别代表在子树P2，P3...，Pm中发现的最小关键字的值k1，k2...，km-1。每次find操作时，都从根开始，依据查找的关键字和存储在节点上值来确定当前层在n个方向中的一个方向，直到在最底层找到对应数据。
在插入时若当前树的平衡被破坏(阶为M的B树的某一个节点的儿子数大于M)，常通过分裂节点来解决，一些情况下也可以将数据迁移到临近的节点中。同理，删除节点时若破坏平衡，可通过与周围节点进行合并来解决。
对于一次find操作，途径的节点个数为，在路径上的每个节点需要花费O(logM)来确认分支的方向，故find操作的时间复杂度为O(logN)。对于一次插入/删除操作，在某个节点处，最坏时需要O(M)来调整该节点所有信息，整体运算的最坏运行时间为。
B树的最大深度为。从运行时间考虑，M最优选择为3或4；从数据库应用考虑，为了使内部节点装满一个磁盘区块，常有。
| 实现方法\操作 | Find_Kth | Find_Key | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | 常数时间 | 线性时间 | 线性时间 | 线性时间 |
| 链表 | 线性时间 | 线性时间 | 线性时间 | 线性时间 |
链表在插入和删除元素时的时间主要花在遍历上。若已经拿到了要删除/插入节点及其前驱节点的信息，时间复杂度骤降到O(1)。
链表还有其他形式，例如双链表、循环链表、多重表等。
栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶端。栈可以理解为后进先出表。
栈可以通过单链表或数组实现。在单链表实现中，表的前端作为栈顶，所有操作均花费常数时间，但该方法的缺点在于对malloc和free的开销昂贵的；更流行的方法是采用数组实现，唯一缺点是需要提前声明一个数组的大小，且错误检测(数组越界)可能影响栈的执行效率。
队列是在末端插入，在开头删除的表。
在采用数组实现队列时，会维护位置变量Front和Rear。为防止队列溢出，只要位置变量达到数组的末端，它就又绕回开头。
优先队列是允许至少插入和删除最小者(找出、返回并删除优先队列的最小元素)的数据结构。二叉堆(堆，binary heap)可以在O(logN)内支持以上两种操作。
二叉堆具有结构性和堆序性，每次对堆的操作均需要到堆的所有性质全被满足时方可停止。
结构性：堆满足完全二叉树结构，一个堆数据结构由一个数组、一个代表最大值的整数和当前的堆大小组成。
堆序性：在堆的任意非根节点中，节点的关键字大于其父辈节点的关键字。换而言之，根节点最小。
在插入元素X时，在堆的下一个空闲位置创建一个空穴，若不满足堆结构，将空穴父节点的元素移入空穴，元素上移一层，迭代直至将X合理插入。这种方法称为上滤：新元素在堆中上滤直到找出正确的位置。
散列以常数平均时间进行插入、删除和查找，但不支持任何基于元素间排序的的操作。
散列表数据结构是一个含有关键字的固定大小的数组，通常情况下，关键字是一个带有相关值的字符串(类比Python中的字典结构：关键字key和相关值value)。将每个关键字使用散列函数(Hash function)映射到0至TableSize-1范围中的一个数字，再在数组对应位置存放关键字对应的值。理想情况下，函数在运算简单的同时应尽可能在单元间均匀地分配关键字。
当一个元素准备插入处已存在另一个元素时(二者散列值相同)，为消除冲突，常采用分离链接法和开放定址法。
开放定址法的核心思路是在冲突发生时不断选择另外的单元，直到找到空的单元。此方法要求表稍大，装填因子应小于0.5。常用方法有线性探测法，平方探测法和双散列法。