2分木(2分探索木)
テスト前に簡単に説明していた2分探索木を説明する。 リスト構造の問題点として、 挿入処理のオーダO(1),N番目参照のオーダO(N),データ探索O(N)の説明。 特に、データ探索ではN/2番目のアクセスがリストでは、問題になることを説明する。
探索リスト
データ探索で、速度向上のテクニックとして、辞書などに使われる、 検索結果のデータを先頭に入れ換えるテクニックを紹介。
ヒープ
2分探索木の配列上の実装として、ヒープを説明する。 i番目の左枝を(i*2+1)番目,右枝を(i*2+2)番目…といったテクニックを紹介する。
2分探索木
2分木の説明として、セルの生成関数を示した後、直接の木の生成、データ検索処理、データ追加処理の説明を行う。
プログラムの書き間違いがあって修正するが、「思い込み間違い」の危険さを力説したあと、 「思い込み間違いを減らすには?」と聞いてみる。 インターンシップ報告会の後だし、関連ネタとして「ペアプログラミング」などの返答を 期待したけど、答えてくれる人がいなかった…寂しい…