Prodotto di tutti i nodi ad eccezione di uno in albero binario

Question

Assumere ci viene dato un albero binario con un intero seduto in ogni nodo.Sto cercando un modo efficace per trovare per ogni percorso dalla radice a una foglia ogni prodotto possibile con esattamente un nodo omesso.Sto cercando una soluzione senza divisioni (cioè I numeri interi possono essere zero).

un modo per andare a riguardo questo ho pensato Posso calcolare tutti i possibili prodotti parziali a partire dalla radice.Questo è ogni nodo memorizza il prodotto del percorso unico dal root su questo nodo (ma eccetto il numero intero memorizzato in quel particolare valore).Quindi per ogni nodo foglia posso salire sul percorso del nodo radice moltiplicando i numeri interi sulla strada.A un determinato nodo prima di accumulare il nodo nel prodotto posso moltiplicare il prodotto con il prodotto prefisso memorizzato nel nodo.

Sembra che stia facendo un sacco di moltiplicazioni ridondanti quando si visita ogni percorso da una foglia alla radice, poiché questi percorsi condividono potenzialmente molti nodi.C'è un modo più veloce per farlo?

Answer 1

Un approccio semplice: per un nodo interno $ x $ , let $ p (x) $ Dentare il prodotto dei numeri interi sul percorso dalla radice a $ x $ , e lasciare $ q (x) $ < / span> Denotare il set di numeri interi ottenibili come il prodotto di tutti tranne uno dei numeri interi sul percorso dalla radice a $ x $ . Ora, scendi l'albero dalla root fino alle foglie, computing $ P (x) $ e $ q (x) $ per ogni nodo $ x $ come vai. Si noti che è possibile calcolare $ p (x), q (x) $ da $ p (w), q (w ) $ , dove $ W $ è il genitore di $ x $ . Il tempo di esecuzione del caso peggiore asintotico sarà $ o (n ^ 2) $ . Nessun algoritmo ha un tempo di esecuzione asintotico peggiore del caso peggiore, poiché può esserci $ \ theta (n ^ 2) $ Prodotti diversi che è necessario utilizzare, quindi qualsiasi algoritmo corretto sarà necessario avere il tempo di esecuzione del caso peggiore almeno $ \ theta (n ^ 2) $ .