Download Ayudantia-5-14.05.10

AYUDANTÍA 5: ARBOLES
Carlos Pulgar R.
Mail: [email protected]
Página Ayudantía: http://capulgar.wordpress.com/
ARBOLES

Describir estructuras con algún tipo de jerarquía

Organizan información


Permiten
localizar
información
mas
rápidamente
la
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
(CONCEPTO)

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

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.
TERMINOLOGÍA
BÁSICA
Á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.

Á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

ÁRBOL BINARIO

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:
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
 Si F.E. >1


rotar derecha.
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


Caso 2: la clave no está en una página interior



Desplazar a la izquierda el resto de las claves
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)
