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

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

#contents


*2分探索木 [#c0fc4525]

 ''2分探索木''とは[[リスト]]をさらに工夫して、配列に要素を追加するときにその大小関係を考慮しつつ左右2つの方向に分岐するリストとしたものである。実際のメモリが2方向に分かれるわけではなく、プログラムによって論理的に実現される。

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


*特徴 [#ha3e81be]

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



*参考文献 [#yc5cf108]

-『プログラムはなぜ動くのか』