重拾数据结构

最近由于某些原因在复习专业课，包括数据结构、计算机组成原理、操作系统、计算机网络等，然后我发现我大一时学的数据结构比我上学期学的操作系统和计算机网络记得更清晰，所以，我这两年到底在干嘛……而且我再一次认识到我学校有多次，考研要考的当时基本都没有深入讲，可苦了考研狗……
言归正传，开始捡数据结构，写在这里方便以后查阅。
1. 平衡二叉树
平衡二叉树也叫做 AVL 树，它要么是一棵空树，要么为一棵满足以下条件的树：各结点的左子树与右子树的深度之差的绝对值不超过 1，这个差叫做平衡因子（BF），所以一棵平衡二叉树的 BF 取值可以为 0， 1，-1。
2. 完全二叉树与满二叉树
满二叉树： 2^k - 1 个结点，叶子结点只可能在其最后一层出现。
完全二叉树：我的理解就是将一棵满二叉树，从后往前依次删除 1 个或多个结点得到的树就是完全二叉树，所以其叶子结点只可能出现在最后两层。
3. m 阶 b 树特点
 1. 每个结点最多有 m 个结点。
 2.若根结点不是叶子结点，则其至少有 2 棵子树。
 3.除根结点之外的非叶子结点至少有 ceil（m / 2）【即向上取整】棵子树。
 4.各结点内关键字均按升序或降序排列。
 5.所有叶子结点都在同一层上。
B+树特点：叶子结点之间通过指针连接。
4. 最小堆（小根堆）与最大堆（大根堆）
最小堆：根结点内的关键字最小，且每个结点都不大于其子结点。
最大堆：根结点的关键字最大，且每个结点都不小于其子结点。
最小堆的构造：先根据所给序列按元素先后顺序画出完全二叉树，然后按照从左到右、从下往上的顺序依次遍历结点，若发现该结点比起父节点小，则调换，待所有调换完成之后，再进行递归调整。
5. 排序
 1. 冒泡排序：每趟排序只能决定一个元素的位置。
 2. 简单选择排序：从待排序的序列中找出关键字最小的元素；如果该元素不是第一个元素则对换；对剩下的序列重复进行前两个步骤，直至排序结束。
特点：每趟排序能确定一个元素的位置。
 3. 插入排序：在部分有序的序列中从后往前插入新的元素。
特点：每趟排序之后能保证若干元素有序。
 4. 二路归并排序：采用 “ 分治 ”思想，将一个大的问题分解成若干个解法相同的小问题，待小问题全部解决之后，再将各个小问题的解归并起来从而得到大问题的解。
特点：每趟排序之后会得到若干个有序子序列。