Download presentacion equipo 8

Definición:
Á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.
Á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