【情処本勉強中】2分探索木

2分木については知っていたけど、どうやって探索するのかについては知らなかったのでメモ。

・2文探索木
[再編成処理]
2文探索木のノードが削除された場合の再編成処理
①削除されたノードから見て、左にある最大値を削除されたノードに入れる
②削除されたノードから見て、右にある最小値を削除されたノードに入れる

追加は左の子は右の子よりも大きな値を持つようにする。

[2分木探索]
①行きがけ順(先行順)深さ優先探索
逆ポーランドのなぞり方で先に探索する
②帰りがけ順(後行順)深さ優先探索
逆ポーランドのなぞり方で後に探索する
③通りがけ順(中間順)深さ優先探索
逆ポーランドのなぞり方でノードの中間を探索する
④幅優先探索
配列を先頭から順番に探索

2分木にヒープというものがある。
親要素が常に2つの子要素より大きくならない（またはその逆）構造になっている木。

そのヒープを用いたソート方法。
降順ヒープソートの手順
①親と子を比較。
②親よりも小さな子があれば交換。(ヒープの構成)
③最後のデータと根を交換。
④最後のデータをソート対象から外し、①に戻る。

入れ替えてはソート対象を外しヒープの構成を行う。これを繰り返す。