algorithm - tipos - modelo c4 5

¿De cuántas maneras puede insertar una serie de valores en un BST para formar un árbol específico?

Question

Esta pregunta anterior preguntaba de cuántas maneras había para insertar los valores 1 - 7 en un árbol de búsqueda binario que daría como resultado el siguiente árbol:

       4
     /   /
    2     6
   / /   / /
  1   3 5   7

(La respuesta es 80, por cierto).

Supongamos que, en general, se le otorga una BST arbitraria que contiene un conjunto de valores y desea saber de cuántas maneras existen para insertar esos valores en una BST que terminaría produciendo el árbol resultante. ¿Hay un algoritmo eficiente para determinar esto?

¡Gracias!

Answer 1

Esta es una pregunta interesante. Implementé esta idea en Python y esta memorización de recursión más tiene un rendimiento bastante bueno. El "seq" es la lista de entrada de enteros únicos

def answer(seq):
    from math import factorial
    BStore = dict() # store binomsial coefficient
    Store = dict() # store the recusion step 
    def TreeGenerator(a,L): # for a given number a and a list L, this functions returns the left tree (a list) and the right tree (a list)
        LT = []
        RT = []
        for i in L:
            if i<a:
               LT.append(i)
            else:
               RT.append(i)
        solution = [LT,RT]
        return(solution)       
    def binomial_coefficient(n, k):
        d = n - k
        if d < 0:
           return(0)
        return(factorial(n) / factorial(k) / factorial(d))
    def binomial(n, k):
        if (n, k) in BStore:
           return(BStore[n, k])
        else:
           solution = binomial_coefficient(n, k)
           BStore[n, k] = solution
           return(solution)    
    def R(S): # recursion starts here
        if tuple(S) in Store:
           return(Store[tuple(S)])
        else:
           if len(S)<2:
              results = 1
           else:
              a = S[0]
              S = S[1:]
              Tree = TreeGenerator(a,S)
              R1 = R(Tree[0])
              R2 = R(Tree[1]) 
              results = binomial(len(R1)+len(R2), len(R2))*R1*R2             
        Store[tuple(S)] = results
        return(results)
     return(R(seq)) 

Answer 2

Podemos resolver esto utilizando un algoritmo recursivo inteligente.

Como nuestro caso base, si le dan un árbol vacío, hay exactamente una forma de construir ese árbol: no inserte ningún valor.

Para el caso recursivo, supongamos que tienes un BST que se ve así:

              v
             / /
            L   R

Aquí, v es la raíz, y L y R son los subárboles correctos, respectivamente.

Si queremos construir este árbol de búsqueda binario, tendríamos que empezar insertando v primero; si no lo hiciéramos, v no sería la raíz. Después de insertar v, necesitamos insertar los elementos en un ordenamiento que hará que los subárboles L y R se reconstruyan. La parte difícil aquí es que no necesitamos acumular toda la L antes de construir la R o viceversa; podríamos insertar algunos elementos de L, luego algunos elementos de R, luego más elementos de L, luego más elementos de R, etc.

Afortunadamente, sin embargo, hay una observación útil que podemos hacer. Supongamos que S _L es una secuencia de elementos que, si se insertan en una BST, forman la BST L. De manera similar, sea S _R una secuencia de elementos que si se insertan en una BST forman la BST R. Si consideramos cualquier posible intercalación de En las secuencias S _L y S _R , terminaremos con una secuencia de elementos que, si se insertan en una BST que contiene solo v, construirán el árbol.

   v
  / /
 L   R

Como ejemplo, considere este árbol:

       4
     /   /
    2     6
   / /   / /
  1   3 5   7

Una posible secuencia que construye el subárbol izquierdo (que contiene 1, 2, 3) es 2, 1, 3. Una posible secuencia que construye el subárbol derecho es 6, 5, 7. Cualquier posible intercalación de esas secuencias, cuando se inserta en un BST que contiene solo el nodo raíz 4, terminará construyendo el BST anterior. Por ejemplo, cualquiera de estas secuencias funcionará:

 2, 1, 3, 6, 5, 7
 2, 6, 1, 5, 3, 7
 6, 5, 2, 1, 3, 7
 ...

