AYUDANTÍA 5: ARBOLESCarlos Pulgar R.

Mail: carlos.pulgar@alumnos.usm.cl

Página Ayudantía: http://capulgar.wordpress.com/

Describir estructuras con algún tipo de jerarquía

Organizan información

Permiten localizar mas rápidamente la información

En informática se utilizan en distintos ámbitos Sistema de archivos: estructura de directorios y

subdirectorios con forma de árbol Esquema para el desarrollo de algoritmos

ARBOLES

Estructura jerárquica no lineal

Relaciones padre-hijo entre nodos

Def: Colección de elementos llamados NODOS, uno de los

cuales es la raíz, junto con una relación PADRE-HIJO, que coloca a todos los nodos en una estructura JERARQUICA.

Un Padre puede tener varios Hijos, pero un Hijo solo puede tener UN Padre.

Hay un único camino desde la raíz al nodo

ARBOLES (CONCEPTO)

TERMINOLOGÍA BÁSICA Raíz: único NODO sin padre. Nodo interno: tiene al menos un hijo Nodo hoja (externo): no tiene hijos Descendiente directo: hijo Descendientes: hijo, nieto… Subárbol : árbol formado por un nodo y sus descendientes Grado de un nodo: numero de descendientes directos Grado de un árbol: mayor grado de sus nodos Árbol binario: árbol de grado 2. Lista: árbol degenerado de grado 1. Profundidad de un nodo: número de predecesores Altura de un árbol: profundidad máxima de cualquier nodo

(numero máximo de los enlaces de las ramas del árbol) Rama: camino desde el nodo raíz a una hoja Nivel: numero de nodos desde la raíz al nodo Bosque: colección de dos o más árboles.

Árbol completo: si todo nodo no terminal tiene asociado exactamente el grado del árbol.

Árbol lleno: si esta completo y tiene todas sus hojas en el mismo nivel.

Casi lleno: es cuando el árbol esta lleno hasta el penúltimo nivel y las hojas que están en el ultimo nivel se encuentran lo mas a la izquierda posible.

A. Isomorfos: cuando dos árboles tienen la misma estructura, pero no necesariamente los mismos elementos.

A. Semejantes: son aquellos que poseen los mismos elementos, pero no necesariamente la misma estructura.

TERMINOLOGÍA BÁSICA

ÁRBOL BINARIO

Arbol de grado 2. Propiedades

n: número de nodos e: número de nodos hoja i: número de nodos internos h: altura del árbol

Recorrido de un árbol: InOrden -> ( I , R , D ) PreOrden -> ( R , I , D ) PostOrden -> ( I , D , R )

Ejercicio: En un árbol general, el recorrido en inorden se

puede definir recorriendo el primer hijo en inorden, seguido de la raíz y de los demás hijos en inorden. Indicar los recorridos en preorden, inorden y postorden del siguiente árbol general:

ÁRBOL BINARIO

ARBOLES DE BÚSQUEDA BINARIA (ABB)

Los valores de la izquierda son menores al padre y los de la derecha mayores

Al eliminar sube el mayor de la izquierda, o en algunos casos el menor de la derecha.

Ejercicio: Genere un ABB al insertar la secuencia de claves

enteras: 100, 29, 71, 82, 48, 39, 101, 22, 46, 17, 3, 20, 25, 10.

Altura del árbol? Hojas? Recorrido Postorden?

AVL

Si para todo nodo, se tiene una diferencia de a lo más 1 en la altura de los subárboles.

Se ocupa el Factor de Equilibrio, para comprobar la definición.

Si 1< F.E. < -1 se aplica rotación. Si F.E. < -1 rotar derecha. Si F.E. >1 rotar izquierda.

Si se elimina un nodo con dos hijos, el valor debería ser substituido por el menor de su hijo derecho.

ARBOLES 2-3

Todas las hojas se encuentran al mismo nivel Balanceado por altura Tienen 2 o 3 descendientes Al agregar se ordenan los 3 datos y sube el

del medio. En la eliminación, los nodos que quedan

vacios se fusionan con uno de sus hermanos para formar uno solo.

ARBOLES B Cada nodo puede tener mas de dos ramas. División del árbol en subarboles, llamados páginas. Un árbol B de orden “d” contiene a lo más “2d”

claves y “2d+1” punteros. Camino mas largo: logd(n) nodos, donde d es el orden

del árbol. Borrar:

Caso 1: la clave está en una página hoja Desplazar a la izquierda el resto de las claves

Caso 2: la clave no está en una página interior Lo mismo que el ABB

(fusión : izq primero, luego drch) Ejercicio:

Insertar en un Árbol B los siguientes elementos: 23, 45, 100, 5, 87.

ÁRBOL B* (DE ORDEN M)

Cada página tiene un máximo de M descendientes.

Todas las páginas, menos la raíz y las hojas, tienen al menos (2M-1)/3 descendientes.

Asegura ocupación >=66,6%

ÁRBOL B+

Formados por: Índice: nodos interiores Secuencia: página Hoja enlazadas

secuencialmente en las que se repiten las claves interiores.

Cuando una hoja se divide en 2, sube una copia del valor medio y el real queda en la hoja derecha

Orden : n Altura : h

N° máximo de claves = n^h N° mínimo de claves = 2(n/2)^(h-1)