大话数据结构——查找

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解查找。

查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

顺序表查找

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个记性记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

/**
 * 顺序查找
 */
public class SequentialSearch {
    public int sequentialSearch(int[] array, int key){
        if(array.length>0){
            for(int i=0;i<array.length;i++){
                if(array[i]==key)
                    return i+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,3,5,4,6,8,7};
        SequentialSearch sequentialSearch=new SequentialSearch();
        int n=sequentialSearch.sequentialSearch(array,8);
        System.out.println("数8在数组中的第"+n+"个位置");
    }
}

有序表查找

折半查找

折半查找又称二分查找。它的前提是线性表中的记录必须是关键码有序（通常是从小到大有序），线性表必须采用顺序存储。
​ 折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。 时间复杂度为O(logn）

/**
 * 折半查找||二分查找
 */
public class BinarySearch {
    /**
     * 非递归实现
     */
    public int binarySearch(int[] array, int key){
        if(array.length>0){
            int low=0;
            int high=array.length-1;
            int mid;
            while(low<=high){
                mid=(low+high)/2;
                if(key<array[mid]){
                    high=mid-1;     //最高下标调整到中位下标小1位
                }else if(key>array[mid]){
                    low=mid+1;      //最低下标调整到中位下标大1位
                }
                else{
                    return mid+1;
                }
            }
        }

        return -1;
    }
    /**
     * 递归实现
     */
    public int binarySearch2(int[] array,int key,int low,int high){
        if(low<=high){
            int mid=(low+high)/2;
            if(key<array[mid]){
                return binarySearch2(array,key,low,mid-1);
            }else if(key>array[mid]){
                return binarySearch2(array,key,mid+1,high);
            }else{
                return mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,3,5,9,11,15};
        BinarySearch binarySearch=new BinarySearch();
        System.out.println("---------非递归实现二分查找----------");
        int n=binarySearch.binarySearch(array,11);
        System.out.println("数11在数组中的第"+n+"个位置");
        System.out.println("---------递归实现二分查找----------");
        int m=binarySearch.binarySearch2(array,11,0,array.length-1);
        System.out.println("数11在数组中的第"+m+"个位置");
    }
}

插值查找

算法思想：插值查找的关键是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式mid=low+(key-a[low])*(high-low)/(a[high]-a[low])。

时间复杂度：从时间复杂度上看，它也是O(logn)

优缺点：对于表长比较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比这般查找要好很多。

斐波那契查找

算法思想：依然是对查找点的优化，采用Fibonacci数组，找到对于当前长度的有序表的黄金分割点，作为每次的中间值。

时间复杂度：时间复杂度和其他两种有序表查找相同，都是O(logn)

优缺点：对于平均性能，斐波那契查找要优于折半查找，但如果是最坏情况，查找效率低于折半查找。

小结：有序表查找是一种针对查找优化的表结构，查找的时间复杂度是O(logn)。但有序表的插入和删除性能是比较差的，插入和删除不能破坏有序表的特性。

线性索引查找

索引是把一个关键字与它对应的记录相关联的过程。一个索引由若干个索引构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。
​ 线性索引是将索引项集合组织为线性结构，称为索引表。 以下重点介绍三种线性索引：稠密索引、分块索引、倒排索引。

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。

算法思想：稠密索引要应对的可能是成千上万的数据，因此对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。因此可以对索引使用折半、插值、斐波那契等有序表查找算法，大大提高了效率。

时间复杂度：因为对于索引的查找使用的也是有序表的查找算法，时间复杂度是O(logn)。

优缺点：和有序表类似的是，稠密索引必须要维护索引的有序性。另外如果数据量很大，也要同时维护一个同样规模的索引，可能就需要反复访问磁盘，降低了查找性能。

分块索引

算法思想：如果对索引进行一次分级呢？对于一级索引下，可能会有多个记录，称之为一个块，块内的记录再获得一个二级的索引。这些块有一个条件，就是块内无序，块间有序。块内无序就是在一级索引内部的记录可以是无序的，只要落在索引的范围内就可以；块间有序就是下一个块所有的关键字都要大于上一个块的最大关键字。因此对于一个块结构来讲，它具有最大关键码，块中的记录个数和指向块首数据的指针。

时间复杂度：分块索引在查找时，先找到查找记录所在的块，在查找在块内的为孩子。设n个记录，平均分成m个块，每个块有t个记录，这样平均查找次数就是(m+1)/2 + (t+1)/2 = (n/t + t)/2 + 1 >= logn + 1。所以分块索引的时间复杂度介于O(n)和O(logn)之间。

分块索引兼顾了有序和无序的需求，平衡了插入，删除和查找的性能，普遍用于数据库查找技术等。

倒排索引

算法思想：倒排索引主要应用于搜索引擎。基本思想就是将得到的key-value关系进行一个反映射，得到某个value有多少个key指向它。比如查找某个单词出现在哪些文章中，可以先访问文章中的所有单词，建立一个单词的索引，将出现该单词的文章记录到索引中。这样在搜索时直接输入单词，就能得到文章列表。

优缺点：倒排索引的优点是速度快，缺点就是记录不等长，维护比较困难，插入和删除都要做相应的处理。比如删除某个文章，就可能要对所有的单词都进行考察。

二叉排序树

算法思想：有序表的问题就是如果插入一个较小的记录，就要把比它大的记录依次移动，腾出插入的位置。如果用二叉树来实现呢，只需要让这个较小的记录成为某个结点的左孩子就可以了。为什么是左孩子呢，和二叉排序数的定义有关，简单来说，二叉排序树的中序遍历就是一个有序表。这样插入任何一个记录都不需要改变已经建好的树。

查找：查找某个记录时，从根结点开始，如果查找记录大于该结点的值，就走右子树；如果小于该结点的值，就走左子树。不断向下查找，直到找到该记录，或者到叶子结点的值和查找记录不同，未找到该记录。

插入：插入和查找类似，向下找到最接近它的结点，然后把该记录作为它的左孩子或者右孩子。

删除：删除相对查找和插入来讲复杂一点，主要复杂在如果处理它的子树。下面的算法是这么处理的：首先获取要删除的节点的parent节点，如果找不到直接返回；找到parent之后，判断删除节点是parent节点的左节点还是右节点，并保存在一个临时的tmp节点；接下来要做删除操作，首先判断的是删除节点是否具有右节点：如果没有右节点的话，且删除节点是parent左节点，就直接让parent左节点指向删除节点的左节点，如果删除节点是parent右节点，同样直接让parent右节点指向删除节点的左节点；没有右节点是最好处理的情况，最复杂的是删除节点有右节点：首先将删除节点记录为father ,删除节点的右节点为tmp；如果tmp没有左节点，只有右节点最好处理了，直接移除father，将tmp补在father；如果tmp有左节点，我们不断向下直到找到最底下的左节点，将其替换删除节点即可。

时间复杂度：如果二叉排序树是平衡的，那么查找的时间复杂度是O(logn)；如果是不平衡，比如最极端的斜树，那么时间复杂度是O(n)。

优缺点：二叉排序树保留了有序表查找高效的特点，最理想的情况能达到O(logn)的时间复杂度，并且解决了插入和删除记录的问题，能够保证树的整体结构不受影响。缺点就是可能在插入的过程中，二叉排序树不能保持平衡，出现了某一边的树远远大于另一边，降低了查找的效率。后面提到的平衡二叉树解决了这个问题。

/**
 * 二叉排序树
 */
public class BinarySearchTree {
    BiTreeNode root;
    // 非递归方式插入新的节点数据
    public boolean insert(int data){
        if(!find(data)){
            BiTreeNode newNode=new BiTreeNode(data);
            if(root==null){
                root=newNode;
            } else {
                BiTreeNode current=root;
                BiTreeNode parent;
                while(true){
                    parent=current;
                    if(data<current.data){
                        current=current.left;
                        if(current==null){
                            parent.left=newNode;
                            return true;
                        }
                    }else{
                        current=current.right;
                        if(current==null){
                            parent.right=newNode;
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    //非递归方式实现查询
    public boolean find(int data){
        BiTreeNode current=root;
        while(current!=null){
            if(current.data==data){
                return true;
            }else if(data<current.data){
                current = current.left;
            }else{
                current = current.right;
            }
        }
        return false;
    }

    //删除值为data的节点
    public boolean remove(int data){
        BiTreeNode dummy=new BiTreeNode(-1);
        dummy.left=root;
        BiTreeNode node;
        BiTreeNode parent=findParent(dummy,root,data);
        if(parent.left!=null && parent.left.data==data){
            node=parent.left;
        }else if(parent.right!=null && parent.right.data==data){
            node=parent.right;
        }else{
            return false;
        }
        delete(parent,node);
        return true;
    }

    //查找父节点
    private BiTreeNode findParent(BiTreeNode parent,BiTreeNode current,int data){
        if(current==null){
            return parent;
        }else if(current.data==data){
            return parent;
        }else if(current.data>data){
            return findParent(current,current.left,data);
        }else{
            return findParent(current,current.right,data);
        }
    }

    //删除节点
    private void delete(BiTreeNode parent,BiTreeNode current){
        if(current.left==null){
            if(parent.left==current){
                parent.left=current.right;
            }else{
                parent.right=current.right;
            }
        }else if(current.right==null){
            if(parent.left==current){
                parent.left=current.left;
            }else{
                parent.right=current.left;
            }
        }else{
            BiTreeNode father =current;
            BiTreeNode node =current.right;
            while(node.left!=null){     //转左，然后向右到尽头（找待删结点的后继）
                father=node;
                node=node.left;
            }

            if(father.left==node){      //将待删结点的后继接上
                father.left=node.right;
            }else{
                father.right=node.right;
            }

            if(parent.left==current){
                parent.left=node;
            }else{
                parent.right=node;
            }

            node.left=current.left;
            node.right=current.right;

            if(root==current){      //如果根结点，要将根节点重置
                root=node;
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree=new BinarySearchTree();
        binarySearchTree.insert(8);
        binarySearchTree.insert(3);
        System.out.println(binarySearchTree.find(8));
        System.out.println(binarySearchTree.find(3));
        System.out.println(binarySearchTree.root.left.data);
        System.out.println(binarySearchTree.insert(3));
        binarySearchTree.insert(10);
        System.out.println(binarySearchTree.root.right.data);
        binarySearchTree.insert(2);
        binarySearchTree.insert(7);
        System.out.println(binarySearchTree.root.left.right.data);
        binarySearchTree.insert(11);
        binarySearchTree.insert(9);
        System.out.println(binarySearchTree.remove(8));
        System.out.println("is find 8 ?"+binarySearchTree.find(8));
        System.out.println("root is "+binarySearchTree.root.data);
        System.out.println(binarySearchTree.remove(3));
        System.out.println("is find 3 ?"+binarySearchTree.find(3));
        System.out.println("root is "+binarySearchTree.root.left.data);
    }
}
/**
 * 二叉树结点
 */
public class BiTreeNode {
    int data;
    BiTreeNode left;
    BiTreeNode right;
    public BiTreeNode(int data){
        this.data=data;
        this.left=null;
        this.right=null;
    }
}

平衡二叉树（AVL树）

平衡二叉树是一种二叉排序树，其中每一个节点的的左子树和右子树的高度差之多等于1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)。

最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称为最小不平衡子树。

判断是否为平衡二叉树：

public class BalancedBinaryTree extends BinarySearchTree {
    /**
     * 判断结点是否平衡
     */
    public boolean isBalanced (BiTreeNode node){
        return maxDepth(node)!=-1;
    }
    /**
     * 求结点的最大深度
     * 若该结点不平衡，则深度为-1
     */
    private int maxDepth(BiTreeNode node){
        if(node==null){
            return 0;
        }
        int left=maxDepth(node.left);
        int right=maxDepth(node.right);
        //若左子树或右子树不平衡，或其高度差大于1,则该结点不平衡
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }

    public static void main(String[] args) {
        BalancedBinaryTree tree=new BalancedBinaryTree();
        tree.insert(8);
        tree.insert(3);
        tree.insert(10);
        tree.insert(12);
        System.out.println(tree.isBalanced(tree.root));
        tree.insert(15);
        System.out.println(tree.isBalanced(tree.root));
    }
}

多路查找树

多路查找树(mutil-way search tree)，其每一个节点的孩子树可以多于两个，且每个节点处可存储多个元素。

散列表查找

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。

散列技术最适合的求解问题是查找与给定值相等的记录。我们把上述的对应关系f称为散列函数，又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表。

散列函数的构造方法：

直接定址法：取关键字的某个线性函数，f(key)=a*key+b；优点：简单、均匀、不会产生冲突，适合事先知道关键字的分布，查找表较小且连续，不常用。
​ 数字分析法：抽取，使用关键字的一部分来计算存储位置，适合事先知道关键字的分布且关键字若干位的分布较均匀，关键字位数较多。
​ 平方取中法：先（关键字^2）再抽取中间位，适合不知道关键字分布，关键字位数较少。
​ 除留余数法：散列表长m，f(key)=key MOD p，(p≦m)，其中可以对关键字取模，也可以在折叠、平方取中后再取模，缺点：p值取的不好，很容易有冲突、出现同义词，取的好也不容易避免冲突，最常用。
​ 随机数法：f(key)=random(key)，适合关键字长度不等。

处理散列冲突的方法：

开放定址探测法：单向寻找，线性探测法。改进，di=1^2,-1^2,2^2,-2^2,…,q^2,-q^2,(q≦m/2)，双向寻找，二次探测法，伪随机数，随机种子，di=random(di)，随机探测法。
​ 再散列函数法：一旦发生冲突就换一个散列函数，优点：使得关键字不会产生聚集。缺点：增加了计算时间。
​ 链地址法：有冲突的关键字存储在一个单链表中，同义词子表。优点：冲突较多时，不会找不到空地址缺点：查找时可能需要遍历单链表。
​ 公共溢出区法：有冲突的关键字都放在公共溢出表，散列表=基本表+溢出表。查找：先通过散列函数得到散列地址在基本表中找，如果没有，再到溢出表中顺序找。适合冲突较少的情况。
散列表的查找：散列表的查找性能取决于：
1）关键字的分布，2）散列函数的选择，3）处理冲突的方法，4）装填因子α装填因子=记录个数/散列表长度，α=n/m，通常将散列表的空间设置的比查找表/集合大，空间换时间。