登录
目录
当前位置： 首页 > 文档资料 > 互联网面试笔记 >

第三章 算法与数据结构 - 3.2 查找

优质
小牛编辑
128浏览
2023-12-01

一.顺序查找

1.1 思路：这是最简单的算法，从头开始遍历每个元素，并将每个元素与查找元素比较，如果一致则返回。

1.2 时间复杂度: O(N)

1.3 空间复杂度: O(1)

1.4 代码：

  1. public int search(int[] array, int num) {
  2.     if(array == null || array.length == 0) {
  3.         return -1;
  4.     }
  5.     for(int i = 0; i < array.length; i++) {
  6.         if (array[i] == num) {
  7.             return i;
  8.         }
  9.     }
  10.     return -1;
  11. }

二.二分查找

2.1 思路：二分查找前提是查找的数组是有序的，利用数据有序的特性提高查找性能。首先与数组中间位置的值比较，如果查找值大于中间位置值，则对数组右边以相同的思路查找，否则在左边以相同方式查找。这种方式使得每次查找范围变为原来的1/2.

2.2 时间复杂度: O(log2n)
2.3 空间复杂度: O(1)

  1. public int halfSearch(int[] array, int num) {
  2.     if(array == null || array.length == 0) {
  3.          return -1;
  4.     }
  5.     int lo = 0, hi = array.length-1;
  6.     while(lo <= hi) {
  7.         int mid = (lo + hi) >> 1;
  8.         if (array[mid] == num) {
  9.             return mid;
  10.         } else if (array[mid] < num) {
  11.             hi = mid -1;
  12.         } else {
  13.             lo = mid + 1;
  14.         }
  15.     }
  16.     return -1;
  17. }

三. 变种二分查找

http://www.cr173.com/html/20428_1.html

四. hash 算法

4.1 思想：哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上，并将关键字对应的值存储在该地址空间，可以通过关键字快速获取对应的值，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
4.2 查找复杂度: O(1)
4.3 哈希函数：

  1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
  2. 数字分析法：因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
  3. 平方取中法：取关键字平方后的中间几位作为散列地址
  4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
  5. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

4.4 hash冲突及解决
hash冲突在所难免，解决冲突是一个复杂问题。冲突主要取决于：
（1）与散列函数有关，一个好的散列函数的值应尽可能平均分布。
（2）与解决冲突的哈希冲突函数有关。
（3）与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。
解决冲突的办法：
（1）开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。
（2) 拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。

4.5 应用：
1.字符串哈希
2.加密哈希
3.几何哈希
4.布隆过滤器

4.6 不足：获取有序序列复杂度高

参考：
http://www.tuicool.com/articles/RnErui

五.二叉树搜索树

5.1 思想

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.任意节点的左、右子树也分别为二叉查找树。
4.没有键值相等的节点（no duplicate nodes）。
复杂度: 插入和查找的时间复杂度均为O(logN), 最坏为O(N)

5.2 插入

  1. 如果当前结点是null，则创建新结点返回。
  2. 如果插入结点比当前结点值大，则插入其右孩子结点中。

  3. 如果插入结点比当前结点值小，则插入其左孩子结点中。
    复杂度: 平均 O(logn) 最坏O(n)
    代码:

    1.  public Tree insert(Tree root, int val) {
    2.      if (root == null) {
    3.          return new Tree(val);
    4.      }
    5.      if (val == root.val) {
    6.          return root;
    7.      } else if (val > root.val) {
    8.          root.right = insert(root.right, val);
    9.      } else {
    10.          root.left = insert(root.left, val);
    11.      }
    12.      return root;
    13.  }

5.3 查找

5.3.1 某个值

