Elian's blog page

B 树的定位B 树又称多路平衡查找树。它可以理解为把 二叉排序树 推广为多叉查找树，并额外要求结点尽量“满”、整棵树保持“绝对平衡”。 这里的“绝对平衡”是指：所有叶结点，也就是查找失败的外部结点，都在同一层。 B 树常用于外存索引。一个结点可以存放多个关键字，查找时一次读入一个结点，可以减少访问层数。 m 阶 B 树定义B 树的阶是一个结点允许拥有的最大孩子数，通常记为 $m$。 一棵 $m$ 阶 B 树，或为空树，或满足： 每个结点至多有 $m$ 棵子树，即至多有 $m-1$ 个关键字。 若根结点不是终端结点，则根至少有 2 棵子树，即至少有 1 个关键字。 除根结点外，所有非叶结点至少有 $\lceil m/2\rceil$ 棵子树，即至少有 $\lceil m/2\rceil-1$ 个关键字。 非叶结点内部关键字有序：$K_1<K_2<\cdots<K_n$。 若结点有 $n$ 个关键字，则有 $n+1$...

定义红黑树是一种自平衡的二叉排序树。它比 AVL 树 的平衡条件更宽松，但仍能保证树高为 $O(\log_2 n)$。 红黑树必须同时满足： 它是一棵二叉排序树。 每个结点要么是红色，要么是黑色。 根结点是黑色。 叶结点是黑色。这里的叶结点通常指外部空结点，也就是 NULL、失败结点或 NIL 结点。 不存在两个相邻的红结点，即红结点的父结点和孩子结点都必须是黑色。 对任一结点，从该结点到任一叶结点的简单路径上，黑结点数相同。 可以把判断口诀记为： Important 左根右，根叶黑，不红红，黑路同。 判断一棵树是不是红黑树时，应按以下顺序查： 先看是否满足 BST 的左小右大关系。 再看根是否为黑，外部空叶是否按黑结点处理。 检查是否存在红父红子。 对每个结点检查到各 NIL 叶结点的黑结点数是否相同。 黑高结点 x 的黑高 bh(x) 定义为： 从 x 出发，不含 x 本身，到达任一 NIL 叶结点的路径上黑结点总数。 因为红黑树要求“黑路同”，所以对同一个结点 x，无论走向哪个 NIL...

定义与性质AVL 树是一种自平衡的二叉排序树。它不仅满足 BST 的左小右大性质，还要求： Important 对树上任一结点，其左子树和右子树的高度差绝对值不超过 1。 结点的平衡因子定义为： $$BF = h_{left} - h_{right}$$ 因此 AVL 树中任一结点的平衡因子只能是 -1、0、1。只要有一个结点的平衡因子绝对值大于 1，整棵树就不是 AVL 树。 AVL 树首先是 BST，所以中序遍历仍得到递增序列；查找过程也与 BST 完全一致。区别在于：插入、删除后如果破坏平衡，需要通过旋转恢复平衡。 若树高为 $h$，查找一个关键字最多比较 $h$ 次。因此 AVL 树的高度上界直接决定查找性能。 高度为 $h$ 的 AVL 树至少有多少个结点？ 要让整棵 AVL 树高度达到 $h$，根的某一棵子树高度至少要达到 $h-1$。 为了让结点总数尽量少，另一棵子树应尽可能矮。 但 AVL 要求左右子树高度差不能超过 1，所以另一棵子树最低只能是 $h-2$。 两棵子树本身也必须是 AVL 树，而且也要各自取最少结点。 令 $N(h)$...

