Red Black Tree 対決

Program DKUT

Powered by dKingyo Rails | ソフトウェア開発技術者 | GPU Gems | 画像処理 | C言語

某氏が公開していたRed Black Treeの実装と既存のRed Black Treeの実装を対戦させてみた。
インクリメントキー



1	/ Challenger red black tree delete	/ 2035

2	/ red black tree insert	/ 54441

3	/ STLport red black tree delete	/ 78082

4	/ Challenger red black tree insert	/ 101272

5	/ STLport red black tree insert	/ 140324

6	/ red black tree delete	/ 181662
ランダムキー


1	/ Challenger red black tree delete	/ 5127

2	/ red black tree delete	/ 18825

3	/ red black tree insert	/ 96301

4	/ Challenger red black tree insert	/ 108134

5	/ STLport red black tree insert	/ 118734

6	/ STLport red black tree delete	/ 188965
deleteが異様に早い。
某氏のソースコードを見てみたが、理解するには１日つぶしそうだ･･･。



さて、このテストをやっていて気付いた。
dkutil_cのred black treeがランダムな要素をキーとしdeleteする時に内部に格納していたデータが入れたデータと違っているという現象が発生したのだ。これは忌々しき事態だ。
dkutil_cはかなりバグチェックは行っているはずなのだが･･･
要素を二重削除していたのでバグっていました。dkutil_cのミスではなく完全にプログラミングしている私のミスでした。