【2日目】アルゴリズム参考記事

いやー飲み会で帰るのが遅くなってしまった。考えてみればゴールデンウィーク前って三日坊主になる感満載のタイミングで始めてしまったな。

二分木とはの記事を読んでのメモを貼っておきます。

・二分木は二分探索や二分ヒープを実装するために使われる。

・「二分木は連結された (connected) 閉路をもたない (acyclic) グラフで、各頂点 (vertex) の次数 (degree) （各頂点に出入りする辺の数）が3を超えないもの。」と定義されている。要するに同じノードに戻ってくるようなものは分岐は２つまで。まあ二分木だしね。

・唯一の根を決めることでどんなメリットがあるのか？入力が１つに絞られるのは確かに有難い。

・二分木を実装するなら、まずルートをつくりその下にleft、rightをつくりそこをまずはnullにしておく。ルートの下に階層をつくりたい場合は関数を呼び出し、leftやrightに同じようなものをルートを作る。これ実装できるかな？これができたらファイル構造を作れるかもしれない。

・配列に二分木を格納するという方法はなっとくアルゴリズムでやった気がする。リンクリストではないからハッシュテーブルかな。

・2i+1、2i+2で配列に格納していける。i=0なら1と2に、格納し、1の子ノードとして3と4に格納される。二分ならそこまで大変そうではない。空きが大量になることはあってもそこは使われているからそこは使っているから別のところへ行ってくれというのはない。

・n個のノードをもつ高さhの二分木の場合、配列の要素の数は2^h - nのペースで増えていく。二分木は大きくなればなるほどメモリの消費は激しくなる。そこは気をつける必要がある。

・二分木の巡回方法はいろいろある。根をまず調べて(子ノードまで調べる)、その後で子ノードの根を調べるやり方。子ノードがなくなるまで調べてを繰り返すやり方などがある。

・ノードの中に１つしか線がないものが続いてしまったらそれはもう連結リストになってしまう。二分木としてやっている以上効率が下がってしまう。

・全てを漏らすことなく、同じものを重複せずに調べることを走査という。調べると言われればこれをしなければならない。

・走査には2種類あり、幅優先探索と深さ優先探索がある。⭐️これらをまずは実装してみる。そもそも二分木をクリックもしくは呼び出したら新しい二分木がでてきても作ってみたい。面倒ならファイル構造を対象にできるようになると楽しい。

・写経でいいからまずはこれを実装する。写経でこの長さを書けなければコードを自分でこの長さ書けるとは思えない。