わかってうれＣ〜コンピュータ　第９回〜乱数から作られた二分探索木の処理回数はどれくらい？
日経ソフトウェア　第172号　2012.3.1

この記事の情報
掲載誌	日経ソフトウェア　第172号（2012.3.1）
ページ数	4ページ　（全2995字）
形式	PDFファイル形式　（362kb）
雑誌掲載位置	138〜141ページ目

第９回　前回の探索アルゴリズムの処理回数に続いて、今回は二分探索木の処理回数がテーマです。左右にバランスよく枝が伸びた理想的な形状の二分探索木であれば、データ数ｎ個における最大処理回数は、およそｌｏｇ２ｎ回になります。しかし現実的には、それほどバランスのよい二分探索木にはならないでしょうから、処理回数もｌｏｇ２ｎとは異なるはずです。果たして、どれくらい違う値になるのか。Ｃ言語で実験プログラムを作っ…