查找算法¶

二叉树基础

最大堆和最小堆

二分查找

二叉排序树

平衡二叉树

多路查找树2-3树

红黑树

B/B+树

哈希表

跳表

位图

数组和链表¶

数组和链表的区别

赫夫曼编码¶

赫夫曼树

赫夫曼编码

二叉树基础¶

二叉树定义
- n个结点的有限集合，该集合为空集，或者一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
满二叉树
- 一棵二叉树中所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
完全二叉树
- 一棵有n个结点的二叉树按层序编号，编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同
二叉树的性质
- 非空二叉树第 i 层最多 2^(i-1) 个结点（i >= 1）
- 深度为 k 的二叉树最多 2^k - 1 个结点（k >= 1）
- 度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1
- 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1
- 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n）的结点
  - 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
  - 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
  - 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

最大堆和最小堆¶

堆是完全二叉树，根据结点和左右孩子的大小关系，分为最大堆和最小堆

最大堆
- 每个结点的值都大于或等于其左右孩子结点的值
最小堆
- 每个结点的值都小于或等于其左右孩子结点的值

二分查找¶

二分查找适用于有序数组

查找时间复杂度O(logn)

二叉排序树¶

查找时间复杂度O(logn)，最坏情况变成右斜树O(n)

二叉排序树，又称二叉搜索树，若二叉排序树不为空，则具有下列性质

若左子树不为空，则左子树上所有结点的值小于根节点的值

若右子树不为空，则右子树上所有结点的值大于根节点的值

平衡二叉树¶

查找时间复杂度O(logn)，插入和删除时间复杂度O(logn)

平衡二叉树是**二叉排序树**，每一个结点左右子树高度之差的绝对值不超过1

多路查找树2 3树 ¶

多路查找树，每一个结点的孩子数可以多于两个，每一个节点处可以存储多个元素

2-3树¶

每一个结点都具有两个孩子(2结点)或三个孩子(3结点) 一个2结点包含一个元素和两个孩子一个3结点包含一小一大两个元素和三个孩子

红黑树 ¶

查找时间复杂度O(logn)，插入和删除时间复杂度O(logn)
红黑树的五个性质（性质没法解释），红黑树是这样的树！！！
- 每个结点非红即黑
- 根结点为黑色
- 每个叶结点（叶结点即实际叶子结点的NULL指针或NULL结点）都是黑的;
- 若结点为红色，其子节点一定是黑色（没有连续的红结点）
- 对于每个结点，从该结点到其后代叶结点的简单路径上，均包含相同数目的黑色结点（叶子结点要补充两个NULL结点）
- 有了五条性质，才有一个结论：通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。
平衡树和红黑树的区别
- AVL树是高度平衡的，频繁的插入和删除，会引起频繁的调整以重新平衡，导致效率下降
- 红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转，调整时新插入的都是红色。
为什么红黑树的插入、删除和查找如此高效？
- 插入、删除和查找操作与树的高度成正比，因此如果平衡二叉树不会频繁的调整以重新平衡，那它肯定是最快的，但它需要频繁调整以保证平衡
- 红黑树算是一种折中，保证最长路径不超过最短路径的二倍，这种情况下插入最多两次旋转，删除最多三次旋转，因此比平衡二叉树高效。
红黑树为什么要保证每条路径上黑色结点数目一致？
- 为了保证红黑树保证最长路径不超过最短路径的二倍
- 假设一个红黑树T，其到叶节点的最短路径肯定全部是黑色节点（共B个），最长路径肯定有相同个黑色节点（性质5：黑色节点的数量是相等），另外会多几个红色节点。性质4（红色节点必须有两个黑色儿子节点）能保证不会再现两个连续的红色节点。所以最长的路径长度应该是2B个节点，其中B个红色，B个黑色。

B/B+树 ¶

B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，结点最大的孩子数目称为B树的阶。

B/B+树的区别¶

以（key，value）二元组来存储信息

B树¶

B树中的每个结点中既包含key，也包含value值，每个结点占用一个盘块的磁盘空间，一个结点上有两个升序排序的关键字和三个指向子树根结点的指针，指针存储的是子结点所在磁盘块的地址。
缺点：每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

B+树¶

所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度
B+树的头指针有两个，一个指向根节点，另一个指向关键字最小的元素，因此B+树有两种遍历的方式
- 从根节点开始随机查询
- 从最小关键词顺序查询
优点
- 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。
- B+树的叶子结点都是相连的，因此对整棵树的便利只需要一次线性遍历叶子结点即可，方便随机查找和范围查找

区别¶

非叶子节点只存储键值信息，该值是其子树中的最大或最小值

所有叶子节点之间都有一个链指针。

数据记录都存放在叶子节点中，叶子结点按照关键字的大小自小而大顺序连接

