翻訳と辞書
Words near each other
・ tread rubber
・ tread water
・ tread water lift wheel
・ treading
・ treading barley plants
・ treading wheat plants
・ treadle
・ treadle water wheel
・ treadmill
・ treadmill test
・ Treap
・ treason
・ treasonable
・ treasonous
・ TREASURE
・ Treasure
・ treasure
・ TREASURE BOX
・ Treasure Box Vol.1
・ TREASURE COLLECTION


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Treap : ウィキペディア日本語版
Treap[つりーぷ]
Treap (ツリープ)は、乱択アルゴリズムを使用した平衡2分探索木の1つ。1989年に Cecilia R. Aragon と Raimund Seidel が発表した〔
〕〔
〕。平衡2分探索木のアルゴリズムの中ではアルゴリズムが単純であり、コード量が少なくてすむ。Treap という名称は Tree (木構造)と Heap (ヒープ)という2つの単語を組み合わせて作られた。
==アルゴリズム==
各ノードに乱数を割り振る。そして、この乱数値に基づいて、二分ヒープを作る。二分ヒープにおいて、子の左右は無規定だが、この部分を2分探索木のルールに基づき、(乱数値の方ではなく、本来のノードの値に基づき)左の子ノードは親ノードよりも小さくし、右の子ノードは親ノードよりも大きくする。乱数で作られた2分ヒープの高さは、O(log n) であるため、treap の木の高さは O(log n) になる。
より具体的には、挿入時は、乱数値を無視して、2分木として適切な葉に追加し、そこから、木の回転を使い、2分ヒープが成立するように、親方向へノードを上げていく。削除時は、木の回転を使い、葉まで降ろし、そして削除する。探索などは、通常の2分探索木と同一。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Treap」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.