ホーム » 2007 » 10月 » 02

日別アーカイブ: 2007年10月2日

2007年10月
« 9月   11月 »
 123456
78910111213
14151617181920
21222324252627
28293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木(2分探索木)

テスト前に簡単に説明していた2分探索木を説明する。 リスト構造の問題点として、 挿入処理のオーダO(1),N番目参照のオーダO(N),データ探索O(N)の説明。 特に、データ探索ではN/2番目のアクセスがリストでは、問題になることを説明する。

探索リスト

データ探索で、速度向上のテクニックとして、辞書などに使われる、 検索結果のデータを先頭に入れ換えるテクニックを紹介。

ヒープ

2分探索木の配列上の実装として、ヒープを説明する。 i番目の左枝を(i*2+1)番目,右枝を(i*2+2)番目…といったテクニックを紹介する。

2分探索木

2分木の説明として、セルの生成関数を示した後、直接の木の生成、データ検索処理、データ追加処理の説明を行う。

プログラムの書き間違いがあって修正するが、「思い込み間違い」の危険さを力説したあと、 「思い込み間違いを減らすには?」と聞いてみる。 インターンシップ報告会の後だし、関連ネタとして「ペアプログラミング」などの返答を 期待したけど、答えてくれる人がいなかった…寂しい…