Dado que, dadas las secuencias S _L y S _R que forman L y R podemos intercalarlas en cualquier orden, podemos escribir una buena fórmula para el número de secuencias que construirán un árbol con v como su raíz, L como su raíz. subárbol izquierdo, y R como su subárbol derecho:

# ways = (# # intercalaciones de S _L y S _R ) × (# posibles S _L s) × (# posibles S _R s)

Si lo piensa bien, los dos últimos términos de este producto se pueden encontrar al encontrar recursivamente el número de secuencias de inserción que funcionan para los subárboles izquierdo y derecho. Esto significa que si podemos averiguar cuántas interlusiones posibles hay para las dos secuencias, ¡entonces podemos determinar cuántas secuencias de inserción posibles construirán un árbol dado mediante la evaluación recursiva de la expresión anterior!

Entonces, ¿cuántos entresijos hay? Si nos dan dos secuencias de longitud myn sin duplicados en ellas, entonces podemos llegar al número de entrecruzamientos de esas secuencias con la siguiente observación. Considera la secuencia

L L L ... L R R R ... R
  m times     n times

Cualquier permutación de esta secuencia devolverá una serie de Ls y Rs donde el número de Ls es igual al número de elementos en la secuencia de longitud my el número de Rs es igual al número de elementos en la secuencia de longitud n . Podemos interpretar esta secuencia como una manera de describir cómo construir el intercalado: cada vez que vemos L, insertamos un elemento de la secuencia de la izquierda y cada vez que vemos una R, insertamos un elemento de la secuencia de la derecha. Por ejemplo, considere las secuencias 4, 1, 0, 3 y 2, 7. Luego, la permutación LLRLRL da la secuencia

 4, 1, 2, 0, 3, 7
 L  L  R  L  R  L

Si comenzamos con una secuencia de m L y n R, el número de permutaciones distintas vuelve como

(m + n)!
-------- = (m + n) choose m
 m!  n!

Esto se mantiene porque hay (m + n)! posibles formas de reordenar las L y las R si todas fueran distintas. Dado que no lo son, cada pedido se cuenta m! ¡norte! demasiadas veces porque podemos permutar la L indistintamente y la R indistintamente. Otra forma de pensar sobre esto es considerar el conjunto {1, 2, 3, ..., m + n} de índices en el intercalado, luego elegir m de ellos para rellenar con elementos de la primera secuencia, completando implícitamente el Resto de ellos con elementos de la secuencia correcta.

Bien ... ahora tenemos una forma de determinar el número de formas de intercalar dos secuencias de longitud m y n. Por lo tanto, tenemos lo siguiente:

# ways = (# # intercalaciones de S _L y S _R ) × (# posibles S _L s) × (# posibles S _R s)

= ((m + n) elija n) × (# posibles S _L s) × (# posibles S _R s)

Donde m es el número de elementos en el subárbol izquierdo y n es el número de elementos en el subárbol derecho. ¡Hurra!

Por lo tanto, podemos escribir pseudocódigo para este algoritmo:

function countInsertionOrderings(Tree t) {
    if t is null, return 1;
    otherwise:
       let m = numElementsIn(t.left);
       let n = numElementsIn(t.right);
       return choose(m + n, n) * 
              countInsertionOrderings(t.left) *
              countInsertionOrderings(t.right);
}

Este algoritmo realiza un total de O (n) multiplicaciones, donde n es el número de nodos en el árbol, y visita cada nodo exactamente una vez (asumiendo que la cantidad de elementos en el BST se almacena en caché en cada nodo). Sin embargo, esto no significa que el algoritmo se ejecute en el tiempo O (n), porque el trabajo requerido para multiplicar estos números crecerá rápidamente a medida que los números se hagan más y más grandes.

¡Espero que esto ayude!