このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

  • 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#a1d6798e]

#contents


*2分探索木 [#c0fc4525]

 ''2分探索木''とは[[リスト]]をさらに工夫して、配列に要素を追加するときにその大小関係を考慮しつつ左右2つの方向に分岐するリストとしたものである。実際のメモリが2方向に分かれるわけではなく、プログラムによって論理的に実現される。
 ''2分探索木(binary search tree)''とは、2分木の節点にそれぞれデータが格納されていて、どの節点を取っても次の規則が成り立つものである。

-(節点のデータ)<(右部分木のすべてのデータ)
-(左部分木のすべてのデータ)<(節点のデータ)

#img(http://security2600.sakura.ne.jp/main2/image2/2tree.jpg)
#img(,clear)


*2分探索木とデータ構造 [#wc6e24de]

 2分探索木では、根のデータから比較を始めて、目的のデータが左右どちらかにあるかを判定し、左右に分岐していく。つまり、[[リスト]]をさらに工夫して、配列に要素を追加するときにその大小関係を考慮しつつ左右2つの方向に分岐するリストとしたものとなるわけである。しかし、木で表現されているのはあくまで概念であり、コンピュータ上では実際のメモリが2方向に分かれるわけではなく、プログラムによって論理的に実現される。

 2分探索木を実現するためには、配列の個々の要素にデータと2つのインデックス情報を付加すればよい。


*特徴 [#ha3e81be]

-[[リスト]]を発展させたものなので、もちろん要素の追加や削除は効率的に行える。
-リストを発展させたものなので、もちろん要素の追加や削除は効率的に行える。
-データの検索が効率的。単なる配列を使った場合には、配列の先頭からインデックスの順に要素を参照して目的のデータを見つけなければならない。それに対して2分探索木なら目的のデータが現在読み出しているデータより小さければリストの左側、大きければリストの右側を辿ればよいので、目的のデータをより早く発見できる。


*2分探索木における計算量 [#d55bafed]

 理想的な完全2分探索木の形をした2分探索木では、データの個数がn個のとき、&mimetex("\log_2 n");回の比較で葉に達する。よって、探索に要する計算量は最善の場合で&mimetex("O ( \log_2 n)");である。

 また、最悪の場合は、次のような2分探索木の場合である。

#img(http://security2600.sakura.ne.jp/main2/image2/2tree2.jpg)
#img(,clear)

 これはデータの大きさの順にデータをした場合に発生するが、計算量は&mimetex("O ( n ) ");である。


*参考文献 [#yc5cf108]

-『プログラムはなぜ動くのか』
-『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料+午後演習問題』