ALDS1_7_A Rooted Treesを解く話

入力を根付き木として保存する問題である．

ノードの深さ，種類（根，内部ノード，葉），深さも答えさせるのでそれぞれの概念の定義をきちんと理解する必要がある．

木（Tree）

・連結で閉路をもたないグラフ G = (Vertex, Edge)．

・木について話すときは頂点（Vertex）をノード（Node)と言ったりする．

根付き木

・特別なノードである根（Root）を1つだけ持つ木．

多分木/N分木（Multi-way tree/ N-ary tree）

・3つ以上の子を持つノードが存在する木．

木に関する用語

・ノードuの親（Parent）: uから根rに向かうパスの最初のエッジでuと繋がるノード．
・ノードuの深さ（Depth）:根rからuにたどり着くまでの辺の数．
・根（Root）：親を持たないノード．
・内部ノード（Internal node）：親と子を持つノード．
・葉（Leaf）：子を持たないノード．

左子右兄弟表現（Left-child right-sibling representation)

・木構造の表現の1つ．
・多分木を2分木により表現.
・1つのノードを{親，最も左の子，最も近い右の兄弟｝により表現．
・この表現を配列で管理して木全体を実装.

ノードの深さの計算

①素朴なやり方：ノードから根にたどり着くまでの辺を数える．

②再帰を使ったやり方：

　 1.  深さ０で根からスタート．

     2. 左子へ一段下がる．このとき深さをインクリメント．

     3. 同じ段の最も右の兄弟まで辿る．兄弟の深さは同じ．

     4. 2と3を最も左の葉にたどり着くまで繰り返す．

再帰で書くと

  1. calc_depth(node, depth)

  2.     Tree[node].d = depth

  3.     if Tree[node].child != NIL

  4.         calc_depth(Tree[node].child, depth++)

  5.     if Tree[node].sibling != NIL

  6.         calc_depth(Tree[node].sibling, depth)

実装

gist7ec757a5dfd1c569386c0d0bf956fe8d

感想

AOJ本を読んでいるときはスラスラ進むのだが，実装ではスムーズにいかず時間を取られる．cvpaper.challengeで有名な片岡さんの記事を思い出した．

片岡裕雄 技術メモ How to study "computer vision" (Kataoka style)

僕は「完璧に理解すれば実装はできる」と思っているので，実装する時には手法についてとことん理解度を高めるようにします．

 今回は論文手法うんぬん以前の基本的なデータ構造だが，やっていることは変わらないはず．本を読んだときは「なるほど」と納得するが実装で「？」になる．恐らく理解はしているのだが，それが「実装に足りる理解」ではなかったのだと思う．まずは自分の「実装に足りる理解度」を把握するのが目標である．