Hay muchas preguntas en torno a los árboles rojo-negro, pero ninguno de ellos responde cómo funcionan. ¿Por qué se llama rojo-negro? ¿Cómo mantiene esto equilibrado el árbol (aumentando así el rendimiento sobre un árbol de búsqueda binaria normal desequilibrado)? Solo estoy buscando una visión general de cómo y por qué funciona.¿Cómo funciona un árbol rojo-negro?
Respuesta
Para búsquedas y recorridos, es lo mismo que cualquier árbol binario.
Para inserciones y eliminaciones, se aplican algoritmos más sofisticados que tienen como objetivo garantizar que el árbol no pueda estar demasiado desequilibrado. Esto garantiza que todas las operaciones de elementos individuales siempre se ejecutarán en el peor tiempo O (log n), mientras que en un árbol binario simple el árbol binario puede desequilibrarse tanto que es efectivamente una lista enlazada, dando O (n) el peor rendimiento de caso para cada operación de un solo elemento.
La idea básica del árbol rojo-negro es imitar un B-tree con hasta 3 claves y 4 hijos por nodo. B-trees (o variaciones como árboles B +) se utilizan principalmente para índices de bases de datos y para datos almacenados en el disco duro.
Cada nodo de árbol binario tiene un "color" - rojo o negro. Cada nodo negro es, en la analogía del árbol B, la raíz del subárbol para el subárbol que se ajusta dentro de ese nodo B-tree. Si este nodo tiene hijos rojos, también se los considera parte del mismo nodo B-tree. De modo que es posible (aunque no se hace en la práctica) convertir un árbol rojo-negro en un árbol B y volver, conservando (la mayoría) la estructura. La única anomalía posible es que cuando un nodo de árbol B tiene dos claves y tres hijos, puede elegir qué clave va en el nodo negro en el árbol rojo-negro equivalente.
Por ejemplo, con árboles rojo-negro, cada línea desde la raíz a la hoja tiene el mismo número de nodos negros. Esta regla se deriva de la regla del árbol B que dice que todos los nodos hoja tienen la misma profundidad. Aunque esta es la idea básica de la que se derivan árboles rojo-negro, los algoritmos utilizados en la práctica para inserciones y eliminaciones se modifican para aplicar todas las reglas del árbol B (puede haber una excepción menor, se me olvida) actualizaciones, pero están diseñados para la forma de árbol binario. Esto significa que al hacer una inserción o eliminación de un árbol rojo-negro puede dar una estructura diferente para el resultado de la que esperaría comparar al hacer la inserción o eliminación del árbol B.
Para obtener más información, siga el Wikipedia link que ya proporcionó MigDus.
Un árbol rojo-negro es un árbol binario ordenado donde cada vértice es de color rojo o negro. La intuición es que un vértice rojo debe verse a la misma altura que su elemento primario (es decir, un borde a un vértice rojo se considera "horizontal" en lugar de "descendente").
[I no creen la entrada de Wikipedia aclara este punto.]
las normas habituales para árboles rojo-negro que requieren un vértice rojo Nunca apunte a otro vértice rojo. Esto significa que los posibles arreglos de vértices para cualquier subárbol enraizado con un vértice negro (bbb, bbr, rbb, rbr - para [niño izquierdo] [raíz] [niño derecho]) corresponden a 234 árboles.
Buscar en un árbol rojo-negro es lo mismo que buscar en un árbol binario ordinario. La inserción y la eliminación son similares, excepto que puede ser necesaria una rotación de "reparación" en algún momento para preservar la invariante roja-negra.
¡Salud!
"La intuición es que un vértice rojo debería verse a la misma altura que su elemento primario (es decir,, un borde a un vértice rojo se considera "horizontal" en lugar de "descendente"). "* ¡Momento de la bombilla, gracias! * –
- 1. ¿Hay algún árbol B o sitios que muestren visualmente cómo funciona un árbol B?
- 2. ¿Cómo implementar un árbol binario?
- 3. Cómo crear un árbol binario
- 4. ¿Cómo construir un árbol y?
- 5. Construir un árbol
- 6. Cómo eliminar elementos de un árbol
- 7. ¿Cómo se limpia un árbol en ExtJs?
- 8. ¿Cómo manipulo un árbol de objetos inmutables?
- 9. ¿Cómo hacer un árbol en C++?
- 10. Cómo construir un árbol de sintaxis abstracta
- 11. Cómo dibujar (editar) un árbol git ascii
- 12. Cómo decorar un árbol en Haskell
- 13. Árbol binario del árbol general
- 14. balanceando un árbol AVL (C++)
- 15. ¿Cómo funciona un depurador?
- 16. ¿Cómo funciona un ensamblador?
- 17. ¿Cómo funciona un ActionListener?
- 18. ¿Cómo funciona un enlace?
- 19. Encontrar un bucle en un árbol binario
- 20. SimpleXML: agregar un árbol a otro
- 21. Árbol AVL contra árbol B
- 22. Encontrar un subárbol en un árbol CakePHP
- 23. Cómo degradar un árbol de subversión de v1.7 a v1.6?
- 24. ¿Cómo buscar un nodo en un árbol y devolverlo?
- 25. Cómo encontrar un nodo en un árbol con JavaScript
- 26. Cómo elegir un nodo aleatorio de un árbol
- 27. Representando un árbol en Clojure
- 28. Atravesando un árbol binario recursivamente
- 29. ¿Qué es un árbol B *?
- 30. Generando un árbol en Excel
Esta respuesta debería ser aceptada, creo. –