たまには

まじめな内容のブログと行きますか。

今日は試験二日前です。
データ構造とアルゴリズムの勉強してた。
主にリスト、二分探索木 (binary search tree)。
いやー、、、この課目も何故単位が取れたのかがわからないくらい授業理解してなかったけど。
昔の課題プログラムのソース見ると結構わかる、、、

試験の問題もリスト、BSTに限られてるみたいだから、どういう風に関数作ってた～とかを再復習。
おおざっぱな構造は覚えてたけど、BSTの削除の手順とか全然覚えてなかった。
復習がてら思い出しながら書いてみる。

1 現在調べているノードと消したいノードの要素の差を出す(消したいノード - 調べているノード)
2 差が0(消したいノード)の場合
a) 調べているノードのポインタが2つともNULL(そのノードが葉)→ノードをNULLにする。
b) 左のポインタがNULLかつ右のポインタがNULLではない→右のノードを今調べているノードに。
c) b)と逆の場合→上に同じ。
d) 両方ともNULLでない→右側の部分木で最小のノードを探し、そのノードを削除。消したいノードを先ほど消したノードで上書き。

3 差が正の値の場合→消したい値よりも小さい値のノードなので、ノードの右側の部分木を再帰的に調べる。
4 差が負の値の場合→ノードの左側の部分木を再帰的に調べる。
5 最後に削除された2分木を返す

こんな感じか。
結構うろ覚えだなぁ、、、あとでもう一回復習しよう。
今思うと高校の頃は帰納法の考え方も理解はしてなかったなぁ、、、
いや今も苦手だけどさ。
理論を理解するんじゃなくてやり方を理解するって勉強だったからなぁ。
まじめに勉強したら簡単な部分は理解できたが。
そーゆー意味では離散とか論理は駄目だな、俺。

あと2日、、、FHも全然やれない、、、やっちゃいけない。
やるとしても寝る前に