2分探索木の実際として、AVL木やB木を説明する。

AVL木

木の高さ(深さ?)を求める再帰関数を示した後、実際に高さの差がでてきた時の対処として、 データ追記時に行う、1重回転,2重回転のポインタの繋ぎ替えを説明する。

B木

2分探索木の「１回の比較で対象データ件数が半分」を発展させた事例ということで、 「B木」を紹介する「N個のデータとN+1個の枝ポインタ」で図を使って紹介。 最近のデータベースの実装の中心であることを説明する。 また、最近のプログラム言語での「連想配列」の実装でもB木の応用が使われていることを紹介。

演算子と木

２分木の応用として、構文木の話しの導入として式の扱いを説明する。 演算子には、演算子の優先順位の他に演算子の結合方向などの考え方を紹介。 それを２分木として表現できることを図で示す。 この演算子を表現するときに、 LINK http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95「逆ポーランド記法(後置記法)」 (123*+),「前置記法」(+1*23),「中置記法」(1+2*3) などがある。