 Inicio Linux Programación Cursos Programas Artículos Spectrum Varios El Autor |
 |
 |
 |
T.A.D. NO LINEALES
ARBOLES
Son unas de las estructuras más importantes en las ciencias de la computación. Proporcionan una representación natural para muchas clases de datos y son útiles para resolver una gran variedad de problemas algorítmicos.Un árbol con tipo base T es un conjunto de uno o más nodos que cumplen:
a). Existe un nodo especial llamado raíz considerado el inicio del árbol.
b). Los nodos restantes están separados en en n>=0 conjuntos distintos, cada uno de los cuales son a su vez un árbol (subárboles).
(1)
/ \
(2) (3)
/ | \
(4) (5) (6)
Constituyentes del árbol:
> Nodos: elementos del árbol que almacenan información.
> Conexiones: expresan las relaciones entre los nodos.
Estructura del árbol:
> Nodo raíz: nodo más alto de la jerarquía, a partir del cual están conectados los demás.
> Nodo terminal u hoja: aquel que no contiene ningún subárbol.
> Hijos de un nodo: Aquellos nodos conectados a un nodo mediante enlace directo hacia abajo.
> Descendientes: Nodos que encontramos al movernos hacia abajo en un árbol.
> Ascendientes: Nodos que encontramos al movernos hacia arriba en un árbol.
> Padre de un nodo: Antecesor directo de un nodo.
> Hermanos: nodos hijos del mismo padre.
> Nodos internos: aquellos que tienen a su vez padre e hijos (los no terminales).
Topología del árbol:
> Grado de un nodo: número máximo de hijos del nodo.
> Grado de un árbol: grado máximo de los nodos del árbol.
> Camino entre 2 nodos: sucesión de nodos a visitar (único) para llegar desde un nodo a otro.
> Nivel de un nodo: Es la longitud del camino desde el nodo raíz (nivel 0) hasta ese nodo.
> Altura o profundidad de un árbol: nivel máximo del árbol más uno.
> Arbol vacío: árbol sin nodos ni conexiones.
> Bosque: conjunto de n>=0 árboles disjuntos.
ARBOLES BINARIOS
Son árboles de grado 2 (cada nodo tiene, como máximo, 2 hijos). Es o bien un árbol vacío o un nodo que tiene subárboles izquierdo y/o derecho.
(1)
/ \
(2) (3)
/ \
(4) (5)
> El número de nodos en un nivel i del árbol es como máximo (2 elevado a i).> El número máximo de nodos de un árbol de altura k es (2 elevado a k)-1.
> Definimos un árbol lleno como aquel cuyos nodos internos llenan completamente todos los niveles, excepto quizás el último.
> Definimos un árbol binario completo (ABC) como un A.B.lleno pero con sus hojas dispuestas de tal manera que las hojas del nivel más bajo están situadas tan a la izquierda como sea posible.
Representación de árboles binarios completos mediante vectores:
Sea v[i] un vector que represente el árbol mediante el siguiente orden:
---------------------------------
| | | | | | | | |
---------------------------------
v 0 1 2 3 4 5 6 7
Hijo izquierdo de v[i] = v[2i] si 2i <= n
Hijo derecho de v[i] = v[2i+1] si 2i+1 <= n
Padre de v[i] = v[i/2] si i > 1
Nodo raíz = v[1]
( v[i] es una hoja si 2i > n )
Representación de árboles binarios completos mediante estructuras enlazadas:
typedef struct nodoarbolbin
{
tipo_info clave;
struct nodoarbolbin *izq;
struct nodoarbolbin *der;
} NODOARBOL;
NODOARBOL *arbol;
Métodos de recorrido del árbol binario:
Entendemos por recorrer un árbol visitar (y procesar) cada uno de los nodos que lo componen, una sola vez y en un determinado orden. Existen 3 métodos, los cuales difieren en el órden en que procesamos los nodos, y que comunmente a la hora de entrar en nuevos nodos comienzan por el subárbol izquierdo:
Método preorden:
a). Visitar el nodo (y procesarlo).
b). Recorrer el subarbol izq en preorden
c). Recorrer el subarbol der en preorden.
Método inorden:
a). Recorrer el subarbol izq en inorden
b). Visitar el nodo (y procesarlo).
c). Recorrer el subarbol der en inorden.
Método postorden:
a). Recorrer el subarbol izq en postorden
b). Recorrer el subarbol der en postorden.
c). Visitar el nodo (y procesarlo).
Ejemplo:
void PreOrden( NODOARBOL *nodo)
{
if( nodo!=NULL)
{
procesar(nodo);
PreOrden(nodo->izq);
PreOrden(nodo->der);
}
}
Coste temporal = O(n) (n=numnodos)procesar()=udad tº
Coste espacial en pila = O(log n) = O(h)
Las operaciones sobre A.B. dependen del tipo de árbol que usemos, el tipo de clave, etc. De modo que las operaciones de inserción, búsqueda, son diferentes para cada tipo de árbol (sólo coinciden Crear y ArbolVacio).
Árboles binarios de búsqueda:
Son árboles binarios que cumplen lo siguiente:
> Todos los nodos están identificados por un campo clave, y no hay 2 elementos con la misma clave.
> Dado un cierto nodo de clave 'x', todos los nodos del subarbol izq tienen una clave <x, y todos los nodos del subarbol der tienen una clave mayor que x.
> Los subárboles izq y der son a su vez árboles binarios de búsqueda.
(10)
/ \
(6) (20)
/ \
(1) (9)
Para encontrar un dato en un ABB se puede utilizar una función como la siguiente:
NODOARBOL *BuscarABB( tipoinfo x, NODOARBOL nodo ) /* version recursiva */
{
if( nodo == NULL ) return(NULL);
if( x==nodo->clave ) return( nodo);
else
{
if( x<nodo->clave ) return(BuscarABB( x, nodo->izq);
else return(BuscarABB( x, nodo->der);
}
}
o bien:
NODOARBOL *BuscarABB( tipoinfo x, NODOARBOL nodo ) /* version iterativa */
{
NODOARBOL *nd;
nd = nodo;
while( nd!=NULL && nd->clave != x )
{
if( x < nd->clave ) nd = nd->izq;
else nd = nd->der;
}
}
ARBOLES AVL
Un árbol AVL (Adelson-Velskii y Landis) es un árbol binario de búsqueda equilibrado. Un árbol es equilibrado si los subárboles izquierdo y derecho de cualquier nodo tienen alturas que difieren como mucho en 1. Esta condición asegura que la profundad del árbol sea log(n), siendo n el nº de nodos del árbol. Para mantener un árbol equilibrado se definen unas operaciones llamadas rotaciones tras la inserción o eliminación de elementos.
ARBOL AVL:
(1)
/ \
(2) (3)
/ \
(4) (5)
ARBOL NO AVL:
(1)
\
(2)
\
(3)
LOS MONTÍCULOS
Un montículo es un ABC en el que se establece una relación de orden, de tal manera que se cumple que para cada nodo de éste, ninguno de sus 2 hijos tiene un valor mayor que él (montículo de máximos). El montículo de mínimos es aquel en que cada nodo no puede tener hijos con valores menores que él.
MONTICULO DE MAXIMOS:
(13)
/ \
(5) (10)
/ \
(1) (3)
MONTICULO DE MINIMOS:
(1)
/ \
(4) (3)
/ \
(6) (7)
ARBOLES N-ARIOS
Un árbol n-ario o de grado n es un árbol cuyos nodos tienen n o menos hijos, siendo n cualquier valor entero positivo. Su representación puede hacerse de 2 maneras diferentes:
(1)
/ \
(2) (3)
/ | \
(4) (3) (5)
A) mediante vectores de punteros para referenciar a los hijos del nodo:
#define MAX_HIJOS 10
struct nodoarboln
{
tipo_info clave;
struct nodoarboln *hijo[MAXHIJOS];
} NODOARBOL;
B). Manteniendo todos los hijos en una lista lineal (donde tendremos una referencia al primer hijo, y cada hijo una referencia a su hermano siguiente), una estructura mucho más flexible y que aprovecha mejor la memoria:
struct nodoarboln
{
tipo_info clave;
struct nodoarboln *hijo;
struct nodoarboln *hermanos;
} NODOARBOL;
GRAFOS
Ver teoría de grafos en cualquier libro sobre el tema (es bastante complicado dibujar grafos en ascii :).