本條目存在以下問題 ,請協助
改善本條目 或在
討論頁 針對議題發表看法。
此條目需要
精通或熟悉相关主题的编者 参与及协助编辑。
(2020年7月18日 ) 請邀請 適合的人士改善本条目 。更多的細節與詳情請參见討論頁 。
树堆 类型 隨機二元搜索樹 算法
平均
最差 空间
O
(
n
)
{\displaystyle O(n)}
O
(
n
)
{\displaystyle O(n)}
搜索
O
(
log
-->
n
)
{\displaystyle O(\log n)}
O
(
n
)
{\displaystyle O(n)}
插入
O
(
log
-->
n
)
{\displaystyle O(\log n)}
O
(
n
)
{\displaystyle O(n)}
删除
O
(
log
-->
n
)
{\displaystyle O(\log n)}
O
(
n
)
{\displaystyle O(n)}
三層的樹堆
樹堆 (英語:Treap ),是計算機科學中術語。是有一个随机附加域满足堆 的性质的二叉搜索树 ,其結構相当于以随机數據插入的二叉搜索树 。其基本操作的期望時間複雜度 为
O
(
log
-->
n
)
{\displaystyle O(\log {n})}
。相對於其他的平衡二叉搜索樹 ,Treap的特点是實現簡單,且能基本實現隨機平衡的結構。属于弱平衡树。
介绍
Treap一词由Tree 和Heap 二词合成而来。其本身是一棵二叉搜索树 ,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树 不同的是,Treap为每个节点记录优先级。Treap在以关键码构成二叉搜索树 的同时,其节点优先级还满足堆 的性质。Treap维护堆性质的方法用到了旋转,且只需要进行两种旋转操作,因此编程复杂度较Splay 要小一些。
插入
给节点随机分配一个优先级,先和二叉搜索树 的插入一样,先把要插入的点插入到一个叶子上,然后跟维护堆一样進行以下操作:
如果当前节点的优先级比父節點大就進行2. 或3. 的操作
如果当前节点是父節點的左子葉就右旋
如果当前节点是父節點的右子葉就左旋。
由于旋转是
O
(
1
)
{\displaystyle O(1)}
的,最多进行h次(h是树的高度),插入的复杂度是
O
(
h
)
{\displaystyle O(h)}
的,在期望情况下
h
=
O
(
log
-->
n
)
{\displaystyle h=O(\log {n})}
,所以它的期望复杂度是
O
(
log
-->
n
)
{\displaystyle O(\log {n})}
。
删除
因为Treap满足堆性质,所以只需要把要删除的节点旋转到叶节点上,然后直接删除就可以了。具体的方法就是每次找到优先级最大的子葉,向与其相反的方向旋转,直到那个节点被旋转到了叶节点,然后直接删除。
删除最多进行
O
(
h
)
{\displaystyle O(h)}
次旋转,期望复杂度是
O
(
log
-->
n
)
{\displaystyle O(\log {n})}
。
查找
和一般的二叉搜索树 一样,但是由于Treap的随机化结构,Treap中查找的期望复杂度是
O
(
log
-->
n
)
{\displaystyle O(\log {n})}
。
算法分析
二叉搜索树 有一个特性,就是每个子树的形态在优先级唯一确定的情况下都是唯一的,不受其他因素影响,也就是说,左子树的形态与树中大于根节点的值无关,右子树亦然。这是因为Treap满足堆的性质,Treap的根节点是优先级最大的那个节点,考虑它的左子树,树根也是子树里面最大的一点,右子树亦然。所以Treap相当于先把所有节点按照优先级排序,然后插入,实质上就相当于以随机顺序建立的二叉搜索树 ,只不过它并不需要一次读入所有数据,可以一个一个地插入。而当这个随机顺序确定的时候,这个树是唯一的。因此在给定优先级的情况下,只要是用符合要求的操作,通过任何方式得出的Treap都是一样的,所以不改变优先级的情况下,特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。
Treap的其它操作的期望复杂度同样是
O
(
log
-->
n
)
{\displaystyle O(\log {n})}
。
参考程序
Pascal版本
(*
Project: Amber Standard Sources Library [ASSL]
Author: Amber
Title: Treap
Category: Data Structure
Version: v1.0
Remark: XXXXXXXX
Tested Problems: N/A
Date: 2006-11-16
*)
program ASSL_Treap ( Input , Output ) ;
const
Infinity = 65535 ;
type
TIndex = Longint ;
TKey = Longint ;
TPriority = Word ;
PTreapNode = ^ TTreapNode ;
TTreapNode = record
Left , Right : PTreapNode ;
Priority : TPriority ;
Key : TKey ;
end ;
var
NullNode : PTreapNode ;
procedure Initalize ;
begin
if NullNode = nil then
begin
New ( NullNode ) ;
NullNode ^. Left := NullNode ;
NullNode ^. Right := NullNode ;
NullNode ^. Priority := Infinity ;
end ;
end ;
function FindMax ( T : PTreapNode ) : PTreapNode ;
begin
if T <> NullNode then
while T ^. Right <> NullNode do
T := T ^. Right ;
Result := T ;
end ;
function FindMin ( T : PTreapNode ) : PTreapNode ;
begin
if T <> NullNode then
while T ^. Left <> NullNode do
T := T ^. Left ;
Result := T ;
end ;
function Find ( T : PTreapNode ; Key : TKey ) : PTreapNode ;
begin
while T <> NullNode do
if Key < T ^. Key then
T := T ^. Left
else if Key > T ^. Key then
T := T ^. Right
else
Break ;
Result := T ;
end ;
function LeftRotate ( T : PTreapNode ) : PTreapNode ;
begin
Result := T ^. Left ;
T ^. Left := Result ^. Right ;
Result ^. Right := T ;
end ;
function RightRotate ( T : PTreapNode ) : PTreapNode ;
begin
Result := T ^. Right ;
T ^. Right := Result ^. Left ;
Result ^. Left := T ;
end ;
function InsertNode ( Key : TKey ; T : PTreapNode ) : PTreapNode ;
begin
if T = NullNode then
begin
New ( T ) ;
T ^. Left := NullNode ;
T ^. Right := NullNode ;
T ^. Key := Key ;
T ^. Priority := Random ( 65535 ) ;
end
else if Key < T ^. Key then
begin
T ^. Left := InsertNode ( Key , T ^. Left ) ;
if T ^. Left ^. Priority < T ^. Priority then
T := LeftRotate ( T ) ;
end
else if Key > T ^. Key then
begin
T ^. Right := InsertNode ( Key , T ^. Right ) ;
if T ^. Right ^. Priority < T ^. Priority then
T := RightRotate ( T ) ;
end ;
Result := T ;
end ;
function DeleteNode ( Key : TKey ; T : PTreapNode ) : PTreapNode ;
begin
if T <> NullNode then
if Key < T ^. Key then
T ^. Left := DeleteNode ( Key , T ^. Left )
else if Key > T ^. Key then
T ^. Right := DeleteNode ( Key , T ^. Right )
else
begin
if T ^. Left ^. Priority < T ^. Right ^. Priority then
T := LeftRotate ( T )
else
T := RightRotate ( T ) ;
if T <> NullNode then
T := DeleteNode ( Key , T )
else //RightRotate
begin
Dispose ( T ^. Left ) ;
T ^. Left := NullNode ;
end ;
end ;
Result := T ;
end ;
procedure Main ;
begin
Initalize ;
end ;
begin
Main ;
end ;
C++版本
#include <iostream>
#include <ctime>
#include <cstdlib>
#define MAX 100
using namespace std ;
typedef struct
{
int l , r , key , fix ;
} node ;
class treap
{
public :
node p [ MAX ];
int size , root ;
treap ()
{
srand ( time ( 0 ));
size = -1 ;
root = -1 ;
}
void rot_l ( int & x )
{
int y = p [ x ]. r ;
p [ x ]. r = p [ y ]. l ;
p [ y ]. l = x ;
x = y ;
}
void rot_r ( int & x )
{
int y = p [ x ]. l ;
p [ x ]. l = p [ y ]. r ;
p [ y ]. r = x ;
x = y ;
}
void insert ( int & k , int tkey )
{
if ( k == -1 )
{
k =++ size ;
p [ k ]. l = p [ k ]. r = -1 ;
p [ k ]. key = tkey ;
p [ k ]. fix = rand ();
}
else if ( tkey < p [ k ]. key )
{
insert ( p [ k ]. l , tkey );
if ( p [ p [ k ]. l ]. fix > p [ k ]. fix )
rot_r ( k );
}
else
{
insert ( p [ k ]. r , tkey );
if ( p [ p [ k ]. r ]. fix > p [ k ]. fix )
rot_l ( k );
}
}
void remove ( int & k , int tkey )
{
if ( k == -1 ) return ;
if ( tkey < p [ k ]. key )
remove ( p [ k ]. l , tkey );
else if ( tkey > p [ k ]. key )
remove ( p [ k ]. r , tkey );
else
{
if ( p [ k ]. l == -1 && p [ k ]. r == -1 )
k = -1 ;
else if ( p [ k ]. l == -1 )
k = p [ k ]. r ;
else if ( p [ k ]. r == -1 )
k = p [ k ]. l ;
else if ( p [ p [ k ]. l ]. fix < p [ p [ k ]. r ]. fix )
{
rot_l ( k );
remove ( p [ k ]. l , tkey );
}
else
{
rot_r ( k );
remove ( p [ k ]. r , tkey );
}
}
}
void print ( int k )
{
if ( k == -1 ) return ;
if ( p [ k ]. l != -1 )
print ( p [ k ]. l );
cout << p [ k ]. key << " : " << p [ k ]. fix << endl ;
if ( p [ k ]. r != -1 )
print ( p [ k ]. r );
}
};
treap T ;
int main ( void )
{
int i ;
for ( i = 3 ; i >= 1 ; i -- )
T . insert ( T . root , i );
T . print ( T . root );
for ( i = 3 ; i >= 1 ; i -- )
{
cout << endl ;
T . remove ( T . root , i );
T . print ( T . root );
}
return 0 ;
}
与其他结构的比较
外部链接