Arboles rojos y negros
Páginas: 3 (577 palabras)
Publicado: 12 de septiembre de 2014
ARBOLES ROJO Y NEGROS
Un árbol rojo negro es un árbol binario donde cada nodo tiene también un atributo de color, cuyo valor puede ser o rojo o negro. Las hojas de un árbol rojo negro sonirrelevantes y no tienen datos.
Para que un árbol binario ordenado sea considerado como un árbol rojo negro debe cumplir con las siguientes propiedades:
La raíz del árbol es negra.
Los hijos de unnodo rojo son negros.
Las hojas del árbol son negras.
Todas las ramas del árbol (caminos desde la raíz hasta una hoja) tienen el mismo número de nodos negros.
Este tipo de estructuras sirven parael almacenamiento de elementos entre los que exista una relación de orden. La complejidad de la búsqueda en los árboles rojo negro es O(log2 n).
En el caso concreto de implementación enCupi2Collections esta estructura fue desarrollada para soportar objetos de cualquier tipo, siempre que la clase a la que pertenecen implemente la interface Comparable necesaria para la inserción de los elementos deforma ordenada.
Ejemplo:
Usos y ventajas
Los árboles rojo-negro ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda. No es esto únicamente lo que los hacevaliosos en aplicaciones sensibles al tiempo como las aplicaciones en tiempo real, sino que además son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peorcaso. Por ejemplo, muchas estructuras de datos usadas en geometría computacional pueden basarse en árboles rojo-negro.
El árbol AVL es otro tipo de estructura con O(log n) tiempo de búsqueda,inserción y borrado. Está equilibrado de forma más rígida que los árboles rojo-negro, lo que provoca que la inserción y el borrado sean más lentos pero la búsqueda y la devolución del resultado de la mismamás veloz.
Los árboles rojo-negro son particularmente valiosos en programación funcional, donde son una de las estructuras de datos persistentes más comúnmente utilizadas en la construcción de...
Un árbol rojo negro es un árbol binario donde cada nodo tiene también un atributo de color, cuyo valor puede ser o rojo o negro. Las hojas de un árbol rojo negro sonirrelevantes y no tienen datos.
Para que un árbol binario ordenado sea considerado como un árbol rojo negro debe cumplir con las siguientes propiedades:
La raíz del árbol es negra.
Los hijos de unnodo rojo son negros.
Las hojas del árbol son negras.
Todas las ramas del árbol (caminos desde la raíz hasta una hoja) tienen el mismo número de nodos negros.
Este tipo de estructuras sirven parael almacenamiento de elementos entre los que exista una relación de orden. La complejidad de la búsqueda en los árboles rojo negro es O(log2 n).
En el caso concreto de implementación enCupi2Collections esta estructura fue desarrollada para soportar objetos de cualquier tipo, siempre que la clase a la que pertenecen implemente la interface Comparable necesaria para la inserción de los elementos deforma ordenada.
Ejemplo:
Usos y ventajas
Los árboles rojo-negro ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda. No es esto únicamente lo que los hacevaliosos en aplicaciones sensibles al tiempo como las aplicaciones en tiempo real, sino que además son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peorcaso. Por ejemplo, muchas estructuras de datos usadas en geometría computacional pueden basarse en árboles rojo-negro.
El árbol AVL es otro tipo de estructura con O(log n) tiempo de búsqueda,inserción y borrado. Está equilibrado de forma más rígida que los árboles rojo-negro, lo que provoca que la inserción y el borrado sean más lentos pero la búsqueda y la devolución del resultado de la mismamás veloz.
Los árboles rojo-negro son particularmente valiosos en programación funcional, donde son una de las estructuras de datos persistentes más comúnmente utilizadas en la construcción de...
Leer documento completo
Regístrate para leer el documento completo.