トップページ⇒tech
29コメント7KB

探索木

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
探索木の平衡化アルゴリズムについて詳しいサイトありませんか？
特に、STLで使われている赤黒木の情報が欲しいです。
0002デフォルトの名無しさんNGNG
Cﾏｶﾞ OCT.2000見れ
0003デフォルトの名無しさんNGNG
持ってません。>2
0004デフォルトの名無しさんNGNG
バックナンバーを取り寄せろ。
0005デフォルトの名無しさんNGNG
ttp://www3.freeweb.ne.jp/misc/niin/
0006デフォルトの名無しさんNGNG
あ、そっか。(笑)>4
明日本屋に行って来ます。
で、何が載ってるんですか？
0007デフォルトの名無しさんNGNG
なんなんですか？ここ。>5
XTCとか書いてあるけど。ひょっとして全く関係ない？
0008デフォルトの名無しさんNGNG
それと、赤黒木やAVL木の他に、有効な平衡探索木があれば教えてください。
0009デフォルトの名無しさんNGNG
俺も知りたいage
STLのRedBlackTreeははっきり言ってヌルイけど。
0010デフォルトの名無しさんNGNG
ageだろ？
0011デフォルトの名無しさんNGNG
Binary Treeは日本語でなんて言うの？
二進法木？

0012デフォルトの名無しさんNGNG
二分木じゃねーの?
0013デフォルトの名無しさんNGNG
>8
おれはあんまり理解してないけど授業で習ったのはその他に
B木、B+木＠｀2-3木とかがあった。
0014奥さん、名無しですNGNG
B木、B+木、B-木、B*木というのがあるが。
因みにこれはBinaryTreeとは関係ないよ。
0015名無しさん＠お腹いっぱい。NGNG
>2
Ｃマガ２０００・１０に赤黒木のってます？
ページを教えて下さい。
00161NGNG
>15
中途半端にしか載ってなかった様な。P.J.プラウガーの翻訳記事です。
STLの実装だから、読みにくいです。
0017 NGNG
00181NGNG
？下げたいだけ？>17
0019１５NGNG
>1
どうもです。今から見てみますね。
00201NGNG
B木も記憶領域に余裕があるなら結構良さそうですね。
00211NGNG
このまま下がっていくのは寂しいので、一応アルゴリズム毎の測定をやってみました。

・テスト環境
Pen133mhz (32M)
Windows98
VisualC++6.0SP4

・テスト項目
10万件のランダム(同値なし)数値データ(データ長:sizeof(int))
を挿入(リストはその後整列)、全体をトラバース、破壊するまで。

※速度は５回の平均を取りました。
※各プログラムはわたしが適当に組んだものです。
（バグが残ってるかもしれません。）
※今の所、B木は葉の配列を線形になめているので、２分探索に変えればもっと効率
が良くなると思います。
00221NGNG
・テスト結果
(速度順)
----------------------------------------------------
リスト＋C標準ライブラリのqsort
速度 4450 msec
比較回数 2205642
最大メモリ占有量(データ含む) 1815113 bytes
----------------------------------------------------
B木(1ノードに配置する葉の数:4-8)
速度 4610 msec
比較回数 2005995
最大メモリ占有量(データ含む) 1934469 bytes
----------------------------------------------------
赤黒木(left＠｀right)
速度 5440 msec
比較回数 1665535
最大メモリ占有量(データ含む) 2615113 bytes
----------------------------------------------------
AVL木(left＠｀right)
速度 5490 msec
比較回数 1559946
最大メモリ占有量(データ含む) 2215113 bytes
----------------------------------------------------
00231NGNG
・総評
リストですが、単純な分これがやっぱり速いみたいです。
一度ソートしてしまえば、データの探索や追加も２分探索で行なえますし。
しかし恐らく、データが大量になるに従って、クイックソートは不利になって行くでしょう。
残念なのが、平衡木の速度が思ったより良くなかった点です。
木の入れ替え作業が思ったよりオーバーヘッドになっている様です。
もっとチューニングすれば速くなるかな？
複雑な分、扱いにくそうです。
あと、B木は意外にもメモリ消費量が少なく済む事がわかりました。
構造も単純だし、結構使いやすそうです。
数値データの比較だけしかやってないので、他のデータだとまた違った結果がでるかもしれません。
10万件じゃ足りなかったかも。
あ、交換回数計ってなかった・・・。
0024デフォルトの名無しさんNGNG
B木はページあたりのデータ数によってデータ領域のサイズと
速度のトレードオフになるのでためしてみるといいよん。
AVL木はB木のバイナリバージョンってかんじかなぁ。
100万〜10億あたりでネットワーク経由のデータベースを
組んでみると qsort との違いがわかってきます。
00251NGNG
B木の葉の線形探索を2分探索に変更したら予想通り比較回数が減りました。
時間が無くてちゃんと測定してませんが、大体22のテストのAVL木の1559946回付近に収まっています。
速度も多少上がって、現在はリスト＋qsortと同等ぐらいです。
リストにuniqも含める条件だと逆転します。
比較にコストがかかるデータなら恐らく最速でしょう。(レス22の中では(笑))
あとは危険な再帰呼出しをなんとかすれば実用になりそうです。
(B木はそれでも他の木に比べると、圧倒的に再帰呼出しは少ない(1/10以下)ですが。)
00261NGNG
問題は、赤黒木、AVL木、単純な2分探索木共に、データの数／２回の再帰呼出しをトラバース時にしてしまう事です。(例えば10万件をトラバースするとバランスが取れていれも約50000回再帰呼出しを行なう)
独自にスタックを管理すれば良いんだけど、工数がかなりかかってしまいそう…
挿入や、探索はほぼゼロなので良いんですが。
00271NGNG
あ、再帰が５万回は数え間違えでした。（笑）
00281NGNG
大体5000回程度です。(それでも多いけど)
00291NGNG
違う、また間違えました。これで最後

・１０万件データのトラバースに必要だった再帰呼出し回数
B木　　　　　実測4回
赤黒木　　　実測19回
AVL木　　　実測21回
単純２分木　実測26回(最悪10万回)
■ このスレッドは過去ログ倉庫に格納されています