数据结构与算法基础：查找

顺序查找和折半查找错题要点

折半查找的判定树是平衡二叉树，左右子树高度差绝对值不超过 1。
折半查找的取整规则：要么统一向下取整，要么统一向上取整，且每次比较的元素只参与一次划分。
- 例：[a, b, c, d, e, f] 中查找 a，向上取整先比较 d，下一轮范围是 [a ~ c]，d 不再参与比较。
二叉排序树的树高与输入序列的顺序有关，不同序列可能生成不同高度的树。
折半查找判定树中，左右子树的节点个数相差不超过 1（近似相等）。
分块查找的平均查找长度公式（假设每块大小相等）：
$$ ASL \approx \frac{s^2 + 2s + n}{2s} $$
其中：
- ( s )：每块元素个数
- ( n )：总元素个数
更常见的形式：
$$ ASL = \frac{s+1}{2} + \frac{n/s + 1}{2} $$
第一项是块内顺序查找的 ASL，第二项是块索引查找的 ASL。
ASL 计算公式（一般形式）：

$$ ASL = \sum_{i=1}^{n} P_i \cdot C_i $$

其中 (P_i ) 是查找第 ( i ) 个元素的概率，( C_{i} ) 是比较次数。等概率时可简化为：

$$ ASL = \frac{1}{n} \sum_{i=1}^{n} C_i $$

树形查找错题要点

二叉树排序树BST不需要交换平衡二叉树需要交换

n个不同节点的二叉查找树的形态有卡特兰树(Catalan(n))个推荐公式为

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
  n = 0 时            Catalan(0)=1
  n = 1 时 1 * 1 = 1  Catalan(1)=1
  n = 2 时 1 * 1 = 1 
          1 * 1 = 1  Catalan(2) = 1 + 1 = 2
  n = 3 时 1 * 2 = 2
          1 * 1 = 1 ↑
      ↓   2 * 1 = 2  Catalan(3) = 2 + 2 + 1 = 5
  n = 4 时 1 * 5 = 5
          1 * 2 = 2
        ↓  2 * 1 = 2 ↑
          5 * 1 = 5 Catalan(4) = 5 + 2 + 2 + 5 = 14
  n = 5 时 1 * 14 = 14
          1 * 5 = 5  
        ↓  2 * 2 = 4  ↑
          5 * 1 = 5   
          14 * 1 = 14 Catalan(5) = 14 + 5 + 4 + 5 + 14 = 42 

平衡二叉树最少节点数递推公式 $ N_h $ 为构造平衡二叉树最少节点数有
$$ N_0 = 0, N_1 = 1, N_2 = 2, N_h = N_{h-1} + N_{h-2} + 1 $$ 即所有非叶子节点的平衡因子为1
红黑树的相关性质
红黑树首先是一个二叉排序树
- ①每个节点是红色或者黑色
- ②根节点为黑色
- ③叶节点(虚拟节点和NULL节点)都是黑色的
- ④不存在相邻的红色节点即红节点的父节点和子节点都是黑色的,黑节点不做要求
- ⑤对任意节点,从该节点到任意叶子节点经过的黑节点个数都相等,只能向下,不能向上走根据以上可推出
  红黑树从根到叶子最长路径不大于最短的2倍因为任意节点到叶子节点的黑点个数相等,红的穿插到黑节点,最多隔一插一个
二叉排序树判定要旋转的子树是寻找最近的父节点平衡因子的绝对值大于1不包括1的节点, 平衡因子为某个节点的左子树高减去右子树高
B树的树高最值公式
$$ \log_{m}{n+1} \le h\le \log_{\frac{2}{m}}{\frac{n+1}{2} + 1} $$ 其中 $ \frac{2}{m} $的值向上取整,左右两边都是向上取整,奇数个加一后再向上取整
这里的m为m阶B树,n为元素的个数,h为树高(不含最后的空节点)
各种求关键字的题目均可转换成关于上面式子求高度
B树和B+树的几个区别
- B树的叶子节点的值不包括其他节点,即某个值只会在这个B树里出现一次
- B树只能做到随机存储,不能做到顺序存储,而B+树可以做到随机存储和顺序存储
B树所有非叶子节点最多有$ m-1 $个关键字,即$ m $棵子树最少有$ \frac{m}{2} -1$个关键字,$\frac{m}{2}$ 棵子树