Il modo più efficace per generare tutti i discendenti di tutti i nodi in un albero

Se effettivamente vuoi PRODURRE ogni lista come copie diverse, non puoi sperare di ottenere uno spazio migliore di n ^ 2 nel peggiore dei casi. Se hai solo bisogno di ACCESSO ad ogni lista:

Eseguirò un traversal in ordine dell'albero partendo dalla radice:

link

Quindi, per ciascun nodo nella struttura ad albero, il numero minimo in ordine e il numero massimo in ordine nella sua sottostruttura (questo è facilmente gestibile tramite ricorsione - e puoi simularlo con uno stack se lo desideri).

Ora inserisci tutti i nodi in una matrice A di lunghezza n in cui il nodo con il numero in ordine i è in posizione i. Quindi, quando hai bisogno di trovare la lista per un nodo X, cerchi A [X.min, X.max] - nota che questo intervallo includerà il nodo X, che può anche essere facilmente risolto.

Tutto ciò è compiuto in tempo O (n) e richiede O (n) spazio.

Spero che questo aiuti.

La parte inefficiente non sta attraversando l'albero, ma sta creando gli elenchi di nodi. Sembrerebbe ragionevole creare la lista in questo modo:

descendants[node] = []
for child in node.childs:
    descendants[node].push(child)
    for d in descendants[child]:
        descendants[node].push(d)

Poiché ciascun nodo discendente viene copiato nella lista di ciascun genitore, si ottiene in genere con O (n log n) la complessità per gli alberi bilanciati, e O (n²) il caso peggiore per gli alberi degenerati che sono realmente elenchi collegati.

Possiamo passare a O (n) o O (1) a seconda che sia necessario eseguire qualche setup se usiamo il trucco di calcolare le liste pigramente. Supponiamo di avere un child_iterator(node) che ci fornisce i child di quel nodo. Quindi possiamo definire banalmente un descendant_iterator(node) come questo:

def descendant_iterator(node):
  for child in child_iterator(node):
    yield from descendant_iterator(child)
  yield node

Una soluzione non ricorsiva è molto più coinvolta, dal momento che il flusso del controllo iteratore è complicato (coroutine!). Aggiornerò questa risposta più tardi oggi.

Poiché l'attraversamento di un albero è O (n) e l'iterazione su un elenco è lineare, questo trucco rimanda completamente il costo finché non viene pagato comunque. Ad esempio, la stampa dell'elenco dei discendenti per ciascun nodo ha la complessità del caso peggiore O (n²): l'iterazione su tutti i nodi è O (n) e quindi viene ripetuta su tutti i discendenti del nodo, sia che siano memorizzati in un elenco o calcolati ad hoc .

Ovviamente, questo non funzionerà se hai bisogno di una collezione reale su cui lavorare.

Questo breve algoritmo dovrebbe farlo, Dai un'occhiata al codice public void TestTreeNodeChildrenListing()

L'algoritmo passa effettivamente attraverso i nodi dell'albero in sequenza e mantiene l'elenco dei genitori del nodo corrente. Secondo il tuo requisito, il nodo corrente è figlio di ciascun nodo genitore e viene aggiunto a ciascuno di essi come un bambino.

Il risultato finale è memorizzato nel dizionario.

    [TestFixture]
    public class TreeNodeChildrenListing
    {
        private TreeNode _root;

        [SetUp]
        public void SetUp()
        {
            _root = new TreeNode("root");
            int rootCount = 0;
            for (int i = 0; i < 2; i++)
            {
                int iCount = 0;
                var iNode = new TreeNode("i:" + i);
                _root.Children.Add(iNode);
                rootCount++;
                for (int j = 0; j < 2; j++)
                {
                    int jCount = 0;
                    var jNode = new TreeNode(iNode.Value + "_j:" + j);
                    iCount++;
                    rootCount++;
                    iNode.Children.Add(jNode);
                    for (int k = 0; k < 2; k++)
                    {
                        var kNode = new TreeNode(jNode.Value + "_k:" + k);
                        jNode.Children.Add(kNode);
                        iCount++;
                        rootCount++;
                        jCount++;

                    }
                    jNode.Value += " ChildCount:" + jCount;
                }
                iNode.Value += " ChildCount:" + iCount;
            }
            _root.Value += " ChildCount:" + rootCount;
        }

        [Test]
        public void TestTreeNodeChildrenListing()
        {
            var iteration = new Stack<TreeNode>();
            var parents = new List<TreeNode>();
            var dic = new Dictionary<TreeNode, IList<TreeNode>>();

            TreeNode node = _root;
            while (node != null)
            {
                if (node.Children.Count > 0)
                {
                    if (!dic.ContainsKey(node))
                        dic.Add(node,new List<TreeNode>());

                    parents.Add(node);
                    foreach (var child in node.Children)
                    {
                        foreach (var parent in parents)
                        {
                            dic[parent].Add(child);
                        }
                        iteration.Push(child);
                    }
                }

                if (iteration.Count > 0)
                    node = iteration.Pop();
                else
                    node = null;

                bool removeParents = true;
                while (removeParents)
                {
                    var lastParent = parents[parents.Count - 1];
                    if (!lastParent.Children.Contains(node)
                        && node != _root && lastParent != _root)
                    {
                        parents.Remove(lastParent);
                    }
                    else
                    {
                        removeParents = false;
                    }
                }
            }
        }
    }

    internal class TreeNode
    {
        private IList<TreeNode> _children;
        public string Value { get; set; }

        public TreeNode(string value)
        {
            _children = new List<TreeNode>();
            Value = value;
        }

        public IList<TreeNode> Children
        {
            get { return _children; }
        }
    }
}

Normalmente, useresti un approccio ricorsivo, perché ti consente di cambiare l'ordine di esecuzione in modo da poter calcolare il numero di foglie partendo dalle foglie verso l'alto. Poiché, per aggiornare il nodo corrente, dovresti utilizzare il risultato della tua chiamata ricorsiva, sarebbe necessario uno sforzo particolare per ottenere una versione ricorsiva della coda. Se non ti impegni, allora ovviamente questo approccio esploderebbe semplicemente lo stack per un grande albero.

Dato che ci siamo resi conto che l'idea principale è di ottenere un ordine in loop partendo dalle foglie e risalendo verso la radice, l'idea naturale che viene in mente è di eseguire un ordinamento topologico sull'albero. La sequenza risultante di nodi può essere attraversata linearmente al fine di sommare il numero di foglie (assumendo che si possa verificare che un nodo sia una foglia in O(1) ). La complessità temporale complessiva dell'ordinamento topologico è O(|V|+|E|) .

Suppongo che il tuo N sia il numero di nodi, che sarebbe in genere |V| (dalla nomenclatura DAG). La dimensione di E d'altra parte dipende in gran parte dall'arità del tuo albero. Ad esempio, un albero binario ha al massimo 2 bordi per nodo, quindi O(|E|) = O(2*|V|) = O(|V|) in quel caso, che comporterebbe un algoritmo complessivo di O(|V|) . Nota che a causa della struttura generale di un albero, non puoi avere qualcosa come O(|E|) = O(|V|^2) . Infatti, poiché ogni nodo ha un genitore univoco, è possibile avere al massimo un edge da contare per nodo quando si considerano solo parent-relations, quindi per gli alberi abbiamo una garanzia che O(|E|) = O(|V|) . Pertanto, l'algoritmo di cui sopra è sempre lineare nella dimensione dell'albero.