@adamhand 2019-01-02T14:19:03.000000Z 字数 8615 阅读 693

查找算法总结

静态查找
- 顺序查找
- 插值查找
  - 二分查找
  - 插值查找
  - 斐波那契查找
动态查找
- 树表查找
  - 二叉排序树
  - 2-3树
  - 红黑树
分块查找
哈希查找

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
　　查找算法分类：
　　1）静态查找和动态查找；
　　　　注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
　　2）无序查找和有序查找。
　　　　无序查找：被查找数列有序无序均可；
　　　　有序查找：被查找数列必须为有序数列。
　　平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
　　对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
　　Pi：查找表中第i个数据元素的概率。
　　Ci：找到第i个数据元素时已经比较过的次数。

一. 静态查找

1. 顺序查找

　　说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。
　　基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
　　复杂度分析：　
　　查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
　　当查找不成功时，需要n+1次比较，时间复杂度为O(n);
　　所以，顺序查找的时间复杂度为O(n)。

public class SequenceSearch {
    public static int search(int[] arr, int target){
        for(int i = 0; i < arr.length; i++){
            if(target == arr[i]){
                return i;
            }
        }
        return -1;
    }
}

2. 二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。
　　基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
　　复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
　　二分查找有两种实现方式：递归实现和迭代实现。

