Sumas equilibradas en árbol binario

Question

Encontré un problema algorítmico interesante. Nos da un árbol binario que tiene un valor 0 en cada vértice aparte de las hojas. En las hojas tenemos dos opciones:

1. valor es desconocido, pero sabemos que es un número natural es conocida> = 1

2. valor y es un número natural> = 1

El problema es decidir si es posible establecer cada valor desconocido en las hojas de manera que cada subárbol de un árbol dado tenga la misma suma de valores en los vértices en su subárbol izquierdo y derecho.

Por ejemplo:

tree1:

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

la respuesta es no - no teniendo en cuenta que cada signo de interrogación tiene que ser un número natural, es posible, por supuesto

árbol2:

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

La respuesta es SÍ - establecemos: 5, 10, 10 respectivamente en cada signo de interrogación.

Hasta ahora, surgió solo con un algoritmo obvio: creamos un sistema de ecuaciones lineales y verificamos si tiene una solución en números naturales. Pero creo que puede ser muy lento para árboles grandes y debería ser una mejor forma de resolverlo. ¿Alguien puede ayudar? Estaría muy agradecido.

Answer 1

Creo que una solución recursiva funciona bien. En cada nodo, obtenga el peso de los niños izquierdo y derecho. Tiene las siguientes casos:

1. L y R son ambos conocidos: el nodo es válido si y sólo si L == R
2. Ni L o R es conocido: Este nodo es desconocido y tiene multiplicidad dos veces la de la mayor multiplicidad de L y R
3. Se desconoce exactamente uno de L o R: este nodo es válido si el peso del niño conocido es divisible por la multiplicidad del niño desconocido . Su peso es dos veces el peso del niño conocido.

La idea aquí es que necesita realizar un seguimiento de cuántos niños desconocidos están debajo de un nodo determinado, ya que los valores solo pueden ser enteros. La multiplicidad siempre se duplica porque, en un nodo, incluso si su hijo izquierdo tiene 4 incógnitas y su derecho tiene 1 desconocido, entonces el 1 desconocido tendrá que ser un múltiplo de 4, por lo que la multiplicidad de este nodo deberá ser 8.

Nota: Estoy usando la palabra multiplicidad aquí y no está del todo bien, pero no pude pensar en una buena palabra para usar.

Aquí es código, en Go, que demuestra esta solución en sus ejemplos:

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

Esto es paralelizable. Crea sistemas de ecuaciones desde las hojas hacia la raíz, fusionando ecuaciones (y cálculos) en cada vértice. Cuando un sistema de ecuaciones se vuelve imposible, cancele todos los cálculos.

Un análogo no paralelo de esto sería una evaluación de cortocircuito.