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索引背后的数据结构及算法    (阅读：9861)
2. Java heap dump触发和分析    (阅读：6577)
3. 数据结构定义中的中(大陆地区)美差异    (阅读：5619)
4. 爱喝啤酒的程序员是如何学习数据结构的    (阅读：5041)
5. 分布式系统的数据结构    (阅读：4937)
6. stream.js ：一个新的JavaScript数据结构    (阅读：4076)
7. 数据映射–平衡二叉有序树    (阅读：3409)
8. 二叉树迭代器算法    (阅读：3176)
9. STL笔记之二叉查找树    (阅读：3029)
10. 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList    (阅读：2883)