//迭代实现
public class BinarySearchIterator {
    public static int search(int[] arr, int target){
        int left = 0, right = arr.length - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
//递归实现
public class BinarySearchRecursion {
    public static int search(int[] arr, int target, int left, int right){
        if(left > right)
            return -1;
        int mid = left + (right - left) / 2;
        if(arr[mid] == target){
            return mid;
        }else if(arr[mid] < target){
            return search(arr, target, mid + 1, right);
        }else {
            return search(arr, target, left, mid - 1);
        }
    }
}

3. 插值查找

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
　　打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
　　同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5，我们自然会考虑从数组下标较小的开始查找。
　　经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
　　通过类比，我们可以将查找的点改进为如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
　　也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
　　基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
　　注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
　　复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。
同理，插值查找也有递归和递推两种实现方法。
不建议使用插值查找，因为问题多多，详见代码间的注释。

/*插值查找的递归实现，待查找数组有小到大排列。
这个算法有一个问题，如果给定的target很大，那么在int mid = left + (target - A[left]) / (A[right] - A[left]) * (right - left);这句话算出来的mid会很大，就会导致下一句的A[mid]出现数组越界的错误。在递推法实现的时候可以避免*/
public class InsertionSearchRecursion {
    public static int search(int[] A, int target, int left, int right){
        int mid = left + (target - A[left]) / (A[right] - A[left]) * (right - left);
        if(A[mid] == target)
            return mid;
        else if(A[mid] > target)
            return search(A, target, left, mid - 1);
        else
            return search(A, target, mid + 1, right);
    }
}
/*待查找的数组由小到大排列。
这个算法也存在一个问题，还是出现在mid = left + (target - arr[left]) / (arr[right] - arr[left]) * (right - left);这句话。这句话中涉及到整数的除法，整数的除法结果还是整数，结果是不允许有小数点的，这就会导致判断错误。
比如要在数组A={1, 2, 6, 9, 45, 63, 85}查找元素84，按照程序中求mid的方法，我们期望第一次得到的mid为：mid=0 + (84 - 1) / (85 - 1) * (6 - 0) = 0 + 83 / 84 * 6 = 0 + 0.98 * 6 = 5.92。但是，在计算83/84的时候，结果不是0.98，而是0。这就出了问题*/
public class InsertionSearch {
    public static int search(int[] arr, int target){
        int left = 0, right = arr.length - 1;
        int mid = 0;
        if(target > arr[right])
            return -1;
        while(left <= right){
            mid = left + (target - arr[left]) / (arr[right] - arr[left]) * (right - left);
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

4. 斐波那契查找

斐波那契数列有个特点：随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，也就是“黄金分割比例”。利用这个特性，我们就可以将黄金比例运用到查找技术中，而不是像折半查找一样每次取二分之一。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始时待查找表中记录的个数为某个斐波那契数小1，即n=F(k)-1(后面会解释为什么，以及如果不满足这个条件时该怎么办);
与折半查找相似，斐波那契查找开始将k值与第F(k-1）位置的记录进行比较(即mid=low+F(k-1)-1,比较结果也分为三种：

相等，mid位置的元素即为所求
> ,low=mid+1,k-=2;
说明:low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
< ,high=mid-1,k-=1;
说明:low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找

那么，为什么必须满足n=F(k)-1这个条件呢？如果不满足怎么办？
之所以要满足n=F(k)-1，是因为便于将数组分割成两个部分，表中的数据是F(k)-1个，使用mid值进行分割又用掉一个，那么剩下F(k)-2个。正好分给两个子序列，每个子序列的个数分别是F(k-1)-1与F(k-2)-1个，这样格式上统一，方便程序的编写。
如果给定的数组不满足n=F(k)-1这个条件，就需要找到比n的值大且离n的值最近的斐波那契数F(k)，用长度F(k)-1构造一个数组，将原数组放入新数组，并用原数组最后一个值填充新数组后面的空白。这样，如果查找的位置落到填充的位置，就确定要找的数就是原数组最后一个数了。

public class FinonacciSearch {
    //构造一个长度为20的斐波那契数组
    private static int[] fibonacci(){
        int[] f = new int[20];
        f[0] = f[1] = 1;
        for(int i = 2; i < f.length; i++){
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
    public static int finonacciSearch(int[] arr, int target){
        int left = 0, mid = 0, right = arr.length - 1;
        int k = 0;
        int[] f = fibonacci();
        //找到大于arr.length且最接近arr.length的斐波那契数
        while(arr.length > f[k] - 1)
            k++;
        //构造长度为f[k]-1的新数组
        int[] temp = new int[f[k] - 1];
        for(int i = 0; i < arr.length; i++){
            temp[i] = arr[i];
        }
        //用原数组最右边的数填充新数组的空白
        for(int i = arr.length; i < f[k] - 1; i++){
            temp[i] = arr[right];
        }
        while(left <= right){
            mid = left + f[k - 1] - 1;
            if(temp[mid] > target){
                right = mid - 1;
                k -= 1;
            }else if(temp[mid] < target){
                left = mid + 1;
                k -= 2;
            }else {
                if(mid <= right)    // 若相等则说明mid即为查找到的位置
                    return mid;
                else
                    return right;  // mid的值已经大于right,进入扩展数组的填充部分,即原数组最后一个数就是要查找的数。
            }
        }
        return -1;
    }
}

动态查找

5. 二叉查找树

基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

6. 红黑树(RBTree)

RBTree定义

任何一个节点都有颜色，黑色或者红色
根节点是黑色的
父子节点之间不能出现两个连续的红节点
任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
空节点被认为是黑色的

数据结构表示如下：

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

RBTree在理论上还是一棵BST树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。

RBTree的旋转操作

旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。
Rotate分为left-rotate（左旋）和right-rotate（右旋），区分左旋和右旋的方法是：待旋转的节点从左边上升到父节点就是右旋，待旋转的节点从右边上升到父节点就是左旋。

RBTree的查找操作

RBTree的查找操作和BST的查找操作是一样的。

RBTree的插入操作

RBTree的插入与BST的插入方式是一致的，只不过是在插入过后，可能会导致树的不平衡，这时就需要对树进行旋转操作和颜色修复（在这里简称插入修复），使得它符合RBTree的定义。

新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：

叔叔节点也为红色。
叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。

插入操作-case 1

case 1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。

插入操作-case 2

case 2的操作是将B节点进行右旋操作，并且和父节点A**互换颜色**。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以了。

插入操作-case 3

case 3的操作是将C节点进行左旋，这样就从case 3转换成case 2了，然后针对case 2进行操作处理就行了。case 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。

插入操作的总结

插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于case 1操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节（向上回溯）。

祖父节点调节后如果还是遇到它的祖父颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义，修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。

RBTree的删除操作

删除操作首先需要做的也是BST的删除操作，删除操作会删除对应的节点，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作，使的树符合红黑树的定义，符合定义的红黑树高度是平衡的。

删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

删除修复操作分为四种情况(删除黑节点后)：

待删除的节点的兄弟节点是红色的节点。
待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。
待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。
待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。

删除操作-case 1

由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。

case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case 1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。

删除操作-case 2

case 2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合RBTree的定义为止。

case 2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。

删除操作-case 3

case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4状态了，在case 4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。

之所以说case-3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过case 2操作完后向上回溯出现的状态。之所以会出现case 3和后面的case 4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4。

删除操作-case 4

Case 4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。

Case 4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。

删除操作的总结

红黑树的删除操作是最复杂的操作，复杂的地方就在于当删除了黑色节点的时候，如何从兄弟节点去借调节点，以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的，这样只能通过选择操作让他上升到父节点，而由于它是红节点，所以它的子节点就是黑的，可以借调。

对于兄弟节点是黑色节点的可以分成3种情况来处理，当所以的兄弟节点的子节点都是黑色节点时，可以直接将兄弟节点变红，这样局部的红黑树颜色是符合定义的。但是整颗树不一定是符合红黑树定义的，需要往上追溯继续调整。

对于兄弟节点的子节点为左红右黑或者 (全部为红，右红左黑)这两种情况，可以先将前面的情况通过选择转换为后一种情况，在后一种情况下，因为兄弟节点为黑，兄弟节点的右节点为红，可以借调出两个节点出来做黑节点，这样就可以保证删除了黑节点，整棵树还是符合红黑树的定义的，因为黑色节点的个数没有改变。

红黑树的删除操作是遇到删除的节点为红色，或者追溯调整到了root节点，这时删除的修复操作完毕。

参考：
红黑树深入剖析及Java实现