algorithm - 単一の子を持つツリー ノードの子を削除する方法

Question

ツリーを事前にトラバーサルするための配列があります (ノードの値は深さの値です)。私がやりたいのは、子が1つしかない内部ノードの子を削除してツリーを最小化することだけです。

例として (最大深さ = 3 のツリー) ここで視覚化された問題

入力配列: [0, 1, 2, 3, 3, 1, 2, 3]
出力配列: [0, 1, 2, 2, 1]

アルゴリズムはどうあるべきですか？

Answer 1

単純な O(nlog(n)) 平均ケース アルゴリズムは、分割統治法による問題の攻撃から生じます。

input_level = 0、output_level=0、 、left=0で開始しright=n-1ます。

再帰的な各ステップで、範囲 [ , ]input_level+1の入力配列の値を持つ要素をカウントします。これらは現在のノードの子です。そのような要素がない場合は、出力して戻ります。そのような要素が 1 つしかない場合は、現在のノードを「削除」し (つまり、出力しない)、1 ずつ増やして、関数を再帰的に呼び出します。そのような要素が 2 つ以上ある場合は、 を出力し、1 ずつ増やして、子要素によって区切られた各間隔に関数を再帰的に適用します。再帰呼び出しを行うときは常に増加します。Aleftrightoutput_levelleftoutput_leveloutput_levelinput_level

input の例A=[0, 1, 2, 3, 3, 1, 2, 3]では、最初にアルゴリズムが値 1 の要素をインデックス 1 と 5 で見つけます。次に、0 を出力し、 output_levelandcurrent_levelを 1 ずつ増やして、範囲 [1, 4] と [5, 7]。

これの複雑さは、最悪の場合 (実際にはリストである縮退ツリーの場合) O(n ² ) ですが、ランダムな n 分ツリーの高さは O(ログ (n))。

Answer 2

次のアルゴリズムは O(N) で実行されます。今度は正解できそうです。

#include <algorithm>
#include <iostream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

void mark_nodes(const std::vector<unsigned>& tree,
                std::vector<bool>& mark) {
  // {depth, index, mark?}
  using triple = std::tuple<unsigned, unsigned, bool>;
  std::stack<triple> stk;
  stk.push({0, 0, false});
  for (auto i = 1u; i < mark.size(); ++i) {
    auto depth = tree[i];
    auto top_depth = std::get<0>(stk.top());
    if (depth == top_depth) {
      stk.pop();
      if (stk.size()) std::get<2>(stk.top()) = false;
      continue;
    }
    if (depth > top_depth) {
      std::get<2>(stk.top()) = true;
      stk.push({depth, i, false});
      continue;
    }
    while (std::get<0>(stk.top()) != depth) {
      mark[std::get<1>(stk.top())] = std::get<2>(stk.top());
      stk.pop();
    }
    mark[std::get<1>(stk.top())] = std::get<2>(stk.top());
    stk.pop();
    if (stk.size()) std::get<2>(stk.top()) = false;
    stk.push({depth, i, false});
  }
  mark[0] = false;
}

std::vector<unsigned> trim_single_child_nodes(
    std::vector<unsigned> tree) {
  tree.push_back(0u);
  std::vector<bool> mark(tree.size(), false);
  mark_nodes(tree, mark);
  std::vector<unsigned> ret(1, 0);
  tree.pop_back();
  mark.pop_back();
  auto max_depth = *std::max_element(tree.begin(), tree.end());
  std::vector<unsigned> depth_map(max_depth + 1, 0);
  for (auto i = 1u; i < tree.size(); ++i) {
    if (mark[i]) {
      if (tree[i] > tree[i - 1]) {
        depth_map[tree[i]] = depth_map[tree[i - 1]];
      }
    } else {
      if (tree[i] > tree[i - 1]) {
        depth_map[tree[i]] = depth_map[tree[i - 1]] + 1;
      }
      ret.push_back(depth_map[tree[i]]);
    }
  }
  return ret;
}

int main() {
  std::vector<unsigned> input = {0, 1, 2, 3, 3, 1, 2, 3};
  auto output = trim_single_child_nodes(input);
  for (auto depth : output) {
    std::cout << depth << ' ';
  }
}