查找算法 | yupaits的博客

顺序查找

思想： 这是最简单的算法，从头开始遍历每个元素，并将每个元素与查找元素比较，如果一致则返回。
时间复杂度： O(n)
空间复杂度： O(1)

代码示例：

public int search(int[] array, int num) {
    if (array == null || array.length == 0) {
        return -1;
    }
    for (int i = 0; i < array.length; i++) {
        if (array[i] == num) {
            return i;
        }
    }
    return -1;
}

二分查找

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

代码示例：

public int halfSearch(int[] array, int num) {
    if (array == null || array.length == 0) {
        return -1;
    }
    int lo = 0, hi = array.length - 1;
    while(lo <= hi) {
        int mid = lo + ((hi - lo) >> 1); //此处考虑边界问题不能使用 (lo + hi) / 2
        if (array[mid] == num) {
            return mid;
        } else if (array[mid] < num) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return -1;
}

hash算法

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

哈希函数：
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选的不好，容易产生同义词。
hash冲突及解决

hash冲突在所难免，解决冲突是一个复杂问题。冲突主要取决于：
- 与散列函数有关，一个好的散列函数的值应尽可能平均分布。
- 与解决冲突的哈希冲突函数有关。
- 与负载因子的大小有关。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。
解决冲突的办法：
- 开放地址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。
- 拉链法：把所有同义词，及hash值相同的记录，用单链表连接起来。
应用：字符串哈希；加密哈希；集合哈希；布隆过滤器
不足：获取有序序列复杂度高

二叉搜索树

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

插入

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

如果插入节点比当前节点值小，则插入其左孩子节点中。

复杂度：平均O(logn) 最坏O(n)

代码示例：

public Tree insert(Tree root, int val) {
    if (root == null) {
        return new Tree(val);
    }
    if (val == root.val) {
        return root;
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    } else {
        root.left = insert(root.left, val);
    }
    return root;
}

查找

某个值

思想：查找方式有点类似二分查找方法，只是这里采用的树结构进行存储。首先与根节点进行判断:
1. 如果当前节点为null，则直接返回null。
2. 如果当前节点值与查找值相同则返回当前节点。
3. 如果当前节点值小于查找值，则以递归方式到当前节点的右孩子查找。
4. 如果当前节点值大于查找值，则以递归方式到当前节点的左孩子查找。
时间复杂度：平均O(logn) 最坏O(n)

代码示例：

public Tree search(Tree root, int val) {
    if (root == null) {
        return null;
    }
    if (root.val = val) {
        return root;
    } else if (root.val > val) {
        return search(root.left, val);
    } else {
        return search(root.right, val);
    }
}

查找最小值

思想：根据二叉查找树的特点，最小节点都是在最左节点上或者如果根节点无左孩子便是其本身。

代码示例：

public Tree min(Tree root) {
    if (root == null) {
        return null;
    }
    if (root.left != null) {
        return min(root.left);
    }
    return root;
}

查找最大节点

思想：同最小节点。

代码示例：

public Tree max(Tree root) {
    if (root == null) {
        return null;
    }
    if (root.right != null) {
        return max(root.right);
    }
    return root;
}

删除

删除最小节点

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

代码示例：

public Tree deleteMin(Tree root) {
    if (root == null) {
        return null;
    }
    if (root.left != null) {
        root.left = deleteMin(root.left);
    } else if (root.right != null) {
        return root.right;
    }
    return null;
}

删除最大节点

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

代码示例：

public Tree deleteMax(Tree root) {
    if (root == null) {
        return null;
    }
    if (root.right != null) {
        root.right = deleteMax(root.right);
    } else if (root.left != null) {
        return root.left;
    }
    return null;
}

删除某个节点

思想：要删除一个节点首先需要找到该节点的位置，采用上面的查找方式进行查找。找到节点后就是删除的问题，可以按照下面的策略进行删除。
1. 如果一个节点无左孩子和右孩子，那么就可以直接删除。
2. 如果只存在一个孩子节点，则用孩子节点替换。
3. 如果存在两个孩子节点，那么可以用其左孩子最大的节点或者右孩子最小节点替换，并删除最左孩子节点或最右孩子节点。

代码示例：

public Tree delete(Tree root, int val) {
    if (root == null) {
        return null;
    }
    if (root.val == val) {
        if (root.left == null && root.right == null) {
            return null;
        } else if (root.left != null && root.right != null) {
            Tree leftBig = max(root.left);
            root.val = leftBig.val;
            root.left = delete(root.left, leftBig.val);
        } else if (root.left != null) {
            return root.left;
        } else {
            return root.right;
        }
    } else if (root.val < val) {
        root.right  = delete(root.right, val);
    } else {
        root.left = delete(root.left, val);
    }
    return root;
}

AVL查找树

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

查找

查找与二叉查找树一样。

插入

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

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

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

 1. 如果当前结点为空，创建新结点返回.
 1. 如果当前结点值和插入值相同，不做处理返回。
 1. 如果插入值大于当前结点则插入到右其右孩子结点中。插入完成后比较左右孩子结点进行判断树是否失去平衡。如果是判断属于那种类型(RR, RL),并响应的旋转。最后更新当前结点的深度(孩子结点的最大深度加1，默认null深度为-1)。
 1. 否则插入到其做孩子上。 同样比较左右孩子的深度判断是否平衡，对于失去平衡的情况下做出调整。

代码示例：

private AvlNode insert(AnyType x, AvlNode t) { 
    if (t == null) {
        return new AvlNode(x, null, null); 
    }
    int compareResult = myCompare(x, t.element); 
    if (compareResult < 0) {
        t.left = insert(x, t.left); 
        if (height(t.left) - height(t.right) == 2) {
            if (myCompare(x, t.left.element) < 0) {
                //左左情况 
                t = rotateWithLeftChild(t); 
            } else {
                //左右情况
                t = doubleWithLeftChild(t); 
            }
        } 
    } else if (compareResult > 0) {
        t.right = insert(x, t.right); 
        if (height(t.right) - height(t.left) == 2) {
            if (myCompare(x, t.right.element) < 0) {
                //右左情况 
                t = doubleWithRightChild(t); 
            } else {
                //右右情况 
                t = rotateWithRightChild(t); 
            }
        } 
    }
    //完了之后更新height值 
    t.height = Math.max(height(t.left), height(t.right)) + 1; 
    return t; 
}

删除

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

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

B-树

定义

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 为关键码的个数。
- 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空
B-树的特性：
1. 关键字集合分布在整棵树中；
2. 任何一个关键字出现且只出现在一个节点中；
3. 搜索有可能在非叶子节点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制。

查找

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

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

分两种情况：
1. 删除最底层结点中关键码
  - 若结点中关键码个数大于⎡m / 2⎤ -1，直接删去。
  - 否则除余项与左兄弟(无左兄弟，则找左兄弟)项数之和大于等于2( -1) 就与它们父结点中的有关项一起重新分配
2. 删除为非底层结点中关键码若所删除关键码非底层结点中的Ki，则可以指针Ai 所指子树中的最小关键码X 替代 Ki，然后，再删除关键码X，直到这个X 在最底层结点上，即转为(1)的情形

B+树

定义
- 有n 棵子树的结点中含有n 个关键码；
- 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。
B+树的特性
1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4. 更适合文件索引系统；

查找

对B+树可以进行两种查找运算：
- 从最小关键字起顺序查找；
- 从根结点开始，进行随机查找。
在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。
插入

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

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

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

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

红黑树

思想

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
特性
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

插入

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

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

红黑树和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)).

顺序查找

二分查找

hash算法

二叉搜索树

AVL查找树

B-树

B+树

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

红黑树

红黑树和AVL树的比较

哈夫曼树