Comment supprimer les enfants de nœuds d'arbre avec un seul enfant

Question

J'ai un tableau pour la traversée de précommande d'un arbre (les valeurs de nœuds sont des valeurs de profondeur). Tout ce que je veux faire est de minimiser l'arbre en supprimant les enfants des noeuds internes ayant un seul enfant.

A titre d'exemple (un arbre avec une profondeur max = 3) problem visualized here

matrice d'entrée: [0, 1, 2, 3, 3, 1, 2, 3]
matrice de sortie: [0, 1 , 2, 2, 1]

Comment devrait être l'algorithme?

Answer 1

Un simple algorithme O (nlog (n)) cas-type découle d'attaquer le problème par l'approche de diviser pour régner. Commencer par input_level = 0, output_level=0, left=0, right=n-1.

Dans chacune des étapes récursives, compter les éléments ayant une valeur input_level+1 dans le tableau d'entrée A dans la fourchette [left, right]. Ce sont les enfants du nœud actuel. S'il n'y a pas de tels éléments, imprimez output_level et retournez. S'il n'y a qu'un seul élément de ce type, "supprimez" le nœud actuel (c'est-à-dire ne l'imprimez pas), augmentez left de 1 et appelez la fonction récursivement. S'il existe deux ou plusieurs de ces éléments, imprimez output_level, augmentez output_level de 1 et appliquez la fonction récursivement à chacun des intervalles délimités par les éléments enfants. Toujours augmentez input_level lors de l'appel récursif.

Pour l'entrée exemple A=[0, 1, 2, 3, 3, 1, 2, 3], d'abord l'algorithme trouverait des éléments à valeur 1, à des index 1 et 5. Ensuite, il imprimerait 0, augmenter output_level et current_level par 1 et lui-même appeler récursive deux fois: sur les plages [1 , 4] et [5, 7]. La complexité est O (n) dans le pire des cas (pour l'arbre dégénéré qui est en fait une liste), mais O (nlog (n)) en moyenne, comme un ary tree a une hauteur O (log (n)).

Answer 2

L'algorithme suivant s'exécute dans O (N). Je suppose que je comprends bien cette fois.

#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 << ' '; 
    } 
}