定义二叉排序树又称二叉查找树，英文是 Binary Search Tree，常写作 BST。它可以是空二叉树；若非空，则满足： 左子树上所有结点的关键字都小于根结点关键字。 右子树上所有结点的关键字都大于根结点关键字。 左子树和右子树也分别是二叉排序树。 基础定义也可参考 二叉排序树概念。本篇重点放在查找、插入、删除。 BST 的直接推论：==中序遍历 BST 可以得到递增有序序列==。因为中序遍历顺序是“左子树、根、右子树”，而 BST 正好满足“左 < 根 < 右”。 查找BST 查找每次只需要沿一条路径向下： 若 key == root->key，查找成功。 若 key < root->key，去左子树查找。 若 key > root->key，去右子树查找。 若走到空指针，查找失败。 ↻ + − 12345678910111213141516171819202122232425typedef struct BSTNode { int key; ...

最佳归并树解决什么问题在外部排序中，各初始归并段长度可能不同。若归并顺序安排不好，较长的归并段可能被反复读写很多次，导致磁盘 I/O 增加。 最佳归并树用于安排归并顺序，使总读写代价最小。 基本思想和哈夫曼树相同： 把每个初始归并段看作一个叶结点； 归并段长度作为结点权值； 每一次归并相当于生成一个父结点； 目标是让带权路径长度最小。 ↻ + − 二路最佳归并树二路归并时，每次选两个权值最小的归并段先归并。 例如初始归并段长度为： $$2,\ 3,\ 6,\ 9$$ 构造过程： 步骤 合并 新权值 1 $2+3$ $5$ 2 $5+6$ $11$ 3 $9+11$ $20$ 所有内部结点权值之和为： $$5+11+20=36$$ 这个值就是归并过程中每个记录块被反复参与归并的总次数，也等于最佳归并树的带权路径长度。 若权值表示磁盘块数，则： $$\text{读磁盘次数}=36,\qquad \text{写磁盘次数}=36$$ 所以总磁盘 I/O 次数为： $$72$$ 多路最佳归并树$k$...

置换-选择排序的作用在外部排序中，初始归并段越少，后续归并趟数越少。 若用普通方法生成初始归并段，内存工作区能容纳 $L$ 个记录，则每个初始归并段最多只有 $L$ 个记录。若文件共有 $N$ 个记录，初始归并段数量约为： $$r=\lceil N/L\rceil$$ 置换-选择排序的目标是：在内存工作区大小不变的情况下，生成更长的初始归并段，从而减少 $r$。 基本思想置换-选择排序维护一个内存工作区 WA，每次从 WA 中选择当前归并段能接上的最小记录输出。 核心变量是 MINIMAX： MINIMAX 表示当前归并段最后输出的关键字； 能接在当前归并段后面的记录必须满足关键字 $\ge \text{MINIMAX}$； 若新读入记录的关键字 $< \text{MINIMAX}$，它不能放入当前归并段，只能留到下一个归并段。 ↻ + − 操作过程 从初始待排序文件 FI 中读入 $L$ 个记录，填满内存工作区 WA。 从 WA 中选出关键字最小的记录，输出到初始归并段输出文件 FO。 把刚输出的关键字记为 MINIMAX。 从 FI...

多路归并在外部归并排序中，若每次只归并两个归并段，归并趟数可能较多。把二路归并推广为 $k$ 路归并，就可以一次合并最多 $k$ 个归并段。 若有 $r$ 个初始归并段，采用 $k$ 路归并，归并趟数为： $$S=\lceil \log_k r\rceil$$ $k$ 越大，归并趟数通常越少，磁盘 I/O 次数也随之减少。 多路归并的代价多路归并不是只有好处。 影响 原因 输入缓冲区增多 $k$ 路归并至少需要 $k$ 个输入缓冲区和一个输出缓冲区 选最小记录的比较次数增加 若朴素扫描 $k$ 个归并段首记录，每输出一个记录最多比较 $k-1$ 次 所以多路归并的矛盾是： $$k\uparrow\Rightarrow S\downarrow,\quad \text{磁盘 I/O 减少}$$ 但同时： $$k\uparrow\Rightarrow \text{选最小记录的内部比较代价增加}$$ 多路平衡归并$k$ 路平衡归并满足两个条件： 每次最多把 $k$ 个归并段合并为一个新归并段。 若某一趟有 $m$...

外部排序的基本问题外部排序用于处理无法一次全部装入内存的大文件。和内部排序不同，外部排序的主要瓶颈不是 CPU 比较，而是磁盘...

基本思想计数排序是一种非比较排序。它的做法是： 统计每个关键字出现了多少次。 根据计数直接恢复出有序序列。 Example 12345678A = 2, 5, 3, 0, 2, 3, 1C[0] = 1C[1] = 1C[2] = 2C[3] = 2C[4] = 0C[5] = 1 从小到大输出下标i， 每个下标输出C[i]次，即可得到排序后的序列： 10, 1, 2, 2, 3, 3, 5 若记录除了关键字还有其他信息，并且要保持稳定性，就需要用前缀和定位。 稳定计数排序设关键字范围为 $0..k$。稳定计数排序通常使用三个数组： 数组 含义 a 原记录数组 count 计数数组，长度为 $k+1$ out 输出数组 ↻ + − 稳定版本的核心是把 count[x] 从“等于 x 的个数”转换为“$\le x$ 的个数”。 前缀和之后： $$count[x] = |{a_i \mid key(a_i) \le x}|$$ 因此，关键字为 $x$ 的记录最后一个位置是： $$count[x]-1$$ 放入一个关键字为...

Radix Sort基本思想基数排序是一种分配类排序。它不靠两个完整关键字之间的比较来排序，而是把关键字拆成若干个“位”或“组”，再按这些位反复进行分配和收集。 若长度为 $n$ 的线性表中，每个结点 $a_j$ 的关键字可写成一个 $d$ 元组： $$(k_j^{d-1}, k_j^{d-2}, \dots, k_j^1, k_j^0)$$ 其中： $k_j^{d-1}$ 是最高位关键字，也叫最主位关键字。 $k_j^0$ 是最低位关键字，也叫最次位关键字。 每一位关键字的取值范围为 $0 \le k_j^i \le r-1$。 $r$ 称为基数。十进制数按每一位排序时，$r=10$。 基数排序不是基于比较的排序算法 它的主要操作是按当前关键字位把元素放入对应队列，再按队列顺序收集。 多关键字排序一个关键字能拆成多组时，排序本质上就是多关键字排序。 例如三位十进制数 985...