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にする．

計算量

木の高さ回キーの比較をする．ノード数がのとき，なので計算量は．バランスの悪い木ではノード数だけ比較をするので計算量がになることに注意．

実装

gist75c6237289e9f10b588a26566640136c

 感想

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