Arbol rojo/negro
Páginas: 2 (399 palabras)
Publicado: 29 de junio de 2011
1. Introducción.
Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo almacena un bit adicional de información llamado color, el cual puede ser rojo o negro. Sobre este atributode color se aplican restricciones que resultan en un árbol en el que ningún camino de la raíz a una hoja es más de dos veces más largo que cualquier otro, lo cual significa que el árbol esbalanceado.
Cada nodo de un árbol rojo negro contiene la siguiente información: color, dato, hijo izquierdo, hijo derecho y padre. Si un hijo o el padre de un nodo no existe, el apuntador correspondientecontiene el valor NULO, el cual consideraremos como un nodo cuyo color es negro. En lo sucesivo nos referiremos a los nodos distintos a las hojas (NULO) como nodos internos del árbol y a las hojas y alpadre de la raíz como nodos externos.
2. Características Principales.
- Un árbol rojo-negro es un árbol de búsqueda binario y cada uno de sus nodos están coloreados rojo y negro
- La raíz es decolor negra
- Un nodo rojo puede tener solo hijos negros
- Cada camino simple desde un nodo a una hija descendiente contiene el mismo numero de nodos negros, ya sea contando siempre los nodos negrosnulos o bien no contándolos nunca. También es llamada “propiedad del camino” y por tanto el camino no puede tener dos rojos seguidos.
- El camino largo desde la raíz hasta una hoja no es mas largoque 2 veces el camino mas corto desde la raíz del árbol hasta una hija en dicho árbol. El resultado es que dicho árbol esta aproximadamente equilibrado.
3. Ventajas y desventajas.
Los árbolesrojo-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 hace valiosos en aplicaciones sensibles al tiempo como lasaplicaciones en tiempo real, sino que además son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peor caso.
Los árboles rojo-negro son particularmente valiosos en...
Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo almacena un bit adicional de información llamado color, el cual puede ser rojo o negro. Sobre este atributode color se aplican restricciones que resultan en un árbol en el que ningún camino de la raíz a una hoja es más de dos veces más largo que cualquier otro, lo cual significa que el árbol esbalanceado.
Cada nodo de un árbol rojo negro contiene la siguiente información: color, dato, hijo izquierdo, hijo derecho y padre. Si un hijo o el padre de un nodo no existe, el apuntador correspondientecontiene el valor NULO, el cual consideraremos como un nodo cuyo color es negro. En lo sucesivo nos referiremos a los nodos distintos a las hojas (NULO) como nodos internos del árbol y a las hojas y alpadre de la raíz como nodos externos.
2. Características Principales.
- Un árbol rojo-negro es un árbol de búsqueda binario y cada uno de sus nodos están coloreados rojo y negro
- La raíz es decolor negra
- Un nodo rojo puede tener solo hijos negros
- Cada camino simple desde un nodo a una hija descendiente contiene el mismo numero de nodos negros, ya sea contando siempre los nodos negrosnulos o bien no contándolos nunca. También es llamada “propiedad del camino” y por tanto el camino no puede tener dos rojos seguidos.
- El camino largo desde la raíz hasta una hoja no es mas largoque 2 veces el camino mas corto desde la raíz del árbol hasta una hija en dicho árbol. El resultado es que dicho árbol esta aproximadamente equilibrado.
3. Ventajas y desventajas.
Los árbolesrojo-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 hace valiosos en aplicaciones sensibles al tiempo como lasaplicaciones en tiempo real, sino que además son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peor caso.
Los árboles rojo-negro son particularmente valiosos en...
Leer documento completo
Regístrate para leer el documento completo.