Как удалить дочерние узлы дерева с одним дочерним элементом

Question

У меня есть массив для обхода дерева по порядку (значения узлов - значения глубины). Все, что я хочу сделать, - это минимизировать дерево, удалив дочерние узлы, имеющие только один ребенок.

В качестве примера (дерево с максимальной глубиной = 3) problem visualized here

Входной массив: [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 во входном массиве A в диапазоне [left, right]. Это дети текущего узла. Если таких элементов нет, напечатайте output_level и вернитесь. Если есть только один такой элемент, «удалите» текущий узел (т. Е. Не печатайте его), увеличьте left на 1 и вызовите функцию рекурсивно. Если есть два или более таких элемента, напечатайте output_level, увеличьте output_level на 1 и примените функцию рекурсивно к каждому из интервалов, разделенных дочерними элементами. Всегда Увеличение input_level при выполнении рекурсивного вызова.

Для примера ввода A=[0, 1, 2, 3, 3, 1, 2, 3], первый алгоритм найдет элементы со значением 1, на индексы 1 и 5. Затем было бы напечатать 0, увеличить output_level и current_level на 1, и называют себя рекурсивно два раза: на диапазонах [1 , 4] и [5, 7].

Сложность этого вопроса заключается в O (n) в худшем случае (для вырожденного дерева, которое фактически является списком), но O (nlog (n)) в среднем как случайный n- ary tree имеет высоту O (log (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 << ' '; 
    } 
}