数据结构之treap
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/
建议继续学习:
- 浅谈MySQL索引背后的数据结构及算法 (阅读:9962)
- Java heap dump触发和分析 (阅读:6713)
- 数据结构定义中的中(大陆地区)美差异 (阅读:5694)
- 爱喝啤酒的程序员是如何学习数据结构的 (阅读:5185)
- 分布式系统的数据结构 (阅读:5021)
- stream.js :一个新的JavaScript数据结构 (阅读:4101)
- 数据映射–平衡二叉有序树 (阅读:3504)
- 二叉树迭代器算法 (阅读:3245)
- STL笔记之二叉查找树 (阅读:3116)
- 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList (阅读:2958)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:王 聪 来源: A Geek's Page
- 标签: tree heap treap 二叉树 数据结构
- 发布时间:2012-09-18 23:32:04
- [70] Twitter/微博客的学习摘要
- [65] find命令的一点注意事项
- [64] 如何拿下简短的域名
- [64] IOS安全–浅谈关于IOS加固的几种方法
- [63] android 开发入门
- [62] 流程管理与用户研究
- [62] Go Reflect 性能
- [60] Oracle MTS模式下 进程地址与会话信
- [59] 读书笔记-壹百度:百度十年千倍的29条法则
- [59] 图书馆的世界纪录