programacion

Páginas: 3 (653 palabras) Publicado: 24 de octubre de 2013
ARBOLES ROJOS Y NEGROS

Los arboles rojos y negro son arboles binarios de búsqueda donde lo que cambia es que poseen una propiedad más la cual es un color que puede ser rojo a negro.
Losárboles Rojo-Negro cumplen las siguientes 4 propiedades:
1) Todo nodo es rojo o negro.
2) Todo nodo externo es negro.
3) Condición roja: Si un nodo es rojo, ambos hijos son negros.
4) Condición negra:Todo camino desde la raíz hasta una hoja contiene el mismo número de nodos negros.

Ejemplo de un árbol rojo y negro sin nodos externos y uno con sus nodos externos:






OPERACIONES BACICASDE LOS ARBOLES ROJOS Y NEGROS

1. INSERCION:
Caso 1: El padre del nodo es de color negro. En este caso no es necesario realizar ninguna modificación o arreglo del árbol:



Caso 2: El padredel nodo es la raíz del árbol y es de color rojo y su hijo también es de color rojo esto se resuelve cambiando de color la raíz:



Caso 3: El padre del nodo es rojo y no es la raíz si se presentaeste caso es necesario evaluar tres sub casos los cuales son los siguientes:

Caso 3.1: El hijo que no es la raíz del árbol también es rojo se resuelve cambiando los colores de la raíz de árbol, y desus hijos:










Caso 3.2: El nodo derecho de la raíz es negro, y el nodo de la izquierda de la raíz tiene un hijo izquierdo se resuelve con una rotación simple a la derecha de laraíz y cambiando de color el nodo a la izquierda de la raíz y la raíz:


Caso 3.3: El nodo derecho de la raíz es negro, y el nodo de la izquierda de la raíz tiene un hijo derecho se resuelve con unarotación simple a izquierda de nodo izquierdo de la raíz y con esto llegamos al mismo que el caso 3.2 por lo que se resuelve de la misma manera:




2. BUSQUEDA:

En los arboles rojos y negrosse realiza la búsqueda de la misma manera que en los arboles binarios de por lo que se realiza mirando desde la raíz primero evaluamos si la raíz es el nodo del árbol que estamos buscando si esto...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Programación
  • Programacion
  • Programacion
  • Programación
  • Programacion
  • Programacion
  • Programacion
  • Programacion

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS