Download arboles

ÁRBOLES
Matemáticas Discretas
MISTI
Introducción
• El tratamiento de grafos puede resultar una tarea
complicada ya que estos tienen las siguientes
características :
• No guardan una estructura establecida
• No respetan reglas
• Y la relación entre los nodos puede llegar a ser muy compleja
Introducción(II)
• Por lo tanto aplicarlos en ciertas tareas, como el
tratamiento y organización de la información, puede ser
muy complicado.
• Por ello en lugar de usar grafos que están estructurados
sin regla alguna, se utilizan grafos con características
particulares llamados árboles.
Definición
• Un árbol es un grafo
• no dirigido(las aristas no tienen sentido),
• conexo en donde existe un camino entre cualquier par de
vértices(v,w) y
• Sin ciclos
• Sin aristas múltiples
¿Cuál de estos son árboles?
Respuesta= Ambos son árboles ya que son grafos conexos y
acíclicos
¿Cuál de estos grafos son arboles?
Respuesta= El primero no es un árbol, ya que e,b,a,d,e es un
ciclo del grafo
¿Cuál de estos grafos son arboles?
Respuesta= El segundo no es un árbol, ya que no es conexo
Árbol con raíz
• Es un árbol dónde uno de los ha sido designado como la
raíz y todas las aristas están orientadas a alejarse de la
raíz
Con raíz en a
T
Con raíz en c
Nodos y ramas
• Los vértices de un árbol se llaman nodos y los lados
reciben el nombre de ramas
Padres e hijos
• El padre de un nodo es un nodo de mayor nivel con el
que se encuentra relacionado el nodo.
• Si v es el padre u, debe existir una arista dirigida de v a u.
• Cualquier nodo puede tener nodos relacionados en un
nivel más bajo a los cuales se les reconoce como hijos.
• Dos nodos que tienen el mismo padre se dice que son
hermanos.
v es el padre de u y de y
u y y son hijos de v
u y y son hermanos
Antecesores y Descendientes
• Los antecesores de un vértice diferente de la raiz son
todos los vértices que aparecen desde el camino desde la
raíz hasta ese vértice( excluyendo a este último e
incluyendo la raíz).
• Los descendientes de un vértice v son aquellos para los
que v e es un antecesor .
Los antecesores de f
son b, a y c
Los descendientes de a
son b, f y g
Hojas y vértices internos
• Un vértice se llama hoja si no tiene hijos.
• Los vértices que tienen hijos se llaman vértices internos.
Árboles m-narios
• Un árbol con raíz se llama árbol m-ario si todos sus
vértices internos tienen, a lo sumo, m hijos.
• El árbol se llama árbol m-ario completo si todo vértice
interno tiene exactamente m hijos.
Niveles en un árbol
• El nivel de un vértice v en un árbol con raíz es la longitud
del único camino desde la raíz a dicho vértice.
• El nivel de la raíz por definición es 0.
Altura
• La altura de un árbol con raíz es el máximo de los niveles
de sus vértices. En otras palabras, la altura de un árbol
es la longitud del camino más largo desde la raíz a
cualquier vértice.
Puesto que el mayor nivel es
4, el árbol tiene altura 4.
Árboles balanceados
• Un árbol con raíz m-ario de altura h está equilibrado o
balanceado si todas sus hojas están en los niveles h o h1
Árbol balanceado
Árbol no balanceado
Balanceo de un árbol
• Para balancear un árbol con una cantidad constante de
hijos de los nodos padres, se llenan empezando por la
raíz y descendiendo con un avance de izquierda a
derecha.
Árbol no balanceado
Árbol balanceado como ternario
Bosques
• Un bosque es un grafo acíclico pero no necesariamente
conexo. Además tienen la propiedad de que cada una de
sus componentes conexas es un árbol.
Ejemplo de bosque
Árboles generadores
• Sea G un grafo simple. Un árbol generador de G es un
subgrafo de G que es un árbol y contiene todos los
vértices.
• Es decir, es un subgrafo conexo con el mínimo de aristas
y con todos los vértices del grafo original.
Grafo simple G
Árbol generador de G
Ejemplo
• Considere un sistema de carreteras representadas por el
grafo simple G. En invierno estas carreteras se llenan de
nieve. El departamento de mantenimiento quiere limpiar
el menor número de carreteras (ya que limpiarlas todas
lleva mucho tiempo) de modo que dos ciudades
cualesquiera queden siempre conectadas.
Obtención de un árbol generador
• Existen dos formas en que es posible obtener el árbol
generador de un grafo simple:
• Búsqueda a profundidad
• Búsqueda a lo ancho
Búsqueda a lo ancho
• Se comienza a buscar en la raíz
• Después se examinan todos los hijos de la raíz de
izquierda a derecha
• Si la información no se encuentra en ese nivel, se
procede a buscar en el siguiente nivel de izquierda a
derecha
• Si se recorrió todo el árbol y la información no se
encontró se manda el mensaje correspondiente
Este tipo de búsqueda es efectiva cuando el
árbol está balanceado y hay pocos niveles
Ejemplo búsqueda a lo ancho
• Se busca la letra ‘j’
• Se busca en la raíz
• Se busca en el nivel 1 de izquierda a derecha
• Se busca en el nivel 2 de izquierda a derecha
El recorrido para encontrar el nodo
elegido es (a,b,c,d,e,f,g,h,i,j)
Búsqueda en profundidad
• Se comienza a buscar en la raíz.
• Después se busca en el hijo de la izquierda y si este nodo
tiene hijos se continúa con el de la izquierda y así
sucesivamente hasta llegar a la parte más baja.
• Si este nodo ya no tiene hijo izquierdo , se continúa con
el nodo de la derecha.
• Cuando se llega nuevamente a la hoja, se regresa hasta
el nodo inmediato anterior que tenga hijos sin
inspeccionar, y así sucesivamente.
• Si no se encuentra se manda el mensaje correspondiente
Este tipo de búsqueda es efectiva cuando el
árbol está balanceado y hay pocos niveles
Ejemplo búsqueda a profundidad
• Se busca la letra ‘j’
• Se busca en la raíz
• Se busca en los hijos de b
• Se busca en los hijos de c
El recorrido para encontrar el nodo
elegido es (a,b,e,f,g,c,h,l,m,n,i,j)
Generación de árbol por búsqueda a lo
ancho
• Elegimos, de modo arbitrario, un nodo inicial a
• Se añaden todos los nodos adyacentes a al nodo raíz
Generación de árbol por búsqueda a lo
ancho
• Se analiza el siguiente nodo que alfabéticamente sigue y
se añaden los nodos adyacentes que aún no están en el
árbol
Generación de árbol por búsqueda a lo
ancho
• Cómo a y b ya no tienen nodos adyacentes se
inspecciona el nodo que sigue alfabéticamente (c) y se
agregan los nodos adyacentes necesarios
Generación de árbol por búsqueda a lo
ancho
• Se analizan d y e pero ambos no tienen nodos
adyacentes que agregar.
• Se analiza f y se agrega como nodo adyacente a i
Generación de árbol por búsqueda a
profundidad
• Se elige un nodo arbitrario a como raíz
• Construimos un camino tan largo como sea
posible(cuando un nodo tiene 2 hijos se elige el de menor
valor)
Generación de árbol por búsqueda a
profundidad
• Verificamos si d tiene nodos no visitados que sean
adyacentes
• Regresamos a e y vemos que tiene un nodo adyacente
no visitado f
Generación de árbol por búsqueda a
profundidad
• Verificamos si f tiene nodos adyacentes no visitados y
construimos el camino más largo posible
Generación de árbol por búsqueda a
profundidad
• Verificamos si g no tiene adyacentes
• Regresamos a f y como tiene otro adyacente no visitado
se construye el camino
Recorrido de un árbol
• Los árboles con raíz se utilizan frecuentemente para
almacenar información. Por lo tanto se necesitan
procedimientos que permitan visitar cada uno de los
nodos.
• Existen tres maneras de recorrer un árbol (según la
manera en que se coloca el padre con respecto a los
hijos):
• Recorrido en orden primero
• Recorrido en orden segundo
• Recorrido en orden final
Orden primero
• Primero se toma el padre, luego el hijo izquierdo y al final
demás hijos
• Se comienza por la raíz, después sigue el nodo de la
izquierda, si este nodo tiene hijos se sigue por el nodo de
la izquierda hasta llegar a la hoja
• Después se continua con el siguiente hermano de la
derecha y así sucesivamente
Orden segundo
• Primero se toma el hijo izquierdo,luego el padre y al final
demás hijos
• Se comienza por la raíz, después sigue el nodo de la
izquierda, si este nodo tiene hijos se sigue por el nodo de
la izquierda hasta llegar a la hoja
• Después se continua con el siguiente hermano de la
derecha y así sucesivamente
Orden final
• En este recorrido se toma primero el hijo izquierdo,
después los demás hermanos y al final el padre.
Búsquedas
• El árbol binario de búsqueda es aquel dónde cada hijo se
designa como un vértice izquierdo o derecho.
• Cada vértice está etiquetado con una clave de modo de
modo que la clave es mayor de su subárbol izquierdo y
menor que todos sus vértices de su subárbol derecho.
Ejemplo
• Construye un árbol binario de búsqueda para las palabras
matemáticas, paleontología, geografía, zoología,
meteorología, geología, psicología y cosmología
• Paso 1: Se toma la primera palabra como raíz
• Paso2: Se compara la siguiente palabra con la raíz y si es
mayor se coloca como nodo derecho y si es menor como
nodo izquierdo
Ejemplo
Recorridos
Primero: 30,-10,3,-7,4,3,9,7,6,68,50,30,31,56,58,72,98
Segundo: -10,-7,3,3,4,6,7,9,30,30,31,50,56,58,68,72,98
Final: -7,3,6,7,9,4,3,-10,31,30,58,56,50,98,72,68,30
Ejemplo
• Crea un árbol de búsqueda binaria con la siguiente
información: 30, -10,3,4,9,68,50,30,3,7,6,72,98,7,56,31,58
Referencias
• Kenneth H. Rosen, Matemática Discreta y sus
Aplicaciones, Quinta Edición, McGrawHill
• Jiménez , José A, Matemáticas para la Computación ,
Primer Edición, Alfaomega Grupo Editor
Gracias!!!
ÁRBOLES
Matemáticas Discretas
MISTI