Preguntas sobre los árboles de búsqueda, una clase de estructuras de datos utilizadas para almacenar datos ordenados para un acceso eficiente.
Parece que donde quiera que mire, las estructuras de datos se están implementando utilizando árboles rojo-negros ( std::seten C ++, SortedDictionaryen C #, etc.) Después de haber cubierto los árboles (a, b), rojo-negro y AVL en mi clase de algoritmos, esto es lo que obtuve (también de preguntar a...
Supongamos la siguiente definición de un árbol rojo-negro: Es un árbol de búsqueda binario. Cada nodo es de color rojo o negro. La raíz es negra. Dos nodos conectados por un borde no pueden ser rojos al mismo tiempo. Aquí debería haber una buena definición de una hoja NIL, como en wiki. La hoja...
Intuitivamente, los "árboles equilibrados" deben ser árboles donde los subárboles izquierdo y derecho en cada nodo deben tener "aproximadamente el mismo" número de nodos. Por supuesto, cuando hablamos de que los árboles rojo-negros * (ver definición al final) están equilibrados, en realidad...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
No entiendo bien por qué la rotación en la estructura de datos del árbol de separación está teniendo en cuenta no solo al padre del nodo de calificación, sino también al abuelo (operación zig-zag y zig-zig). ¿Por qué no funcionaría lo siguiente? A medida que insertamos, por ejemplo, un nuevo nodo...
En una pregunta anterior , había una definición de árboles con peso equilibrado y una pregunta sobre árboles rojo-negros. Esta pregunta es para hacer la misma pregunta, pero para los árboles AVL . La pregunta es, dada la definición de árboles balanceados como en la otra pregunta,μμ\mu ¿Hay...
Últimamente he estado leyendo un poco de literatura y he encontrado algunas estructuras de datos bastante interesantes. He investigado varios métodos diferentes para reducir el tiempo de actualización a peor tiempo de actualización [1-7].O ( 1 )O(1)\mathcal{O}(1) Recientemente comencé a buscar...
Tengo una tarea en la que necesito hacer uso de un árbol de búsqueda binario y modificarlo para que se ordene a sí mismo de modo que los elementos a los que se accede más (tengan una prioridad más alta) estén en la parte superior del árbol, siendo la raíz el nodo más visitado . El profesor me dio...
Una pregunta común de la entrevista es dar un algoritmo para determinar si un árbol binario dado está equilibrado en altura (definición de árbol AVL). Me preguntaba si podemos hacer algo similar con los árboles rojo-negros. Dado un árbol binario arbitrario sin color (con nodos NULL), ¿existe un...
En la Introducción a los algoritmos de Cormen et al. , La sección 15.3 Elementos de la programación dinámica explica la memorización de la siguiente manera: Un algoritmo recursivo memorizado mantiene una entrada en una tabla para la solución de cada subproblema. Cada entrada de la tabla...
Tengo la siguiente pregunta, pero no tengo respuesta para esto. Agradecería si mi método es correcto: P. Cuando se busca el valor clave 60 en un árbol de búsqueda binario, los nodos que contienen los valores clave 10, 20, 40, 50, 70, 80, 90 se atraviesan, no necesariamente en el orden dado....
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...
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...
¿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
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...
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/...
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 ....
Un SkipList proporciona los mismos límites para la búsqueda que un árbol equilibrado con la ventaja de que no es necesario reequilibrar. Dado que SkipList se construye utilizando lanzamientos aleatorios de monedas, estos límites solo se mantienen mientras la estructura de SkipList esté...
¿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...
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...