n棵子树的结点中包含n个关键字

非叶子结点中的元素会在子树根结点中再次列出

B树和红黑树应用场景 ¶

B树
- B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度.
红黑树
- IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.

实例¶

假定一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在100万个数据中查找目标值，只需要读取两次硬盘。

哈希表 ¶

哈希表是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其存储位置，在该位置上存储着对应的数据

哈希表的实现¶

主要包括构造哈希和处理哈希冲突
- **使用哈希函数将被查找的键转换为数组的索引。**方法有**直接地址法、平方取中法、除留余数法**等。理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。
- 处理哈希碰撞冲突。**有很多处理哈希碰撞冲突的方法，如**拉链法(哈希桶)、线性探测法(开放定址法)、再哈希法、公共溢出区法。

构造哈希¶

直接地址法
- 直接用key或key的线性函数值作为索引
- 如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。
平方取中法
- 将key平方后取中间的几位数作为索引，可以是3位或4位
除留余数法
- 最常用的构造哈希函数的方法，直接对key取模，也可以平方后取模。
- 获取**正整数哈希值**最常用的方法是使用除留余数法，即对于大小为素数M的数组，对于任意正整数k，计算k除以M的余数。M一般取素数。

字符串哈希值¶

将字符串作为键的时候，可以将它作为一个大的整数，将组成字符串的每一个字符取ASCII值然后进行哈希，采用Horner计算字符串哈希值。
如果对每个字符去哈希值可能会比较耗时，所以可以通过间隔取N个字符来获取哈西值来节省时间

int hash = 0;
char *str = "abcdef";
for(int i = 0;i < strlen(str);i++){
    hash = 31*hash + (int)str[i];
}
cout<<hash<<endl;

处理哈希冲突¶

拉链法（哈希桶法）¶

基本思想
- 将大小为M的数组的每一个元素指向一个链表，链表中的每一个结点都存储散列值为该索引的键值对。注意选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率
拉链法查找
- 根据散列值找到索引对应的链表，
- 沿着链表顺序找到相应的键

线性探测法（开放定址法）¶

基本思想：f(key) = (f(key) + d) MOD M

线性探测
- 当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1
二次探测
- 索引值位移量不为1，为1，-1，2，-2…的平方
随机探测
- 索引值位移量采用随机函数计算得到。随机种子产生伪随机数，每次得到的随机序列相同

再哈希法¶

使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置，但每次冲突都要重新散列，计算时间增加，另外需要准备多个哈希函数

公共溢出区法¶

建立一个公共溢出区域，把hash冲突的元素都放在该溢出区里。查找时，如果发现hash表中对应桶里存在其他元素，还需要在公共溢出区里再次进行查找。

为什么哈希桶的长度和除留余数法的M为质数？¶

设有一个哈希函数：H( c ) = c % N; 当N取一个合数时，最简单的例子是取2^{n，比如说取2}3=8,这时候 H(11100(二进制)) = H(28) = 4 H(10100(二进制)) = H(20) = 4

c的二进制**第4位（从右向左数）就“失效”**了，也就是说，无论第c的4位取什么值，都会导致H( c )的值一样．这时候c的第四位就根本不参与H( c )的运算，这样H( c )就无法完整地反映c的特性，增大了导致冲突的几率．
取其他合数时，都会不同程度的导致c的某些位”失效”，从而在一些常见应用中导致冲突．
取质数，基本可以保证c的每一位都参与H( c )的运算，从而在常见应用中减小冲突几率．

跳表 ¶

查找时间复杂度O(logn)，插入、删除时间复杂度O(logn)
用于有序链表的查找，类似二分查找操作的链表

基本思想¶

把链表中的一些节点提取出来作为索引，为了提高效率可以逐级提取作为索引

原始链表
- 14 → 23 → 34 → 43 → 50 → 59 → 66 → 72
- 原始链表查找复杂度O(n)
跳表
- 性质
  - 由很多层结构组成
  - 每一层都是一个有序的链表
  - 最底层(Level 1)的链表包含所有元素
  - 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
  - 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
- 原始链表转换成跳表
14 → 50

↓ ↓

14 → 34 → 50 → 66

↓ ↓ ↓ ↓

14 → 23 → 34 → 43 → 50 → 59 → 66 → 72

第二级索引 - 第一级索引 - 原始链表

跳表的查找、插入和删除 ¶

查找
- 查找时间复杂度为O(logn)
- 如果链表中总共有 n 个结点，那么第一级索引就有 n/2 个结点，第二级索引就有 n/4 个结点，以此类推，那么第 k 级索引就有 n/(2^k) 个结点。如果最高级索引有 2 个结点，那总的索引级数 k=log2n−1，如果我们算上原始链表的话，那也就是总共有 log2n 级。
插入
- 先查找再插入，插入时间复杂度O(logn)
- 当我们不停地往跳表中插入数据的时候，如果我们不更新索引，就有可能出现某两个结点之间数据非常多的情况。极端情况下，跳表还会退化为单链表。
- 我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表结点变多了，索引值就相应地增加一些
- 可以选择同时也将这个数据插入到部分索引层中。而插入到哪些索引层中，则由一个随机函数生成一个随机数字来决定

