查找

平均查找长度（ASL）

$$ ASL = \frac {比较次数} {关键字个数} = 查找长度 \times 查找概率 $$

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

根据顺序表二分法查找比较次数的计算公式： $$ a<log_2n<b (a,b,n \in Z^+) $$ 当顺序表有n个关键字时：

查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

如果顺序表记录数 n=97 ，log₂64<log₂97<log₂128，即6<log₂97<7，最大比较次数为7次。

// arr:  要查找的数组
int binarySearch(int arr[], int left, int right, int data) {

    while (left <= right) {
        // 获取中间下标
        // 这样做比 （left + right）/ 2 更安全，可以避免int溢出
        int mid = left + (right - left) / 2;
        if (arr[mid] == data) {
            // 查找成功，返回下标
            return mid;
        }
        else if (arr[mid] > data) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    // 查找失败
    return -1;
}

分块查找

分块查找的平均查找长度不仅取决于数据集的总记录个数 n，还和每一块的记录个数 t 相关。

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树，二叉搜索树。它或者是一颗空树，或者是具有以下性质的二叉树。

• 若它的左子树不空，则左子树上所有的节点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有的节点的值均大于它的根结点的值；
• ⑶ 左、右子树本身又各是一棵二叉排序树。 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列

平衡二叉树（AVL树）

平衡二叉树（Height-Balanced Binary Search Tree），是一种二叉排序树，其中的每一个结点的左子树和右子树的高度差的绝对值小于等于1。

二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)

假设以$T_h$表示深度为h的平衡二叉树含有的最少结点数。显然有$T_0 = 0, T_1 = 1, T_2 = 2$，并且有： $$ T_h = T_{h-1} + T_{h-2} + 1 $$ 含有n个结点的平衡二叉树最大深度为$O(log_2n)$，因此平衡二叉树的平均查找长度为$O(log_2n)$

散列表

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

对于散列表长为m的散列函数，构造方法有：

散列函数

除留余数法

Hash(key) = key mod p (p<=m)

p一般取小于m的最大质数（素数）

直接定址法

$$ Hash(key) = a\times key + b \quad \left( a, b 为常数 \right) $$

其他还有数字分析法 平方取中法、折叠法、随机数法

装填因子

装填因子反映了一个表的装满程度。 $$ 装填因子 = \frac {填入表中的记录个数n} {散列表长度m} $$ 散列表的平均查找长度依赖于散列表的装填因子$\alpha$​，而不直接依赖于关键字个数n和表的长度m

查找成功=比较次数次数/数据个数。

查找成功ASL

等概率情况下，每个元素查找概率相等。则 $$ ASL_{成功} = \frac {查找每个元素的比较次数之和} {元素个数} $$

假设b c d均映射到Addr[2]，采用线性探测再散列法处理冲突。

地址Addr	0	1	2	3	4	5	6
关键字	a		b	c	d
查找成功比较次数	1		1	2	3

$$ ASL_{成功} = \frac {1 + 1 + 2 + 3} {4} = \frac 7 4 $$

查找失败ASL

如果散列函数为Hash(key) = key mod p，处理冲突采用线性探测再散列法。则查找失败时，经过散列函数计算后，只可能映射到散列表中 Addr[0...p-1] 的位置。每个位置都有可能不匹配，如果该位置不匹配，则会继续比较下一个位置，直到遇到关键字为空，停止比较。

如果散列函数为Hash(key) = key mod 4，则只需要讨论0-3范围内，假设某个元素x不在散列表内，则它可能映射到0-3内任意一个地址。

如果映射到0，则需要和Addr[0]和Addr[1]比较；

如果映射到1，则只需要和Addr[1]比较；

如果映射到2，则需要和Addr[2]，Addr[3]，Addr[4]，Addr[5]比较；

如果映射到3，则需要和Addr[3]，Addr[4]，Addr[5]比较；

地址Addr	0	1	2	3	4	5	6
关键字	a		b	c	d
查找失败比较次数	2	1	4	3

$$ ASL_{失败} = \frac {比较次数} {散列地址数p} = \frac {2 + 1 + 4 + 3} {4} = 2.5 $$

需要注意的是，有一种观点认为与真正的关键字比较才算比较次数，与空结点比较不算。上面的例子算上了空结点的比较次数，是另一种观点。

B树与B+树

多路查找树（muitl-way search tree）：每一个结点的孩子数可以大于两个，且结点处可以存储多个元素。

平衡二叉树（AVL）：一种二叉排序树，其中每一个结点的左子树和右子树的高度差的绝对值至不超过1。

**B树（B-Tree）是一种平衡多路查找树。**是一种自平衡树，叶子结点都在同一层次。所以任意一个结点的平衡因子都是0。

平衡多路查找树：平衡指的是叶子结点均在同一层，任意一个结点的平衡因子均是0。多路查找指的是结点内可以存储多个元素，有多个孩子。

查找方式

