ホーム » 2007 » 11月 » 05

日別アーカイブ: 2007年11月5日

2007年11月
« 10月   12月 »
 123
45678910
11121314151617
18192021222324
252627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木・AVL木・B木と2分木の応用(演算子と木)

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

AVL木

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

B木

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

演算子と木

2分木の応用として、構文木の話しの導入として式の扱いを説明する。 演算子には、演算子の優先順位の他に演算子の結合方向などの考え方を紹介。 それを2分木として表現できることを図で示す。 この演算子を表現するときに、 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) などがある。