Estoy luchando con hashing y material de árbol de búsqueda binaria. Y leí que en lugar de usar listas para almacenar entradas con los mismos valores hash, también es posible usar árboles de búsqueda binarios. Y trato de entender cuál es el tiempo de ejecución más desfavorable y más desfavorable...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
Esta pregunta explica bastante bien que pueden, pero no muestra ningún ejemplo de que haya dos árboles diferentes con el mismo recorrido de preorden. También se menciona que el recorrido en orden de dos árboles diferentes puede ser el mismo, aunque son estructuralmente diferentes. ¿Hay un ejemplo...
Escribí este código de Python y me pregunté si a veces simplemente no termina (suponiendo que tengamos memoria / tiempo infinito y ningún límite de profundidad de recursión). Intuitivamente pensarías que termina, ya que en algún momento debes tener suerte , y si no termina tienes una cantidad...
Hace poco me enteré de la estructura de datos del árbol de rosas, pero simplemente saliendo de una datadefinición de Haskell y la pequeña descripción de Wikipedia , tengo algunos problemas para entender qué aplicaciones podría tener un árbol de rosas. Como referencia, la datadefinición de Haskell...
Necesito crear un algoritmo recursivo para ver si un árbol binario es un árbol de búsqueda binario, así como contar cuántas ramas completas hay (un nodo primario con nodos secundarios izquierdo y derecho) con una variable de conteo global asumida. Esta es una tarea para mi clase de estructuras de...
Yo entiendo que los árboles de segmentos se pueden utilizar para encontrar la suma de sub conjunto de . Y que esto se puede hacer en tiempo O ( log n ) de acuerdo con el tutorial aquí .AAAO(logn)O(logn)\mathcal{O}(\log n) Sin embargo, no puedo demostrar que el tiempo de consulta es de hecho ....
¿Cómo demuestra que la altura esperada de un árbol de búsqueda binario construido aleatoriamente con nnn nodos es O(logn)O(logn)O(\log n) ? Hay una prueba en CLRS Introducción a los algoritmos (capítulo 12.4), pero no la
Estoy tratando de entender cómo se pueden modificar los árboles indexados binarios (árboles fenwick) para manejar tanto las consultas de rango como las actualizaciones de rango. Encontré las siguientes fuentes: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...
¿Existe alguna definición formal sobre la altura promedio de un árbol binario? Tengo una pregunta tutorial sobre cómo encontrar la altura promedio de un árbol binario usando los siguientes dos métodos: La solución natural podría ser tomar la longitud promedio de todos los caminos posibles desde...
Necesito mantener una colección de enteros en el rango de 0 a 65535 para poder hacer rápidamente lo siguiente: Insertar un nuevo entero Insertar un rango de enteros contiguos Eliminar un número entero Eliminar todos los enteros debajo de un entero Prueba si hay un número entero presente Mis...
Una secuencia binaria de longitud es solo una secuencia ordenada para que cada sea o . Para generar todas esas secuencias binarias, se puede usar la estructura de árbol binario obvia de la siguiente manera: la raíz está "vacía", pero cada hijo izquierdo corresponde a la adición de a la cadena...
En mi clase de Java, estamos aprendiendo sobre la complejidad de diferentes tipos de colecciones. Pronto hablaremos de árboles binarios, sobre los que he estado leyendo. El libro establece que la altura mínima de un árbol binario es , pero no ofrece más explicaciones.Iniciar sesión2( n + 1 ) -...
Usar el vector Earley como un reconocedor es bastante sencillo: cuando se alcanza el final de la cadena, solo tiene que verificar si la producción axiomática completa comenzó en la posición 0. Si tiene al menos una, entonces se acepta la cadena. Usar el vector Earley para reconstruir los árboles...
Conociendo las frecuencias de cada símbolo, ¿es posible determinar la altura máxima del árbol sin aplicar el algoritmo Huffman? ¿Hay alguna fórmula que le dé altura a este
Al insertar un elemento en un árbol de despliegue, las rotaciones se realizan en pares, ya sea en zig-zag o en zig-zig. Cuando hay que realizar un número impar de rotaciones, uno podría hacer la rotación adicional que comienza en la hoja o guardar la rotación adicional y hacerlo en la raíz....
¿Se puede implementar la operación de división para árboles AVL con complejidad? O(logn)O(logn)O(\log n)? Estoy interesado en enlaces a artículos o cualquier información específica sobre este tema. La operación de división divide el árbol AVL en dos árboles AVL derivados, según la clave. Uno de...
He leído en muchos artículos sobre búsqueda de vecinos más cercanos en dimensiones superiores que los árboles KD son exponenciales en K, pero parece que no puedo determinar por qué. Lo que estoy buscando es un análisis sólido de complejidad de tiempo de ejecución que explique este aspecto del...
Suponiendo que los bordes no están dirigidos, tienen un peso único y no tienen rutas negativas, ¿estos algoritmos producen los mismos árboles de expansión
En las aplicaciones del mundo real, ¿hay un beneficio concreto al usar los algoritmos lugar de ?O(log(log(n))O(log(log(n))\mathcal{O}(\log(\log(n))O(log(n))O(log(n))\mathcal{O}(\log(n)) Este es el caso cuando uno usa, por ejemplo, árboles de Van Emde Boas en lugar de implementaciones de árbol...