CWYAlpha

Just another WordPress.com site

Thought this was cool: treap

leave a comment »


treap 是一个很有意思的数据结构,从名字也能看得出来,它是 tree 和 heap 的混合产物。为什么会有这么一个数据结构还得从二叉树(BST)说起。

我们都知道,普通的二叉树是不平衡的,在某些情况下进行插入删除操作可以导致时间复杂度从 O(logN) 下降到 O(N)。为了解决平衡的问题,有很多新的二叉树被引入,比如大家熟知的一些:Linux 内核中 CFS 使用到的红黑树(Red-black tree),数据结构课上都会讲到的 AVL 树。这些树都因为要进行复杂的旋转操作而不容易实现。

那么有没有一个实现容易的平衡二叉树呢?Treap 就是一个。普通的二叉树节点只有 key,而 treap 又多了一个 priority,这里的 priority 就是 heap (优先队列)中的 priority。这样, treap 既可以利用二叉树的特性,又可以利用 heap 的特性了。

看它是怎么利用的,以 Perl 的 Tree::Treap 模块为例。

1) 对于搜索,使用二叉树的 key 即可,和普通二叉树没有区别:

PLAIN TEXT
PERL:

  1. sub _get_node {
  2.     my $self = shift;
  3.     my $key  = shift;
  4.     while(!$self->_is_empty() and $self->ne($key)){
  5.         $self = $self->{$self->lt($key)?“left”:“right”}
  6.     }
  7.     return $self->_is_empty() ? 0 : $self;
  8. }

2) 插入一个新的节点 key=x 时,随机一个整数值 y 作为 priority,利用二叉树搜索 x,在它应该出现的位置创建一个新的节点,只要 x 不是根节点而且优先级高于它的父节点,那么旋转这个节点使其和其父节点交换位置。

PLAIN TEXT
PERL:

  1. sub insert {
  2.     my $self = shift;
  3.     my $key  = shift;
  4.     my $data = shift;
  5.     $data = defined($data)? $data : $key;
  6.     my $priority = shift() || rand();
  7.    
  8.     if($self->_is_empty()) {
  9.         $self->{priority} = $priority,
  10.         $self->{key}      = $key;
  11.         $self->{data}     = $data;
  12.         $self->{left}     = $self->new($self->{cmp});
  13.         $self->{right}    = $self->new($self->{cmp});
  14.         return $self;
  15.     }
  16.    
  17.     if($self->gt($key)){
  18.         $self->{right}->insert($key,$data,$priority);
  19.         if($self->{right}->{priority}> $self->{priority}){
  20.             $self->_rotate_left();
  21.         }
  22.     }elsif($self->lt($key)){
  23.         $self->{left}->insert($key,$data,$priority);
  24.         if($self->{left}->{priority}> $self->{priority}){
  25.             $self->_rotate_right();
  26.         }
  27.  
  28.     }else{
  29.         $self->_delete_node();
  30.         $self->insert($key,$data,$priority);
  31.     }
  32.     return $self;
  33. }

从代码可以看出,旋转就是为了保持 heap 的属性,优先级高的节点在上层。

3) 删除一个节点相对比较麻烦:如果要删除的节点 x 是一个叶子,直接删掉即可;如果 x 有一个孩子节点 z,把 x 删掉,然后把 z 作为 x 父亲的孩子;如果 x 有两个孩子节点,则把 x 和它的下一个节点(successor)交换,然后进行相应的旋转。实现是递归实现的,很容易理解。注意:这里实现删除时并没有进行实质的删除操作,而只是把优先级设为了最低的 -100,这也使得代码变得比上面的理论更简单。

PLAIN TEXT
PERL:

  1. sub delete {
  2.     my $self = shift;
  3.     my $key  = shift;
  4.     return 0 unless $self = $self->_get_node($key);
  5.     $self->_delete_node();
  6. }
  7.  
  8.  
  9. sub _delete_node {
  10.     my $self = shift;
  11.     if($self->_is_leaf()) {
  12.         %$self = (priority => -100, cmp => $self->{cmp});
  13.     } elsif ($self->{left}->{priority}> $self->{right}->{priority}) {
  14.         $self->_rotate_right();
  15.         $self->{right}->_delete_node();
  16.     } else {
  17.         $self->_rotate_left();
  18.         $self->{left}->_delete_node();
  19.     }
  20. }

这里的两个旋转操作很容易实现:

PLAIN TEXT
PERL:

  1. sub _clone_node  {
  2.     my $self  = shift;
  3.     my $other = shift;
  4.     %$self = %$other;
  5. }
  6.  
  7. sub _rotate_left {
  8.     my $self = shift;
  9.     my $tmp = $self->new($self->{cmp});
  10.     $tmp->_clone_node($self);
  11.     $self->_clone_node($self->{right});
  12.     $tmp->{right} = $self->{left};
  13.     $self->{left} = $tmp;
  14.    
  15. }
  16.  
  17. sub _rotate_right {
  18.     my $self = shift;
  19.     my $tmp = $self->new($self->{cmp});
  20.     $tmp->_clone_node($self);
  21.     $self->_clone_node($self->{left});
  22.     $tmp->{left} = $self->{right};
  23.     $self->{right} = $tmp;
  24. }

或者借助于这个图来理解右旋:

      B            A
     / \          / \
    A   2   -->  0   B
   / \              / \
  0   1            1   2

参考:
1. http://acs.lbl.gov/~aragon/treaps.html
2. http://www.perlmonks.org/?node_id=289584
3. C 语言实现:http://www.canonware.com/trp/
4. Python 实现:http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

from A Geek's Page: http://wangcong.org/blog/archives/2036

Written by cwyalpha

七月 14, 2012 在 3:08 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: