# 查找算法之顺序、二分、二叉搜索树、红黑树 详细比较总结

## 顺序查找

`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;    }}`

## 二分查找

`public class BinarySearch<Key extends Comparable,Value> {    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;    }}`

## `二叉搜索树`

### 定义

• 是二叉树
• 每个节点含有一个键和关联的值
• 且每个节点的键大于左儿子且小于右儿子

### 实现

`public class BST<Key extends Comparable,Value>{    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(logn)` ，而且能保证数据有序。 `二叉搜索树` 的中序遍历就是数据的顺序。我们貌似已经找到了一个最理想的算法。

## `平衡二叉树`

### `2-3树`

• `2-节点` : 一个键值对，两个儿子。 (也就是标准的 `二叉搜索树` )
• `3-节点` : 两个键值对，三个儿子。 (两个键是有序的，左小右大。左儿子小于左边的键，右儿子大于右边的键，中间的儿子在两个键之间)

#### 实现原理

`2-3树` 插入比较复杂。在插入的同时保持平衡性。

• `2-节点` 中插入键。这种情况比较简单。直接插入即可。
• `3-节点` 中插入键。比较特殊。先暂时把键插入到 `3-节点` ，此时这个节点中就有了三个键，然后再把这个节点分开。把中间的儿子简单当根，左右两边的键当儿子。若父节点还是 `3-节点` ，则继续递归进行。

#### 性能分析

`2-3树` 性能可以说是比较好的。不管数据怎么样，查找删除操作时间复杂度都能达到O(logn)。

### `红黑树`

`红黑树` 最方便的地方除了插入和删除操作的代码略复杂以外，另外的操作都可以直接复制 `二叉搜索树`

`红黑树``2-3树` 的变形，把 `3-节点` 分离开来使之成为普通的 `2-节点` 。但是怎么表现分离开的节点之间的联系呢。我们用红线把他们连起来。

#### 实现

• 连续两个左节点的颜色为红色,向右转
• 右节点的颜色为红色，向左转
• 第三种情况是左右两边都为红色。最好处理，不需要旋转。只需要把左右两个儿子的颜色改成黑色，再把自己的颜色改成黑色。可以想象成把3个键值对 `3-节点` 剥离开。

`public class BlackRedBST<Key extends Comparable,Value> {    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;    }}`

## 性能测试

• `tale.txt` (779kb)
顺序查找(7.143秒) 二分查找(0.46秒) `二叉搜索树` (0.191秒) `红黑树` (0.237秒)
• `leipzig100k.txt` (12670kb)
顺序查找(无) 二分查找(13.911秒) `二叉搜索树` (1.389秒) `红黑树` (1.442秒)
• `leipzig300k.txt` (37966kb)
顺序查找(无) 二分查找(60.222秒) `二叉搜索树` (2.742秒) `红黑树` (3.104秒)
• `leipzig1m.txt` (126607kb)
顺序查找(无) 二分查找(无) `二叉搜索树` (3.016秒) `红黑树` (2.797秒)

• 红黑树(0.173秒)
• 二叉搜索树(StackOverflow)