ÁRBOL

El árbol es como un tipo de grafo cíclico, conexo y no dirigido.

Las estructuras tipo árbol se usan principalmente para representar

datos con una relación jerárquica entre sus elementos. Un árbol con

ningún nodo es un árbol nulo; no tiene raíz. Una estructura vacía o

un elemento o clave de información (nodo) más un número finito de

estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho

número de estructuras es inferior o igual a dos, se tiene un árbol

binario. Es por tanto, una estructura no secuencial.

NODO

Un nodo es un punto de intersección o unión de varios elementos

que confluyen en el mismo lugar.

Definición:

Árboles Binarios Un árbol binario es un conjunto finito de cero o más

nodos tales que: Existe un nodo denominados raíz del

árbol

Cada nodo puede tener 0, 1 o 2 subárboles, conocidos

como subárbol izquierdo y subárbol derecho.

Tipos de árboles binarios

• Un árbol binario es un árbol con raíz en el que cada

nodo tiene como máximo dos hijos.

• Un árbol binario lleno es un árbol en el que cada nodo

tiene cero o dos hijos.

• Un árbol binario perfecto es un árbol binario lleno en el

que todas las hojas están a la misma profundidad

(distancia desde la raíz).

Arboles binarios en c.

Un árbol binario puede declararse de varias maneras. Algunas de

ellas son:

Estructura con manejo de memoria dinámica, siendo punto A el

puntero que apunta al árbol de tipo tArbol:

typedef struct tArbol

{

int clave;

tArbol hIzquierdo, hDerecho;

} tArbol;

tArbol árbol[NUMERO_DE_NODOS];

Recorridos sobre árboles binarios

Recorridos en profundidad

El método de este recorrido es tratar de encontrar de la cabecera a la

raíz en nodo de unidad binaria.

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción sobre el nodo actual y

posteriormente se trata el subárbol izquierdo y cuando se haya

concluido, el subárbol derecho. Otra forma para entender el recorrido

con este método sería seguir el orden: nodo raíz, nodo izquierda, nodo

derecha. el detalle de este es que si no encuentra dara un arbol vacio y

lo dara por terminado, en el otro caso viajará de izq a der para

determinar que si se pueda seguir.

Recorridos en amplitud (o por

niveles).

En este caso el recorrido se realiza en orden por los

distintos niveles del árbol. Así, comienza tratando el

nivel 1, que sólo contiene el nodo raíz,

seguidamente el nivel 2, el 3 y así sucesivamente.

Búsqueda: simplemente efectúa un recorrido comparando el

Elemento que deseas encontrar contra cada uno de los

Elementos en los Arreglos.

Recorrido en postorden.

En este caso se trata primero el subárbol izquierdo,

después el derecho y por último el nodo actual. Otra forma

para entender el recorrido con este metodo seria seguir el

orden: nodo izquierda, nodo derecha, nodo raíz.

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo,

después el nodo actual y por último el subárbol derecho.

Otra forma para entender el recorrido con este metodo

seria seguir el orden: nodo izquierda,nodo raíz,nodo

derecha.viaje a través del Árbol Binario desplegando el

Contenido en el Nodo Izquierdo después la Raíz y

finalmente viaja a través del Nodo Derecho.

Los árboles binarios

• Deben de tener un número de hijos predefinidos.

• Para mantener el orden predefinido, cuando se elimina un nodo se junta o se parte en el nodo siguiente.

• Requiere que todas las hojas tengan la misma altura.

• La información se guarda en las hojas o también llamadas páginas.

• Los nodos hojas se encuentran unidos entre sí como una lista enlazada y se realiza una búsqueda secuencial.

• Cada página tiene como máximo N nodos.

• Cada página excepto la raíz tiene como mínimo n/2 nodos.

• Cada pagina es bien una página hoja o bien tiene mt1 dependientes(número de nodos que contiene)

Árboles AVL Es un tipo especial de árbol binario ideado por

