神刀安全网

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

前言

一般用 符号表 来储存键值对,就好像字典那样,通过索引来查找值,若键重复则覆盖值。我们能希望找到一种高效的查找算法使在平均情况和最差情况下,时间复杂度都能达到 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;

}
}

二分查找

用数组保存数据,保证有序。二分查找速度很快,但是仅限于查找。因为插入的时候要保证有序,所以要往后移动数据以便插入。查找复杂度 O(logn) ,插入复杂度 O(n)

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

但是这个效率只是在平均情况下。如果数据是逆序,或者顺序,那么这棵树就会发生一边倒的情况使复杂度直接达到 O(n) ,就如同快排中选择到糟糕的主元(最大或者最小)。比快排糟糕的是, 快排 我们能通过随机打乱数据来避免这种情况发生。但 二叉搜索树 则不行,数据都是客户提供,直接插入到树中的,这种情况其实经常发生。

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

幸运的是我们有 平衡二叉树 可以解决这个问题。

平衡二叉树

2-3树

为了保持树平衡性,允许节点能保存两个键值对,且能连三个儿子。这样把节点分成了两种类型。

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

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

实现原理

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

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

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

性能分析

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

但是 2-3树 实现比较复杂,需要掌控的情况很多,剥离节点,传递节点等操作,都需要很复杂的代码,且也会耗费不少的时间。所以我们一般不怎么用原始的 2-3树 ,而是用 2-3树 的变形 红黑树 .

红黑树

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

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

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

巧妙地结合 二叉搜索树 的高效查找操作和 2-3树 的平衡插入操作。

每个节点都只有一根连向父节点的线。这个线的颜色称为节点的颜色。

实现

我们通过旋转来维持树的平衡。一般有两种情况需要旋转。

  • 连续两个左节点的颜色为红色,向右转
  • 右节点的颜色为红色,向左转
  • 第三种情况是左右两边都为红色。最好处理,不需要旋转。只需要把左右两个儿子的颜色改成黑色,再把自己的颜色改成黑色。可以想象成把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;
}
}

性能分析

无论数据如何,插入删除时间复杂度都为 O(logn) ,可以说达到了理想状态,且代码简单。

性能测试

分别对四个文件进行插入搜索操作。

  • 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秒)

由上面的数据分析,顺序查找实际是非常慢的。而二分查找对小型数据还是比较快,但是数据一大就不行了。

而这里的 二叉搜索树红黑树 ,无论什么数据效率都是极高。而且由 leipzig300k.txtleipzig1m.txt 数据几乎翻了4倍,而这两种算法的效率几乎没收什么影响。

这里因为我的数据比较平均的关系,比较不出红黑树和二叉搜索树的差异。我自己构造了一组数据进行测试。完全逆序的 100000 个数进行插入删除。

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

Summary

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

Reference

维基百科

算法 4th

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 查找算法之顺序、二分、二叉搜索树、红黑树 详细比较总结

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