跳表和红黑树的对比¶

插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度和跳表是一样
跳表的优点
- 代码相对简单
- 按照区间查找数据这个操作，红黑树的效率没有跳表高。跳表可以在 O(logn) 时间复杂度定位区间的起点，然后在原始链表中顺序向后查询就可以了，这样非常高效。
- 删除一段区间的数据，相对于红黑树容易

位图 ¶

位图一、位图二

基本思想¶

bitmap(位图)，每一位存放某种状态，通常用来判断某个数据是否存在。32位机器上，整型int在内存中占32bit(4 byte = 4 * 8 bit)，可以用对应的32bit对应十进制的0-31个数。

用途¶

排序，去重，查找

map映射表¶

基本思想 假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为**int a[1 + N/32]**，其中a[0]在内存中占32为可以对应十进制数0-31，依次类推： bitmap表为： a[0]--------->0-31 a[1]--------->32-63 a[2]--------->64-95 a[3]--------->96-127 ..........

位映射步骤

求十进制0-N对应在数组a中的下标：
- 十进制0-31，对应在a[0]中，先由十进制数n转换为与32的模(商)可转化为对应在数组a中的下标。比如n=24,那么 n/32=0，则24对应在数组a中的下标为0。又比如n=60,那么n/32=1，则60对应在数组a中的下标为1，同理可以计算0-N在数组a中的下标。
求0-N对应每个下标0-31中的数：
- 十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32的余数求得对应0-31中的数。
利用移位0-31使得对应位为1.

应用¶

2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
- “内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map
- 使用两个位图
  - 第一个Bitmap存储的是整数是否出现
  - 如果再次出现，则在第二个Bitmap中设置
- 使用一个位图
  - 遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。
  - 最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

扩展-布隆过滤器¶

基本思想

当一个元素被加入集合中时,通过k个散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1.
Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。
在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。

缺点

有一定的误判率，当判断某个元素在集合中，有可能是其他的元素的位；若集合中不存在该元素，则一定不存在

数组和链表的区别¶

存储
- 数组时连续的内存空间，链表不需要连续
长度
- 数组的长度需要预先确定，若超出数组则会溢出
- 链表的长度是动态扩展的
随机访问
- 数组可以随机访问，时间复杂度为O(1)
- 链表不支持随机访问，平均需要O(n)
插入、删除
- 数组其实位置的插入和删除，时间复杂度为O(n)
- 链表的时间复杂度为O(1)

什么是随机访问¶

比如first是第一个元素的地址，现在想访问第N个元素。随机访问：直接first+N，便可以得到第N个元素的地址，因为这些相邻元素是按顺序连续存储的。比如普通数组就是可随机访问的。

赫夫曼树 ¶

基本概念¶

路径长度
- 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度，为结点数-1
- 树的路径长度是从树根到每一结点的路径长度之和
带权路径长度
- 若结点带权，则带权路径长度为**该结点到树根之间的路径长度**与**结点上权重**的乘积
赫夫曼树
- 带权路径长度WPL(weight path length)最小的二叉树为赫夫曼树

构建赫夫曼树(自下而上)¶

根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
在F中删除这两棵树,同时将新的二叉树加入F中.
重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

构建示例¶

有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，构造哈夫曼树。

根据给定的n个权值{7,5,2,4}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
- F中有四个二叉树{a(7),b(5),c(2),d(4)}，每个二叉树左右子树为空，只有根节点
在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
- 先取最小的c和d，新结点为m，左右子树为c和d，m权值为6
在F中删除这两棵树,同时将新的二叉树加入F中.
- 在F中删除c和d，加入m，此时F中有三棵树{a(7),b(5),m(6)}
重复2、3,直到F只含有一棵树为止

赫夫曼编码¶

用于解决电报数据传输，赫夫曼编码使得电报编码长度最短，且可以保证唯一性

前缀编码
- 设计长短不等的编码，必须是任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码
赫夫曼编码
- 需要变得字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率为{w1,w2,…,wn}，以d1,d2,…,dn为叶子结点，以w1,w2,…,wn为相应叶子结点的权值来构建一棵赫夫曼树
- 规定赫夫曼树的左分支代表0，右分支代表1，从根结点到叶子结点所经过的路径分支所组成的0,1序列变为该结点对应的字符编码

译码¶

从哈夫曼树根开始，对待译码电文逐位取码。
若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；
再重新从根出发，直到电文结束。