搜索算法顺序、二分、二叉搜索树和红黑树的详细对比和总结

terry 2年前 (2023-09-25) 阅读数 52 #后端开发

一般使用符号表来存储键值对，就像字典一样，值是通过索引。如果重复键覆盖该值。我们希望找到一种高效的搜索算法，使得在平均情况和最坏情况下时间复杂度都能达到O(logn)。下面将逐步介绍这四种算法，最终实现我们的目标。

顺序查找

是用链表实现的，数据无法建立索引。必须要遍历才能找到数据，速度比较慢。搜索和插入时间复杂度为O(n)并且无法保证排序。但实现简单，适合小数据。

public class SequentialSearchST<key,value>  {
    private Node head;
    private int size=0;
    public void put(Key key,Value v){

        Node p=head;
        while(p!=null){
            if(p.key.equals(key)){
                p.v=v;
                return;
            }
            p=p.next;
        }

        head=new Node(key,v,head);
        size++;

    }

    public Value get(Key key){
        Node p=head;
        while (p!=null){
            if(p.key.equals(key)){
                return  p.v;
            }
            p=p.next;
        }
        return null;

    }
}
</key,value>

二分查找

使用数组存储数据以保证顺序。二分查找速度很快，但仅适用于搜索。由于必须保证插入顺序，因此必须将数据向后移动才能插入。搜索复杂度为O(logn)，插入复杂度为O(n)。

public class BinarySearch {

    public void put(Key key,Value value){
        int index=rank(key);
        //键相等则覆盖值
        if(keys[index]!=null&&key.compareTo(keys[index])==0){ 
            values[index]=value;
            return;
        }
        //把数据往后移，以便插入
        for(int i=size+1;i>index;i--){
            keys[i]=keys[i-1];
            values[i]=values[i-1];
        }
        keys[index]=key;
        values[index]=value;
        size++;

    }

    public Value get(Key key){
        int index=rank(key);//二分查找
        if(keys[index]!=null && key.compareTo(keys[index])==0){
            return values[index];
        }
        return null;
    }
       public int rank(Key key){return rank(key,0,size);}

    public int rank(Key key,int l,int h){
        if(l>h) return l;
        int mid = (l+h)/2;
        int cmp=0;
        if(keys[mid]!=null)
            cmp=key.compareTo(keys[mid]);
        if(cmp<0)
            return rank(key,l,mid-1);
        else if(cmp>0)
            return rank(key,mid+1,h);
        return mid;
    }
}

`二分查找树`

通过前面的两种算法我们可以知道，链表可以快速删除和插入，而二分查找可以快速查找。所以我们想要找到一种既是链式结构又可以进行二分查找同时保证查找和插入效率的结构。

答案是二叉搜索树。

定义