思想:查找方式有点类型二分查找方法，知识这里采用的树结构进行存储。首先与根结点进行判断:

  1. 如果当前结点为null，则直接放回Null。
  2. 如果当前结点值与查找值相同则返回当前结点.
  3. 如果当前结点值小余查找值，则递归地到当前结点的右孩子查找

  4. 如果当前结点值大于查找值，则递归地到当前结点的左孩子查找。
    时间复杂度: 平均O(logn) 最坏O(n)

    public Tree search(Tree root, int val) {

    1.  if(root == null) {
    2.      return null;
    3.  }
    4.  if(root.val == val) {
    5.      return root;
    6.  } else if(root.val > val) {
    7.      return search(root.left, val);
    8.  } else {
    9.      return search(root.right, val);
    10.  }

    }

5.3.2 查找最小值

思想:根据二叉搜索树的特点，最小结点都是在最左结点上或者如果根结点无左孩子便是其本身.

  1. public Tree min(Tree root) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     if (root.left != null) {
  6.         return min(root.left);
  7.     }
  8.     return root;
  9. }

5.3.2 查找最大结点

思想: 同最小结点。

  1. public Tree max(Tree root) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     if (root.right != null) {
  6.         return max(root.right);
  7.     }
  8.     return root;
  9. }

5.4 删除

5.4.1 删除最小结点

思想:找到根结点最左结点，如果其不存在右孩子则直接删除，否则用右孩子替换最左结点。需要注意的是根结点可能为null和不存在做孩子的情况。

  1. public Tree deleteMin(Tree root) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     if(root.left != null) {
  6.         root.left = deleteMin(root.left);
  7.     } else if (root.right != null) {
  8.         return root.right;
  9.     }
  10.     return null;
  11. }

5.4.2 删除最大结点

思想: 与删除最小结点类型，根据二叉搜索树的特性，最大结点是根结点的最右孩子。所以只要找到最右孩子结点，其存在左结点的话就用左结点替换否则直接删除.

  1.  public Tree deleteMax(Tree root) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     if(root.right != null) {
  6.         root.right = deleteMax(root.right);
  7.     } else if(root.left != null) {
  8.         return root.left;
  9.     }
  10.     return null;
  11. }

5.4.3 删除某个结点

思想:要删除一个结点首先需要找到该结点的位置，采用上面的查找方式进行查找。找到结点后就是删除的问题的，可以按照下面的策略进行删除。

  1. 如果一个结点无做孩子和右孩子，那幺就可以直接删除
  2. 如果只存在一个孩子结点，则用孩子结点替换。
  3. 如果存在两个孩子结点，那幺可以用其左孩子最大的结点或右孩子最小结点替换，并删除最左孩子结点或最右孩子结点.
  1.  public Tree delete(Tree root, int val) {
  2.     if(root == null) {
  3.         return null;
  4.     }
  5.     if(root.val == val) {
  6.         if(root.left == null && root.right == null) {
  7.             return null;
  8.         } else if(root.left!= null && root.right != null) {
  9.             Tree leftBig = max(root.left);
  10.             root.val = leftBig.val;
  11.             root.left = delete(root.left, leftBig.val);
  12.         } else if(root.left != null){
  13.             return root.left;
  14.         } else {
  15.             return root.right;
  16.         }
  17.     } else if(root.val < val) {
  18.         root.right = delete(root.right, val);
  19.     } else {
  20.         root.left = delete(root.left, val);
  21.     }
  22.     return root;
  23. }

参考: http://www.cnblogs.com/vamei/archive/2013/03/17/2962290.html
http://blog.jobbole.com/79305/

5.5 相关的算法题

剑指offer:

6. AVL查找树

6.1 思想

二叉树查找树在插入时没有对二叉树的深度和结构做一个调整，使得叶子结点深度不一，在查找时深度越深的结点时间复杂度越高。为了改进查找的时间时间复杂度，于是出现了平衡二叉树(AVL).平衡二叉树使得每个结点的左结点和右结点的深度差不超过1.

6.2 查找

查找与二叉查找树一样。

