MAS ARBOLES

Árbol rojo-negro 

Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978. Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol.
Sería ideal exponer la especificación algebraica completa de este tipo abstracto de datos (TAD) escrita en algún lenguaje de especificación de TADs como podría ser Maude; sin embargo, la complejidad de la estructura hace que la especificación quede bastante ilegible, y no aportaría nada. Por tanto, explicaremos su funcionamiento con palabras, esquemas e implementaciones de funciones en el lenguaje de programación C.

Propiedades 

1. Todo nodo es o bien rojo o bien negro.
2. La raíz es negra.
3. Todas las hojas son negras (las hojas son los hijos nulos).
4. Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").
5. Cada camino simple desde un nodo a una hoja descendiente contiene el mismo número de nodos negros, ya sea contando siempre los nodos negros nulos, o bien no contándolos nunca (el resultado es equivalente). También es llamada "Propiedad del camino", y al número de nodos negros de cada camino, que es constante para todos los caminos, se le denomina "Altura negra del árbol", y por tanto el cámino no puede tener dos rojos seguidos.
6. El camino más largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol. El resultado es que dicho árbol está aproximadamente equilibrado.

 

Operaciones

 -Rotación

Para conservar las propiedades que debe cumplir todo árbol rojo-negro, en ciertos casos de la inserción y la eliminación será necesario reestructurar el árbol, si bien no debe perderse la ordenación relativa de los nodos. Para ello, se llevan a cabo una o varias rotaciones, que no son más que reestructuraciones en las relaciones padre-hijo-tío-nieto.
Las rotaciones que se consideran a continuación son simples; sin embargo, también se dan las rotaciones dobles.

void

rotar_izda(struct node *p)

{

        struct node *aux;

        aux = p;

        p = p->dcho;

        aux-> dcho = p->izdo;

        p->izdo = aux;

}

void

rotar_dcha(struct node *p)

{

        struct node *aux;

        aux = p;

        p = p->izdo;

        aux->izdo = p->dcho;

        p->dcho = aux,

}

 

-Búsqueda

La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol.
La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) en general, y en un árbol rojo negro en particular, se puede realizar de dos formas, iterativa o recursiva.

Version recursiva

int buscar(tArbol *a, int elem)

{

  if (a == NULL)

    return 0;

  else if (a->clave < elem)

    return buscar(a->hDerecho, elem);

  else if (a->clave > elem)

    return buscar(a->hIzquierdo, elem);

  else

    return 1;

}

Inserción

La inserción comienza añadiendo el nodo como lo haríamos en un árbol binario de búsqueda convencional y pintándolo de rojo. Lo que sucede después depende del color de otros nodos cercanos. El término tío nodo será usado para referenciar al hermano del padre de un nodo, como en los árboles familiares humanos. Conviene notar que:

• La propiedad 3 (Todas las hojas, incluyendo las nulas, son negras) siempre se cumple.
• La propiedad 4 (Ambos hijos de cada nodo rojo son negros) está amenazada solo por añadir un nodo rojo, por repintar un nodo negro de color rojo o por una rotación.
• La propiedad 5 (Todos los caminos desde un nodo dado hasta sus nodos hojas contiene el mismo número de nodos negros) está amenazada solo por repintar un nodo negro de color rojo o por una rotación.

Los nodos tío y abuelo pueden ser encontrados por las siguientes funciones:

struct node *

abuelo(struct node *n)

{

        if ((n != NULL) && (n->padre != NULL))

                return n->padre->padre;

        else

                return NULL;

}

struct node *

tio(struct node *n)

{

        struct node *a = abuelo(n);

        if (n->padre == a->izdo)

                return a->dcho;

        else

                return a->izdo;

}

Árbol-B

En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

-Búsqueda

La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.
Procedimiento:

1. Situarse en el nodo raíz.
2. (*) Comprobar si contiene la clave a buscar.
   1. Encontrada fin de procedimiento.
   2. No encontrada:
      1. Si es hoja no existe la clave.
      2. En otro caso el nodo actual es el hijo que corresponde:
         1. La clave a buscar k < k1: hijo izquierdo.
         2. La clave a buscar k > ki y k < ki+1 hijo iésimo.
         3. Volver a paso 2(*). 

-Inserción

Todas las inserciones se hacen en los nodos hoja.

1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
   1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
   2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
   3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
   
   

-Eliminación

La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.

• localizar y eliminar el elemento, y luego corregir, o
• hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando

Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento, el número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.

-Bibliografia
Arbol rojo-negro
Arbol-B