Somme bilanciate nell'albero binario

Question

Ho trovato un interessante problema algoritmico. Ci viene dato un albero binario che ha valore 0 in ogni vertice oltre alle foglie. In foglie abbiamo due opzioni:

1. valore è sconosciuto, ma sappiamo che è un numero naturale> = 1

2. valore è noto ed è un numero naturale> = 1

Il problema è decidere se è possibile impostare ogni valore sconosciuto in foglie in modo tale che ogni albero secondario di un dato albero abbia la stessa somma di valori nei vertici nella sua sottostruttura sinistra e destra.

Ad esempio:

tree1:

 0 
    /\ 
    0 ? 
/\ 
    0 5 
/\ 
? ? 

la risposta è no - non prendendo in considerazione che ogni punto di domanda deve essere un numero naturale, è naturalmente possibile

tree2:

 0 
    / \ 
    0  0 
/\ /\ 
    0 10 ? ? 
/\ 
5 ? 

La risposta è SI - impostiamo: 5, 10, 10 rispettivamente in ogni punto interrogativo.

Finora, sono arrivato solo con un algoritmo ovvio: creiamo un sistema di equazioni lineari e controlliamo se ha una soluzione in numeri naturali. Ma penso che possa essere molto lento per i grandi alberi e dovrebbe essere un modo migliore per risolverlo. Qualcuno può aiutare? Sarei molto grato.

Answer 1

Penso che una soluzione ricorsiva funzioni bene. Ad ogni nodo prendi il peso dei bambini di sinistra e di destra. Si hanno le seguenti casi:

1. L e R sono entrambi noti: Il nodo è valida sse L == R
2. Né L o R è noto: Questo nodo è sconosciuto e ha molteplicità doppio di quella più grande molteplicità di L e R
3. Esattamente uno di L o R è sconosciuto: questo nodo è valido se il peso di figlio conosciuto è divisibile per la moltiplicazione del figlio sconosciuto . Il suo peso è il doppio del peso del bambino conosciuto.

L'idea è che è necessario tenere traccia di quanti bambini sconosciuti si trovano al di sotto di un determinato nodo, poiché i valori possono essere solo numeri interi. La molteplicità raddoppia sempre perché, su un nodo, anche se il suo figlio sinistro ha 4 incognite e il suo diritto ha 1 sconosciuto, allora l'1 sconosciuto dovrà essere un multiplo di 4 e quindi la molteplicità di questo nodo dovrà essere 8.

Nota: sto usando la parola molteplicità qui e non è davvero molto bene, ma non riuscivo a pensare a una buona parola da usare.

Ecco il codice, in Go, che dimostra questa soluzione sui vostri esempi:

package main 

import (
    "fmt" 
) 

// Assume that (Left == nil) == (Right == nil) 
type Tree struct { 
    Val   int 
    Left, Right *Tree 
} 

func (t *Tree) GetWeight() (weight int, valid bool) { 
    if t.Left == nil { 
    return t.Val, true 
    } 
    l, lv := t.Left.GetWeight() 
    r, rv := t.Right.GetWeight() 
    if !lv || !rv { 
    return 0, false 
    } 
    if l < 0 && r < 0 { 
    if l < r { 
     return 2 * l, true 
    } 
    return 2 * r, true 
    } 
    if l < 0 { 
    return 2 * r, r%(-l) == 0 
    } 
    if r < 0 { 
    return 2 * l, l%(-r) == 0 
    } 
    return r + l, r == l 
} 

func main() { 
    t := Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: 5}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 10}, 
    }, 
    &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
    }, 
    } 
    w, v := t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
    t = Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 5}, 
    }, 
    &Tree{Val: -1}, 
    } 
    w, v = t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
} 

Answer 2

Questo è parallelizzabile. Crei sistemi di equazioni dalle foglie verso la radice, unendo equazioni (e calcoli) ad ogni vertice. Quando un sistema di equazioni diventa impossibile, interrompere tutti i calcoli.

Un analogo non parallelo di questo sarebbe la valutazione di cortocircuito.