6.3 插入

  1. 当在AVL中插入新的结点时，需要根据实际情况对AVL中的某些结点做单旋转或双旋转操作，单旋转表示做一次顺时针或逆时针的旋转操作，而双旋转则做两次单旋转操作（先顺时针后逆时针，或者先逆时针后顺时针），单旋转发生在LL型插入和RR型插入，而双旋转则发生在LR型插入和RL型插入。以下的失去平衡点都指的是离插入点最近的那个失去平衡的结点。

LL型：插入点位于失去平衡点的左孩子的左子树上；
RR型：插入点位于失去平衡点的右孩子的右子树上；
LR型：插入点位于失去平衡点的左孩子的右子树上；
RR型：插入点位于失去平衡点的右孩子的左子树上。

插入思路
和二叉搜索树的插入一样，首先在树中找到对应的位置然后插入，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。　
具体插入过程如下:

  1. 如果当前结点为空，创建新结点返回.
  2. 如果当前结点值和插入值相同，不做处理返回。
  3. 如果插入值大于当前结点则插入到右其右孩子结点中。插入完成后比较左右孩子结点进行判断树是否失去平衡。如果是判断属于那种类型(RR, RL),并响应的旋转。最后更新当前结点的深度(孩子结点的最大深度加1，默认null深度为-1)。
  4. 否则插入到其做孩子上。 同样比较左右孩子的深度判断是否平衡，对于失去平衡的情况下做出调整。
  1. private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> t) {
  2.     if (t == null)
  3.         return new AvlNode<AnyType>(x, null, null);
  4.     int compareResult = myCompare(x, t.element);
  5.     if (compareResult < 0) {
  6.         t.left = insert(x, t.left);
  7.         if (height(t.left) - height(t.right) == 2) {
  8.             if (myCompare(x, t.left.element) < 0)     //左左情况
  9.                 t = rotateWithLeftChild(t);
  10.             else                                    //左右情况
  11.                 t = doubleWithLeftChild(t);
  12.         }
  13.     } else if (compareResult > 0) {
  14.         t.right = insert(x, t.right);
  15.         if (height(t.right) - height(t.left) == 2) {
  16.             if (myCompare(x, t.right.element) < 0)        //右左情况
  17.                 t = doubleWithRightChild(t);
  18.             else                                        //右右情况
  19.                 t = rotateWithRightChild(t);
  20.         }
  21.     }
  22.     //完了之后更新height值
  23.     t.height = Math.max(height(t.left), height(t.right)) + 1;
  24.     return t;
  25. }

6.4 删除

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。
a.当被删除节点n是叶子节点，直接删除
b.当被删除节点n只有一个孩子，删除n，用孩子替代该节点的位置
c.当被删除结点n存在左右孩子时，真正的删除点应该是n的中序遍在前驱，或者说是左子树最大的节点，之后n的值替换为真正删除点的值。这就把c归结为a，b的问题。

从删除的结点处自低向上向根结点折回，根据当前结点的左右孩子深度判断是否平衡，如果不平衡则按选择规则进行旋转。最后更新当前结点深度，如此递归折回到根结点。

http://blog.csdn.net/xiaofan086/article/details/8294382
http://blog.csdn.net/liyong199012/article/details/29219261
http://www.mamicode.com/info-detail-90162.html

七. B-树（B树）

7.1 定义

B-树是一种平衡的多路查找树，它在文件系统中很有用。
定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树：

  • 树中每个结点至多有m 棵子树；
  • 若根结点不是叶子结点，则至少有两棵子树；
  • 除根结点之外的所有非终端结点至少有⎡m/2⎤ 棵子树；
  • 所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，…，Kn，An）
    其中：Ki（i=1,2,…,n）为关键码，且Ki< Ki+1，Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn， ⎡m/2⎤ −1 ≤ n ≤m −1 ，n 为关键码的个数。
  • 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空

7.2 查找

B-树的查找是由两个基本操作交叉进行的过程，即

  • 在B-树上找结点；
  • 在结点中找关键码。