是一棵二叉树
每个节点包含一个键和关联值
并且每个节点的键大于左儿子并小于真实儿子实现u定义，实现已经是清除。说白了，就是从头开始构建一棵二叉树。每次插入都会与树中的节点进行比较。较小的放置在左侧，较大的放置在右侧。像快速排序一样，使用枢轴将左侧和右侧分开。
还是直接看代码比较清楚吧
```
public class BST{

    Node root;

    public void put(Key key,Value value){
        root = put(root,key,value);
    }

    public Node put(Node x, Key key, Value value) {
        if(x==null){
            return new Node(key,value,0);
        }
        int cmp = key.compareTo(x.key);
        if(cmp<0) x.left=put(x.left,key,value);
        else if(cmp>0) x.right=put(x.right,key,value);
        else {
            x.value=value;
            x.N = size(x.right)+size(x.left)+1; 
        }

        return x;
    }

    public Value get(Key key){
        return get(root,key);
    }

    private Value get(Node x, Key key) {
        if(x==null)
            return null;
        int cmp =key.compareTo(x.key);
        if(cmp<0)   return get(x.left,key);
        else if(cmp>0) return get(x.right,key);

        return x.value;
    }
}
```
效率问题
二叉搜索树查找查找的时间复杂度可以达到❀平均，并且可以保证数据一切正常。按照二叉搜索树的顺序遍历就是数据的顺序。我们似乎找到了一个最优算法。
但这种效果只是在一般情况下。如果数据是倒序的，或者是顺序的，那么这棵树就会是一边倒的，复杂度直接达到O(n)，就像选择了一个坏的pivot（最大或者最小）一样在快速排序中。。比快速排序更糟糕的是，使用 快速排序，我们可以通过随机打乱数据来避免这种情况的发生。但是二叉搜索树不起作用。数据由客户提供并直接插入到树中。这种情况其实经常发生。
幸运的是，我们有平衡二叉树来解决这个问题。
平衡二叉树
2-3树
为了保持树的平衡，允许节点存储两个键值对并连接三个儿子。这将节点分为两种类型。
- 2-节点：一个键值对，两个儿子。（即标准的二叉搜索树）
- 3节点：两个键值对，三个儿子。（两个键按顺序，左小右大，左儿子比左键小，右子比右键大，中间子在两个键之间）
实现原理
2-3木插入比较复杂。插入时保持平衡。
- 将密钥插入2 节点。这种情况比较简单。只需插入即可。
- 将钥匙插入3 节点。相当特别。首先，将密钥临时插入3节点。此时这个节点已经有3个key了，那么就将该节点分开。只要将中间的孩子视为根，将左右的钥匙视为儿子即可。如果父节点仍然是3-node ，则继续递归。
性能分析
2-3木性能可以说是比较不错的。不管数据是什么，查找和删除操作的时间复杂度都可以达到O(logn)。
但是2-3树的实现比较复杂，需要检查的情况也很多。剥离节点、转移节点等操作需要非常复杂的代码并且消耗大量时间。所以我们一般不使用原始的2-3树，而是使用变形后的2-3树
❝ ❝ ❝-。黑树
红黑树最方便的是，除了插入和删除操作的代码有点复杂之外，其他操作都可以直接复制二叉搜索树。
红黑树是2-3树的变形，它将3节点❝分成2-❝❝❝ de 。但如何表达不同节点之间的连接呢？我们用共同的线索将它们连接起来。
巧妙地结合了二叉搜索树的高效搜索操作和2-3树的平衡插入操作。
每个节点只有一根线连接到其父节点。这条线的颜色称为节点的颜色。
实现
我们通过转动树来保持树的平衡。一般有两种情况需要轮换。
- 连续两个左侧节点的颜色为红色，向右转
- 右侧节点的颜色为红色，向左转
- 第三种情况是左右两侧都是红色。最好处理，无需旋转。只需将左右儿子的颜色改为黑色，然后将自己的颜色改为黑色即可。可以认为是删除 3 个键值对3 个节点。
```
public class BlackRedBST {
    private final boolean RED = true;
    private final boolean BLACK = false;
    private Node root;
    public void put(Key key,Value value){
        root = put(root,key,value);
        root.color = BLACK;
    }

    private Node put(Node x, Key key, Value value) {
        if(x==null) return new Node(key,value,0,RED);
        int cmp = key.compareTo(x.key);
        if(cmp<0) x.left = put(x.left,key,value);
        else if(cmp>0) x.right = put(x.right,key,value);
        else if(cmp==0) x.value =value;

        if( isRED(x.right) && !isRED(x.left)) x=rotateLeft(x);
        if( isRED(x.left) && isRED(x.left.left)) x=rotateRight(x);
        if( isRED(x.left) && isRED(x.right)) flipColor(x);
        x.N = size(x.right) + size(x.left) +1;
        return  x;
    }

    private void flipColor(Node x) {
        x.right.color = BLACK;
        x.left.color = BLACK;
        x.color = RED;
    }
    private Node rotateLeft(Node x) {
        Node r =x.right;
        x.right = r.left;
        r.left = x;
        r.color = x.color;
        x.color = RED;
        x.N = size(x.left)+size(x.right) +1;
        return r;
    }

    private Node rotateRight(Node x) {
        Node r =x.left;
        x.left = r.right;
        r.right = x;
        r.left.color = RED;
        r.right.color = RED;
        r.color =BLACK;
        x.N = size(x.left)+size(x.right) +1;
        return r;
    }
}
```
性能分析
无论数据如何，插入和删除的时间复杂度都是O(logn)。可以说已经达到了理想的状态，代码也很简单。
性能测试
分别对四个文件执行插入和搜索操作。
- tale.txt(779kb) 顺序搜索（7.143秒）二分搜索（0.46秒）二分搜索树秒。红黑树（0.237秒）红黑树（1.442秒）
- leipzig300k.txt（37966kb）顺序搜索（无）二分搜索 (60.222秒） B♻222 秒 B♻2 秒（2.742 秒）红 - 黑木（3.104 秒）
- leipzig1m.txt（126607kb）序列tial 搜索（无）二进制搜索（无）❝in （3,016秒）红黑树（2,797秒）
从上面的数据分析来看，顺序搜索其实是非常慢的。二分查找对于小数据来说还是比较快的，但是如果数据很大就不行了。
这里的二叉搜索树和红黑树无论数据如何都非常高效。而且，从leipzig300k.txt到leipzig1m.txt的数据几乎翻倍，而这两种算法的效率几乎没有影响。
因为我的数据比较平均，红黑树和二叉搜索树的区别无法比较。我自己构造了一组数据进行测试。以完全相反的顺序插入和删除 100000 数字。
- 红黑树（0.173秒）
- 二叉搜索树（StackOverflow）