技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 数据结构之treap

数据结构之treap

浏览:2688次  出处信息

    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 即可,和普通二叉树没有区别:

sub _get_node {
 my $self = shift;
 my $key  = shift;
 while(!$self->_is_empty() and $self->ne($key)){
  $self = $self->{$self->lt($key)?"left":"right"}
 }
 return $self->_is_empty() ? 0 : $self;
}

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

sub insert {
 my $self = shift;
 my $key  = shift;
 my $data = shift;
 $data = defined($data)? $data : $key;
 my $priority = shift() || rand();
 if($self->_is_empty()) {
  $self->{priority} = $priority,
  $self->{key}   = $key;
  $self->{data}  = $data;
  $self->{left}  = $self->new($self->{cmp});
  $self->{right} = $self->new($self->{cmp});
  return $self;
 }
 if($self->gt($key)){
  $self->{right}->insert($key,$data,$priority);
  if($self->{right}->{priority}> $self->{priority}){
   $self->_rotate_left();
  }
 }elsif($self->lt($key)){
  $self->{left}->insert($key,$data,$priority);
  if($self->{left}->{priority}> $self->{priority}){
   $self->_rotate_right();
  }
 }else{
  $self->_delete_node();
  $self->insert($key,$data,$priority);
 }
 return $self;
}

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

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

sub delete {
 my $self = shift;
 my $key  = shift;
 return 0 unless $self = $self->_get_node($key);
 $self->_delete_node();
}
sub _delete_node {
 my $self = shift;
 if($self->_is_leaf()) {
  %$self = (priority => -100, cmp => $self->{cmp});
 } elsif ($self->{left}->{priority}> $self->{right}->{priority}) {
  $self->_rotate_right();
  $self->{right}->_delete_node();
 } else {
  $self->_rotate_left();
  $self->{left}->_delete_node();
 }
}

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

sub _clone_node  {
 my $self  = shift;
 my $other = shift;
 %$self = %$other;
}
sub _rotate_left {
 my $self = shift;
 my $tmp = $self->new($self->{cmp});
 $tmp->_clone_node($self);
 $self->_clone_node($self->{right});
 $tmp->{right} = $self->{left};
 $self->{left} = $tmp;
}
sub _rotate_right {
 my $self = shift;
 my $tmp = $self->new($self->{cmp});
 $tmp->_clone_node($self);
 $self->_clone_node($self->{left});
 $tmp->{left} = $self->{right};
 $self->{right} = $tmp;
}

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

      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/

建议继续学习:

  1. 浅谈MySQL索引背后的数据结构及算法    (阅读:9886)
  2. Java heap dump触发和分析    (阅读:6616)
  3. 数据结构定义中的中(大陆地区)美差异    (阅读:5640)
  4. 爱喝啤酒的程序员是如何学习数据结构的    (阅读:5070)
  5. 分布式系统的数据结构    (阅读:4956)
  6. stream.js :一个新的JavaScript数据结构    (阅读:4082)
  7. 数据映射–平衡二叉有序树    (阅读:3434)
  8. 二叉树迭代器算法    (阅读:3190)
  9. STL笔记之二叉查找树    (阅读:3053)
  10. 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList    (阅读:2901)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1