B+树有两个头指针：一个指向B+树的根节点，一个指向关键码最小的叶节点。因此，B+树可以进行两种查找运算：

• 顺序查找：循着叶节点自己建立的链表进行的查找
• 随机查找：从根节点开始，进行自顶向下，直至叶节点进行的查找

B树只支持随机查找，从根节点开始，找到匹配元素就停止查找；没有匹配元素就会查找到叶节点，说明查找失败。

对于一棵m阶B树和B+树而言

	B树	B+树
起源	由二叉排序树进化而来	由分块查找进化而来
关键字	任何节点的关键字都不会重复	叶节点包含了全部关键字，非叶节点的关键字一定会出现在叶节点中
关键字取值范围	非根节点： $\lceil m / 2 \rceil - 1 \leq k \leq m-1$ 根节点： $1 \leq k \leq m-1$	非根节点： $\lceil m / 2 \rceil \leq k \leq m$ 根节点： $2 \leq k \leq m$
包含信息	全部节点的关键字都包含信息	仅叶节点包含信息，非叶节点只起索引作用
查找方式	只支持随机查找	支持顺序查找和随机查找
查找失败	如果找到匹配关键字就停止，只有失败会到最后一层	查找成功或失败都只会发生在最后一层，在非叶节点中遇到匹配关键字仍会继续查找，直到在叶节点中再次匹配。
关键字与子树对应关系	n个关键字含有n+1棵子树	n个关键字含有n棵子树

三个核心问题

对于一棵含有n个关键字的m阶B树，设高度为h（不包含叶节点）

有多少个叶节点

对于任何一棵B树，n个关键字相当于将一个线段划分成了n+1和区间；查找的时候只有n个关键字能匹配。不匹配的就是区间内的关键字，也就是叶子节点。所以一共有n+1个叶子节点。

最小高度是多少

最胖的树最矮，让每个节点的关键字达到最大m-1个。

m阶B树，每个节点最多有$k = m$个子树，$k-1$个关键字。则节点数、关键字数、与树的层数（高度）关系是

层数	结点数	关键字
第一层	$k^0 = 1$	$k^0(k-1)$
第二层	$k^1$	$k^1(k-1)$
第三层	$k^2$	$k^2(k-1)$
···	···	···
第h层	$k^{h-1}$	$k^{h-1}(k-1)$

等比数列求和公式为，得到总的关键字个数为 $$ S = \frac {a_1(q^n - 1)} {q-1} $$

$$ \begin{aligned} &(k^0 + k^1 + ···+ k^{h-1})(k-1) \ &= \frac {k^0(k^h - 1)} {k-1} \times(k-1) \ &= k^h - 1 \end{aligned} $$

高度为h的m阶B树，关键字个数最多为$k^h - 1$个，从而 $$ \begin{aligned} n &\leq k^h -1 = m^h - 1\ h &\geq \lceil \log_m(n+1) \rceil \end{aligned} $$

理解：

经过分析，可以发现如果树的高度是h，则关键字最多为$k^h - 1$，不能再多了，否则就超过h了。现在有n个关键字，且高度为h。则稍加推理就能得到n可定是不大于$k^h - 1$

最大高度是多少

最瘦的树最高，让每个节点的关键字达到最小$\lceil m/2 \rceil-1$个。

m阶B树，每个非根节点节点至少有$k = \lceil m / 2 \rceil $个子树，$k-1$个关键字。根节点特殊，至少有2棵子树，1个关键字。则节点数、关键字数、与树的层数（高度）关系是

层数	结点数	关键字
第一层	$1$	$1$
第二层	$2k^0$	$2k^0(k-1)$
第三层	$2k^1$	$2k^1(k-1)$
第四层	$2k^2$	$2k^2(k-1)$
···	···	···
第h层	$2k^{h-2}$	$2k^{h-2}(k-1)$

得关键字总的个数为 $$ 1+2(k-1)(k^0 + k^1 + k^2 +··· + k^{h-2}) = 2k^{h-1} - 1 $$ 高度为h的m阶B树，关键字个数最少为：$2k^{h-1} - 1$个，从而 $$ \begin{aligned} n &\geq 2k^{h-1} - 1 \ h &\leq \log_k (\frac {n+1} 2) + 1 &， k = \lceil m/2 \rceil \end{aligned} $$

理解：

经过分析，可以发现要想树的高度是h则至少需要$2k^{h-1} - 1$关键字，不能再少了，否则高度就达不到h。现在有n个关键字，且树的高度为h。则 稍加推理就能得到n肯定是不小于$2k^{h-1} - 1$

拓展：

第$h+1$层是叶节点，最少为$2k^{h-1}$个。又由问题1可得，叶节点有$n+1$个。则二者联立可得： $$ \begin{aligned} n+1 &\geq 2k^{h-1} \ h &\leq \log_k (\frac {n+1} 2) + 1 &， k = \lceil m/2 \rceil \end{aligned} $$