es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Tag: BINARY-SEARCH-TREE

Posición de inserción de búsqueda de leet-code: ¿Por qué mi búsqueda binaria no puede devolver la respuesta correcta?

05 Aug, 2023 Programación

clase Solución: def búsqueda_binaria_recursiva(self, nums: list[int], objetivo: int, base: int): if (len(nums) == 1): return base posición = int((len(nums) – 1)/2) if (nums[posición] == objetivo): return base + posición + 1 elif (nums[posición] > objetivo): base = base + int((len(nums) – 1) / 2) return Solución.búsqueda_binaria_recursiva(self, nums[posición+1:], objetivo, base) elif . . . Read more

Calcular un Big O

02 Aug, 2023 Programación

Estoy tratando de calcular el Big-O de esta función que está reflejando el árbol de búsqueda binario (estructura de datos). Pero no estoy seguro si lo calculé correctamente o no. ¿Podrías explicar cuál sería el Big-O de esta función? void mirror(NODE *root){ if (root) { mirror(root->left); mirror(root->right); NODE *temp = . . . Read more

Demuestra que para cualquier árbol AVL con altura h, todos los niveles hasta h/2 son árboles completos mediante inducción. Para demostrar esto por inducción, primero estableceremos el caso base. Cuando h = 1, el árbol AVL constará de un único nodo, lo cual se considera un árbol completo. Ahora asumamos que para un árbol AVL con altura n, todos los niveles hasta n/2 son árboles completos. Consideremos un árbol AVL T con altura n+1. Podemos divide este árbol en dos subárboles más pequeños: el subárbol izquierdo L y el subárbol derecho R. La altura de ambos subárboles será n o n+1, ya que ambos deben tener diferencias de altura de a lo sumo 1 debido a la propiedad AVL. Por nuestra suposición de inducción, sabemos que los niveles hasta n/2 son árboles completos tanto en L como en R. Si los dos subárboles tienen alturas iguales, entonces todos los niveles hasta (n+1)/2 también serán árboles completos en el árbol T. Si los subárboles tienen alturas diferentes, podemos observar que uno de los subárboles, digamos L, tiene una altura de n+1 mientras que el otro subárbol, R, tiene una altura de n. En este caso, el subárbol L no puede tener un nivel adicional en comparación con R. Por lo tanto, sabemos que los niveles hasta n/2 siguen siendo árboles completos tanto en L como en R. Concluimos que para cualquier árbol AVL con altura h, todos los niveles hasta h/2 son árboles completos.

01 Aug, 2023 Programación

Me dieron esta pregunta en un examen: “demuestra por inducción, que para un árbol AVL dado de altura h, todos los niveles del árbol hasta h/2 (redondeado hacia abajo) son árboles binarios completos”. Anoté la siguiente respuesta y me gustaría saber si mi argumento es válido. Caso base: h=0-> entonces . . . Read more