los matemáticos rusos Adelson-Velskii y Landis

(de los cuales toma ese nombre). Fue el primer

árbol de búsqueda binario auto-balanceable que

se ideó.

Definición de un árbol AVL

Un árbol vacío es un árbol avl.

es un árbol binario de búsqueda en el que para

cada nodo, las alturas de sus subárboles

izquierdo y derecho no difieren en más de 1. a

cada nodo de un árbol AVL se le asocia un

factor de Balance, el cual es izquierdo alto, igual

o derecho alto, respectivamente, según que el

subárbol izquierdo tengauna altura mayor, igual o

menor que la del subárbol derecho. La

denominación de árbol AVL viene dada por los

creadores de tal estructura (Adelson-Velskii y

Landis).

Factor de equilibrio:

Cada nodo, además de la información que se pretende

almacenar, debe tener los dos punteros a los árboles

derecho e izquierdo, igual que los AB, y además un

miembro nuevo: el factor de equilibrio.

El factor de equilibrio es la diferencia entre las alturas

del árbol derecho y el izquierdo: FE = altura subárbol derecho - altura

subárbol izquierdo;

Por definición, para un árbol AVL, este valor debe ser -

1, 0 ó 1.

Operaciones con los arboles AVL:

Rotaciones

El reequilibrado se produce de abajo hacia arriba sobre los

nodos en los que se produce el desequilibrio. Pueden darse

dos casos: rotación simple o rotación doble; a su vez ambos

casos pueden ser hacia la derecha o hacia la izquierda.

Extracción

El procedimiento de borrado es el mismo que en el caso de

árbol binario de búsqueda. La diferencia se encuentra en el

proceso de reequilibrado posterior. El problema de la

extracción puede resolverse en O (log n) pasos. Una

extracción trae consigo una disminución de la altura de la

rama donde se extrajo y tendrá como efecto un cambio en

el factor de equilibrio del nodo padre de la rama en cuestión,

pudiendo necesitarse una rotación.

Rotación Simple a la Derecha:

Se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el

derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo

tenga una FE de -1, es decir, que esté cargado a la izquierda.

1.Pasamos el subárbol derecho del nodo Q

como subárbol izquierdo de P. Esto

mantiene el árbol como ABB, ya que todos

los valores a la derecha de Q siguen estando

a la izquierda de P.

2.El árbol P pasa a ser el subárbol derecho

del nodo Q.

3.Ahora, el nodo Q pasa a tomar la posición

del nodo P, es decir, hacemos que la entrada

al árbol sea el nodo Q, en lugar del nodo P.

Previamente, P puede que fuese un árbol

completo o un subárbol de otro nodo de

menor altura.

Rotación Simple a la

Izquierda: Se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el

izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho

tenga una FE de 1, es decir, que esté cargado a la derecha.

1.Pasamos el subárbol izquierdo del

nodo Q como subárbol derecho de P.

Esto mantiene el árbol como ABB, ya

que todos los valores a la izquierda de Q

siguen estando a la derecha de P.

2.El árbol P pasa a ser el subárbol

izquierdo del nodo Q.

3.Ahora, el nodo Q pasa a tomar la

posición del nodo P, es decir, hacemos

que la entrada al árbol sea el nodo Q, en

lugar del nodo P. Previamente, P puede

que fuese un árbol completo o un

subárbol de otro nodo de menor altura.

Rotación Doble a la Derecha:

Se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el

derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo

tenga una FE de 1, es decir, que esté cargado a la derecha.

1.Haremos una

rotación simple de Q a

la izquierda.

2.Después, haremos

una rotación simple de

P a la derecha.

Rotación Doble a la Izquierda:

Se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el

izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho

tenga una FE de -1, es decir, que esté cargado a la izquierda. Se trata del caso

simétrico del anterior.

1.Haremos una rotación

simple de Q a la

derecha.

2.Después, haremos una

rotación simple de P a la

izquierda.

Thanks,ありがとう, Danke,Gracias