由于，通常B-树是存储在外存上的，操作⑴就是通过指针在磁盘相对定位，将结点信息读入内存，之后，再对结点中的关键码有序表进行顺序查找或折半查找。因为，在磁盘上读取结点信息比在内存中进行关键码查找耗时多，每次向下搜索一层都需要从内存中加载磁盘信息，B-树的层次树是决定B-树查找效率的首要因素。

7.2 插入

在B-树上插入关键码与在二叉排序树上插入结点不同，关键码的插入不是在叶结点上
进行的，而是在最底层的某个非终端结点中添加一个关键码，若该结点上关键码个数不超过m-1 个，则可直接插入到该结点上；否则，该结点上关键码个数至少达到m 个，因而使该结点的子树超过了m棵，这与B-树定义不符。所以要进行调整，即结点的“分裂”。方法为：关键码加入结点后，将结点中的关键码分成三部分，使得前后两部分关键码个数个结点将其插入到父结点中。若插入父结点而使父结点中关键码个数超过m-1，则父结点继续分裂，直到插入某个父结点，其关键码个数小于m。可见，B-树是从底向上生长的。

7.3 删除

分两种情况：
(1)删除最底层结点中关键码

  • 若结点中关键码个数大于⎡m / 2⎤ -1，直接删去。
  • 否则除余项与左兄弟(无左兄弟，则找左兄弟)项数之和大于等于2( -1) 就与它
    们父结点中的有关项一起重新分配

(2)删除为非底层结点中关键码
若所删除关键码非底层结点中的Ki，则可以指针Ai 所指子树中的最小关键码X 替代
Ki，然后，再删除关键码X，直到这个X 在最底层结点上，即转为(1)的情形

7.2 B-树的特性：

  1. 关键字集合分布在整颗树中；
  2. 任何一个关键字出现且只出现在一个结点中；
  3. 搜索有可能在非叶子结点结束；
  4. 其搜索性能等价于在关键字全集内做一次二分查找；
  5. 自动层次控制；

http://c.biancheng.net/cpp/html/1028.html

八. B+树

8.1 定义

  • 有n 棵子树的结点中含有n 个关键码；
  • 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且
    叶子结点本身依关键码的大小自小而大的顺序链接。
  • 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。

8.2 B+的特性

  1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
  2. 不可能在非叶子结点命中；
  3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
  4. 更适合文件索引系统；

8.3 操作

1)查找操作

对B+树可以进行两种查找运算：

  • 从最小关键字起顺序查找；
  • 从根结点开始，进行随机查找。

在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

2).插入操作

B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。(算法见百度百科)

3)删除操作

B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。

7.2 B+树和B-树最大的不同点：

1).B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。

2).在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好，而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B+树的性能可能还会好些，而且B+树的叶子节点使用指针连接在一起，方便顺序遍历(例如查看一个目录下的所有文件，一个表中的所有记录等)，这也是很多数据库和文件系统使用B+树的缘故。

3）B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/25/2608880.html
http://blog.csdn.net/v_JULY_v/article/details/6530142/

8. 红黑树

思想

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

特性

性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

插入

II、红黑树插入的几种情况：
情况1，z的叔叔y是红色的。
情况2：z的叔叔y是黑色的，且z是右孩子
情况3：z的叔叔y是黑色的，且z是左孩子

删除

III、红黑树删除的几种情况。
情况1：x的兄弟w是红色的。
情况2：x的兄弟w是黑色的，且w的俩个孩子都是黑色的。
情况3：x的兄弟w是黑色的，且w的左孩子是红色，w的右孩子是黑色。
情况4：x的兄弟w是黑色的，且w的右孩子是红色的。

http://www.cnblogs.com/daoluanxiaozi/p/3340382.html

红黑树和AVL树的比较：

红黑树：

  • (1)并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。
  • (2)此外，由于它的设计，任何不平衡都会在三次旋转之内解决。红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

AVL树：

  • 它的左子树和右子树都是AVL树，左子树和右子树的高度差不能超过;
  • 查找、插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树;
  • 一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
    一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
    一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).
免责声明： 以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。
@小牛知识库 xnip.cn