読者です 読者をやめる 読者になる 読者になる

ALDS1_8-A Binary Search Tree Iを解く話

根付き木,二分木に続いて二分探索木を実装する.

二分探索木(Binary Search Tree)

・内部接点はが {キー,左部部分木, 右部分木} を持つような根付き木.

・二分探索木条件(Binary search tree property)を満たす木.

 二分探索木条件: 左部分木の根 <= キー <= 右部部分木の根

 

特徴

・二分探索木に中間順巡回を行うと,昇順に並んだキーが得られる.

・連結リストのように動的にキーの挿入,削除が可能.

 

挿入操作の実装

・ノード同士はポインタで接続

・各ノード: {キー,左部分木のルートへのポインタ,右部分木のルートへのポインタ}

・挿入するキーは葉になる.

・最初のループでxを挿入する位置z(現在葉の子)まで移動

・xはNILなのでxの親yをいじってzをつなぐ.

・yがNILのときzはrootにする.

 

計算量

木の高さh回キーの比較をする.ノード数がnのとき,h = log_2(n)なので計算量はO(log_2(n)).バランスの悪い木ではノード数だけ比較をするので計算量がO(n)になることに注意.

 

実装

gist75c6237289e9f10b588a26566640136c

 

 感想

 実装をする前に必要な時間を見積もるようにしている.短時間で実装できるようになる事も目標だが,自分の実装力を客観的に測定できる事も必要である.まだ見積もり時間を越してしまうが,AOJ本を始めた頃に比べて精度は高くなっている.