Cuenta Número de formas de construir árbol de búsqueda binario con n elementos -- python campo con tree camp codereview Relacionados El problema

Count number of ways to construct binary search tree with n elements


6
vote

problema

Español

Tuve esta pregunta en una entrevista:

¿En cuántas maneras, podemos construir un árbol de búsqueda binario de $ n $ elementos?

He escrito este código, pero recibí un comentario que podría mejorarse. ¿Cómo hacerlo?

  DeepPtr7  
Original en ingles

I had this question asked in an interview:

In how many ways, we can construct binary search tree from \$n\$ elements?

I have written this code, but got a feedback that it could be improved. How to do it?

def count_ways(n):     c = [0] * (n+1)     c[0] = 1     c[1] = 1     for i in xrange(2, n+1):         sum_w = 0         for j in xrange(0, i):             sum_w += c[j] * c[i-j-1]         c[i] = sum_w     return c[n]       print count_ways(4) 
     

Lista de respuestas

7
 
vote
vote
La mejor respuesta
 

El número de árboles se puede expresar en la forma cerrada $ frac { binom {2n} {n}} {n + 1}} {n + 1} $, y debido a $ binom {2n} {n} = frac {4n - 6} {n} binom {2 (n-1)} {n-1} $ El resultado se calcula en tiempo lineal.

No haría ninguna pregunta sobre la entrevista cara a cara (a menos que la posición requiera un conocimiento profundo de la teoría combinatoria y del gráfico).

 

The number of trees can be expressed in the closed form \$\frac{\binom{2n}{n}}{n+1}\$, and due to \$\binom{2n}{n} = \frac{4n - 6}{n} \binom{2(n-1)}{n-1}\$ the result is computed in linear time.

I would not ask such question in face-to-face interview (unless the position requires in-depth knowledge of combinatoric and graph theory).

 
 
 
 
2
 
vote

La única optimización obvia para mí es reducir el número de iteraciones en el bucle interno por el factor de dos:

  def count_ways_v2(n):     c = [0] * (n + 1)     c[0] = 1     c[1] = 1     for i in range(2, n + 1):         sum_w = 0         for j in xrange(0, i / 2):             sum_w += 2 * c[j] * c[i - j- 1]         if i % 2 == 1:             sum_w += c[i / 2] * c[i / 2] # Handle the case in which i is odd:         c[i] = sum_w     return c[n]   

espero que ayude.

editar

@peilonrayz sugiere una mejora: sus versiones y minares se ejecutan en un momento cuadrático, pero a través de Números catalán Puede hacerlo en tiempo lineal:

  def count_ways_catalan(n):     a, b = 1, 1     for k in range(2, n + 1):         a *= n + k         b *= k     return a / b   
 

The only optimization obvious to me is to reduce the number of iterations in the inner loop by the factor of two:

def count_ways_v2(n):     c = [0] * (n + 1)     c[0] = 1     c[1] = 1     for i in range(2, n + 1):         sum_w = 0         for j in xrange(0, i / 2):             sum_w += 2 * c[j] * c[i - j- 1]         if i % 2 == 1:             sum_w += c[i / 2] * c[i / 2] # Handle the case in which i is odd:         c[i] = sum_w     return c[n] 

Hope it helps.

Edit

@Peilonrayz suggests an improvement: your and mine versions run in quadratic time, yet via Catalan numbers you can do it in linear time:

def count_ways_catalan(n):     a, b = 1, 1     for k in range(2, n + 1):         a *= n + k         b *= k     return a / b 
 
 
 
 
0
 
vote

Aquí hay una versión ligeramente optimizada:

  # python's default stack size is small from sys import setrecursionlimit setrecursionlimit((1<<31)-1)  def ways(n, cache={}):     if n == 0: return 1     elif n not in cache:         cache[n] = sum(ways(s) * ways(n-s-1) for s in xrange(n))     return cache[n]   
 

Here is a slightly optimized version:

# python's default stack size is small from sys import setrecursionlimit setrecursionlimit((1<<31)-1)  def ways(n, cache={}):     if n == 0: return 1     elif n not in cache:         cache[n] = sum(ways(s) * ways(n-s-1) for s in xrange(n))     return cache[n] 
 
 

Relacionados problema

12  Codificación de árbol binario  ( Binary tree encoding ) 
Implementé una solución a este desafío de codificación en el código de golf. Tengo experiencia decente con C / C ++, pero ha sido un tiempo desde que los us...

2  Montón Binomial en Java  ( Binomial heap in java ) 
Tengo esta implementación de un montón de binomio que proporciona inserto, disminución de la tecla y el extracto en el tiempo logarítmico. minpriorityqueue...

3  Incrustar un HTML (cadena) generado de un árbol estructurado de árbol  ( Embedding an html string generated from a tree structured json ) 
Cómo hacer insertJson3 FASTER (¿Debería mantener el script compatible con versiones anteriores de IE y otros navegadores)? Problema innerHTML de este ...

13  Árbol de búsqueda binaria - C ++  ( Binary search tree c ) 
Estoy implementando varias estructuras de datos en un intento por aprender C ++. A continuación se muestra un árbol de búsqueda binario que he implementado pa...

2  Implementación de árboles de búsqueda de ternarios en Python 3  ( Ternary search tree implementation in python 3 ) 
He implementado un árbol de búsqueda ternario. Funciona bien. Pero si crees que algo necesita mejorarse, dígalo. Este código fue probado en Python 3.7.4. c...

11  Patrones compuestos y de visitantes para la funcionalidad de la encuesta basada en árboles en C #  ( Composite and visitor patterns for tree based survey functionality in c ) 
He escrito alguna funcionalidad de encuesta para un proyecto. Básicamente, un formulario de encuesta genérico que se puede componer de secciones y preguntas. ...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

4  Función abstracta del mapa del árbol  ( Abstract tree map function ) 
Ejercicio 2.31. Resumen tu respuesta Para ejercer 2.30 para producir un Procedimiento Árbol - Mapa con la propiedad. ese árbol cuadrado podría definirs...

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos