Chapter 7. 查找

公式与性质

• 查找方式	ASL _ {成功}	ASL _{失败}
  一般线性表的顺序查找	\frac {n+1}{2}	n+1
  有序线性表的顺序查找	\frac {n+1}{2}	\frac n 2 + \frac {n}{n+1}

  查找方式	ASL
  折半查找	\approx \log _2 (n+1) -1
  n 个块每块 s 个记录的分块查找	\frac {s^2 + 2s + n} {2s} ，当 s = \sqrt n 时有最小值 \sqrt n+1

• 折半查找的 mid 指针每次都指向表的中间位置 \lfloor (low + high) / 2 \rfloor 。

• 平衡二叉树任意结点的左右子树高度差的绝对值 \le 1 。

• 对二叉排序树进行中序遍历 ，可以得到一个递增的有序序列。

• 平衡二叉树的调整（每次调整的对象都是最小不平衡子树）

  旋转方式	旋转条件	具体过程
  LL	L孩子的L子树失衡	L孩子向右上右旋，L孩子的R子树转移到R孩子的L子树
  RR	R孩子的R子树失衡	R孩子向左上左旋，R孩子的L子树转移到L孩子的R子树
  LR	L孩子的R子树失衡	先左旋再右旋
  RL	R孩子的L子树失衡	先右旋再左旋

• 以 n_h 表示深度为 h 的平衡二叉树中含有的最少结点数，则有 n_0 =0, n_1 =1, n_2 =2, n_h = n_{h-2} + n_{h-1} + 1 。

• 红黑树的性质

  1. 每个结点非黑即红。
  2. 根结点是黑色的。
  3. 叶结点（虚构的外部结点、NULL结点）都是黑色的。
  4. 不存在两个相邻的红结点。
  5. 任意结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。

• 红黑树的结论

  1. 从根到叶结点的最长路径不大于最短路径的 2 倍。
  2. 有 n 个内部结点的红黑树的高度 h \le 2 \log _2 (n+1) 。
  3. 新插入红黑树的结点初始着为红色。

• B树的性质

  一颗 m 阶 B 树或为空树，或为满足如下特性的 m 叉树：

  1. 树中每个结点至多有 m 颗子树，即至多有 m-1 个关键字。
  2. 若根结点不是叶结点，则至少有 2 颗子树，即至少有 1 个关键字。
  3. 除根结点外的所有非叶结点至少有 \lceil \frac m 2 \rceil 颗子树，即至少有 \lceil \frac m 2 \rceil - 1 个关键字。

  即非根非叶结点的关键字的个数 n 的取值范围为 \lceil \frac m 2 \rceil -1 \le n \le m-1 。

  4. 所有叶结点都出现在同一层次上，为外部结点，不携带信息。（即查找失败时的结点）。
  5. 设高度为 h ，关键字个数为 n，则 m,n,h 应满足 \log _m (n+1) \le h \le \log _{\lceil \frac m 2 \rceil} \frac {n+1}{2} +1 。
  6. 不支持顺序查找。

• B+树：叶结点包含信息（全部关键字及指向相应记录的指针），按关键字大小顺序排列，并且相邻叶结点按大小顺序相互连接。 所有分支结点仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

• 散列表装填因子 \alpha=\frac {表中记录数n} {散列表长度m} 。

概念

• 分块查找既有动态结构又适于快速查找。

• 构造二叉排序树的目的不是排序，而是提高查找、插入和删除关键字的速度。

• 设散列表中有 m 个存储单元，散列函数 H(key)=key \% p ，则 p 最好选择小于等于 m 的最大素数

• 查找哈希 Hash 表，不会发生冲突的哈希函数是直接地址法

  理想情况下，地址无限，永远不会发生冲突。实际上地址不可能无限。

• 散列表的平均查找长度与冲突处理方法和填充因子有关。

考点

• 折半查找无论查找成功失败，查找次数最多时为树高 \lceil \log _2 (n+1) \rceil 。

• 折半查找判定树为平衡二叉树（任意结点左子树要么与右子树高相等，要么矮一层，要么高一层，但是矮一层和高一层的情况不能同时出现）。

• 折半查找的（最坏）搜索效率与平均搜索效率相等，都是 O(\log _2 n) 。

• 对有 65025 个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行 2 \log _2 (\sqrt {65025} + 1)=16 次关键字比较。

  索引块大小 =\sqrt {65025} = 255 ，总共 \frac {65025}{255} = 255 个索引块，对索引块和每个索引块内进行折半查找，最多需要 2 \log _2 (255+1)=16次。

• 能表示 4 个不同元素的二叉查找（搜索）树可以有 C ^ n _ {2n} \frac {1}{n+1} = C ^ 4 _ 8 \frac 1 5 = 14 种不同的形态。

  遇事不决，卡特兰数（bushi

• 在二叉排序树中插入一个结点的时间复杂度为 O(n) 。

  二叉排序树在最坏情况下退化为链表。

• 一颗二叉树的左右子树都是平衡二叉树，且高度差绝对值不超过 1 ，那么它是平衡二叉树。

• 在任意一颗非空平衡二叉树 T_1 中，删除某结点 v 后形成平衡二叉树 T_2 ， 再将 v 插入 T_2 形成平衡二叉树 T_3 。若 v 不是 T_1 的叶结点，则 T_1 与 T_3 不一定相同。

    2         3        3        2
   / \       /        /        / \
  1   3     1        1        1   3
                      \
                       2
     --删2-->  --插2-->  --平衡-->
  

  不相同的情况容易构想。以上是一个相同的例子。

• 平衡二叉树最后插入的元素不一定是叶结点。

  可能导致平衡调整。

• 具有 n 个关键字的 m 阶 B 树应有 n+1 个叶结点。

  叶结点即失败结点，n 个关键字即有 n+1 种失败可能。

• 长度为 11 且初始为空的散列表，散列函数是 H(key)=key\%7 ，采用线性探测，注意不冲突的情况下只能模到 0-6；失败情况下的平均查找长度应除以 7。