Contents

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

[perl]
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;
}
[/perl]

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

[perl]
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;

}
[/perl]

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

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

[perl]
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();
}
}
[/perl]

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

[perl]
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;
}
[/perl]

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

      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/

Contents