トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

木構造(実践問題)

[アルゴリズム]

木構造 - 実践問題

  A Rational Sequence 2

問題の前提

  • A Rational Sequence 2
    • 2分木の中身が親要素の数で変化するという感じ
    • 親が p/q で表される場合、左の子は p/p+q、右の子は p+q/q
  • ノードの番号が先行順巡回 (preorder tree walk) で与えられる
    • 親→左の子→右の子→右の子…→一番左下の子
  • 入力として分数が与えられるので、そのノードの番号を答える
    • 5/2, 2178309/1346269

ファイルが存在しません。

  解法

木の深さを調べる

問題文にて

  • 左の子 / 右の子
    • 左の子 = p / ( p + q )
    • 右の子 = (p + q) / q

と決まっており、当然pとqが負の数になることもない。よって分数の左と右の大きさを比べれば、親の要素がわかる。

親を特定して、木の深さを調べる手順

深さを1として処理を始める

  1. 左の子 > 右の子 ならば2へ、そうでなければ3へ
  2. 親の要素は, 左の子-右の子/右の子、深さを+1して4へ
  3. 親の要素は, 右の子-左の子/左の子、深さを+1して4へ
  4. 右の子、左の子が両方1になれば木構造の頂点なので終了

深さが求められると、それにより対象の要素が収まるノードの番号の範囲がわかる。

上から順に木の深さを数えた時

  • 左端のノードの番号は、深さをNとすると2^(N - 1)
  • 右端のノードの番号は、深さをNとすると2^N - 1

後は、対象のノード自体が左端から何番目の兄弟ノードか数えて、左端のノードの番号に足し合わせると終わり。

兄弟ノードの数を調べる

ネタあかしをすると、2分木の左・右ノード情報を0/1でマッピングするとそれがそのまま2進数の数値になる。上で、木の深さを調べた際に、自身が右ノードだったら1、自身が左ノードだったら0という具合に配列に収めておく。

最後にそれを10進数に直せば、それが自身が左端から何番目の兄弟ノードかの答えになる。

後は、上で求めた左端のノードの番号と何番目の兄弟ノードかを足し合わせると終わり。

お名前: コメント: