Arbol Y Grafo

ÁRBOL

Lo Podemos definir brevemente de dos maneras:

• Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

• Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

GRADO: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.

TIPOS

• Árbol rojo-negro

Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables (como por ejemplo números).

En los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora de implementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas. Así,todas las referencias de los nodos internos a las hojas van a parar al nodo centinela.

En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O(log n).

Ejemplo de árbol rojo-negro

• Árboles B

En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en los cuales cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

• Árboles Multicamino O Árboles Multirrama

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

• A está vacío

• Cada nodo de A muestra la siguiente estructura: [nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]

nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1

Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves

Clavei, son los valores de clave, pudiendo ser: 1 <= i <= nClaves

• Clavei < Clavei+1

• Cada valor de clave en el subárbol Enlacei es menor que el valor de Clavei+1

• Los subárboles Enlacei, donde 0 <= i <= nClaves, son también árboles m-caminos.

Existen muchas aplicaciones en las que el volumen de la información es tal, que los datos no caben en la memoria principal y es necesario almacenarlos, organizados en archivos, en dispositivos de almacenaminento secundario. Esta organización de archivos debe ser suficientemente adecuada como para recuperar los datos del mismo en forma eficiente

• Árbol binario de búsqueda

Un árbol binario de búsqueda también llamados BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.

Descripción

Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma:

Todo árbol vacío es un árbol binario de búsqueda.

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:

• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo

almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario

de búsqueda.

• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo

almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario

de búsqueda.

Un árbol binario de búsqueda de tamaño 9 y profundidad 3, con raíz 8 y hojas 1, 4, 7 y 13

Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.

Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.

El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.

• Árbol de Fibonacci

Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci.

El árbol de Fibonacci se define de la siguiente manera:

• El árbol nulo (no contiene ningún nodo) es de orden 0.

• El árbol que consta

...