UNIVERSIDAD ESTATAL A DISTANCIA DE COSTA RICA
3069 MATEMÁTICA PARA COMPUTACIÓN II
Cátedra de Matemática para la Administración y
Computación
Lic. Hernán Vı́quez Céspedes
[email protected] Árboles Binarios
Material Complementario
Definición: Árbol
Sea A un conjunto y T una relación en A, entonces se dice que T es un árbol si existe un vértice v0 en
A con la propiedad de que existe una única trayectoria en T de v0 hacia cualquier otro vértice de A, pero
no existe una trayectoria de v0 a v0 .
Nota: El vértice v0 es llamado raı́z del árbol T , y T es entonces un árbol con raı́z denotado por (T, V0 ).
Ejemplo: Considere la siguiente figura que corresponde a un árbol (T, 8) definido sobre el conjunto
A = {8, 3, 10, 1, 6, 14, 4, 7, 13}.
En el árbol anterior se deduce que el vértice 8 es la raı́z, pues existe una única trayectoria de 8 a cualquier
otro vértice, pero no existe una trayectoria de 8 a 8.
Caracterización de un árbol
Sea (T, v0 ) un árbol con raı́z, entonces:
a) No existen ciclos en T .
b) v0 es la única raı́z en T .
c) Cada vértice en T , distinto de v0 , tiene grado interno uno, y v0 tiene grado interno
cero.
Matemática para Computación II Código: 3069
Ejemplo: Considere el siguiente árbol (T, 50), definido sobre el conjunto A cuya notación por extensión
es la siguiente A = {50, 17, 76, 9, 23, 54, 14, 19, 72, 12, 67}.
Observe que en el árbol anterior no existen trayectorias que terminen en el mismo vértice que iniciaron,
por lo que no existen ciclos en T ; el vérice 50 es la única raı́z en el árbol T ; por último, note que a cada
vértice del árbol le llega una única flecha, lo que quiere decir que cada vértice (excepto la raı́z) tiene grado
interno uno y la raı́z tiene grado interno cero por que no le llega ninguna flecha.
Propiedades de un árbol
Sea (T, v0 ) un árbol con raı́z, entonces:
a) T es irreflexivo.
b) T es asimétrico.
c) T no es transitivo.
Ejemplo: Considere el siguiente árbol (T, F ) definido sobre el conjunto A = {F, B, G, A, D, I, C, E, H}
Note que en el árbol anterior ningún vértice se relaciona con sigo mismo, por lo que se dice que T es
irreflexivo, además T es asimétrico pues siempre que (a, b) ∈ T se tiene que (b, a) 6∈ T , lo que quiere
decir que las trayectorias definidas en el árbol T no se devuelven; por último, T no es transitivo, pues
Lic. Hernán Vı́quez Céspedes 2
Matemática para Computación II Código: 3069
observe que (F, B) ∈ T y (B, D) ∈ T pero (F, D) 6∈ T .
Ejemplo: Identificar un árbol
Sea A{1, 3, 4, 6, 7, 8, 10, 13, 14} un conjunto y T una relación sobre A cuyo gráfico está dado por:
T = {(8, 3), (8, 10), (3, 1), (3, 6), (10, 14), (6, 4), (6, 7), (14, 13)}
Muestre que la relación T es un árbol con raı́z e identifiquela, además construya el grafo de dicho árbol.
Solución
Note que no existe ninguna trayectoria que inicie en los vértices 1, 4, 7, 14 por lo que estos vértices se
descartan de ser raı́ces, además no existe ninguna trayectoria de los vértices 3, 10, 6 y 14 al vértice 8. Por
lo tanto, T es un árbol con raı́z 8. El grafo del árbol T está representado por la siguiente imagen.
Teorema: Subárboles
Si (T, v0 ) es un árbol con raı́z y v ∈ T , entonces T (v) también es un árbol cuya raı́z es v. Ası́, se dice
que T (v) es un subárbol de T que comienza en v.
Teorema: Identificar subárboles
Para el árbol construido en el ejemplo anterior identifique y construya dos subárboles.
Note que T (10) denota al subárbol que tiene vértice 10, mientras que T (6) denota al subárbol que tiene
vértice 6.
Lic. Hernán Vı́quez Céspedes 3
Matemática para Computación II Código: 3069
Árboles etiquetados
A veces es útil etiquetar los vértices de un árbol para indicar su uso para un propósito especı́fico. Esto
es particularmente cierto para muchos usos de los árboles en la ciencia de la computación. Ahora se
proporcionará varios ejemplos donde los conjuntos de vértices de los árboles no son importantes, sino que
la utilidad del árbol se enfatiza mediante las etiquetas sobre estos vértices.
Ejemplo: Árbol etiquetado
a) Considere la siguiente expresión algebraica con cada operación entre signos de agrupación:
[3 − (2 ∗ x) + [(x − 2) − (3 + x)]]
Construya el árbol binario etiquetado que determina a la expresión dada.
b) Determine el árbol binario etiquetado que genera a la expresión siguiente:
[3 ∗ (1 − x)] ÷ [(4 + (7 − (y + 2))) ∗ (7 + (x ÷ y))]
Lic. Hernán Vı́quez Céspedes 4
Matemática para Computación II Código: 3069
Representación de árboles binarios en la memoria
Una de las mejores unidades de almacenamiento idealizada es la celda. Una celda tiene dos elementos:
los datos (en algún orden) y el apuntador a la siguiente celda; es decir se indica la dirección donde se
localiza la siguiente celda. Una colección de tales celdas, enlazadas mediante sus apuntadores, es una lista
enlazada.
Se necesita una versión extendida de este concepto, una lista doblemente enlazada, donde cada celda
contenga dos apuntadores y un elemento de datos. Se utilizará el simbolo gráfico de celda con dos ex-
tremos y el dato central. El espacio central representa el almacenaciento de datos y los dos apuntadores,
llamados apuntador izquierdo y apuntador derecho se representan por medio de flechas.
Ejemplo: Construcción de una lista doblemente enlazada
Describa el árbol que genera la expresión [3−(2∗x)+[(x−2)−(3+x)]] como una lista doblemente enlazada.
Ejemplo: Arreglos Left, Data y Right
Proporcione los arreglos Left, Data y Right que describe a la lista doblemente enlazada constuida en el
ejemplo anterior.
Búsqueda o recorrido en árboles binarios
Definición: Visita a un vértice
La realización de tareas adecuadas en cada vértice de un árbol es una visita del vértice.
Definición: Búsqueda en un árbol
El proceso de visita de cada vértice de un árbol en cierto orden especı́fico es a lo que se le llama una
búsqueda en el árbol.
Búsquedas en árboles posicionales binarios
Se harán tres estilos de búsqueda, los cuales son: en preorden, en inorden y en postorden.
Búsqueda o recorrido en Preorden
Paso 1: Visite la raı́z.
Paso 2: Búsque en el subárbol izquierdo, si este existe.
Paso 3: Búsque en el subárbol derecho, si este existe.
Lic. Hernán Vı́quez Céspedes 5
Matemática para Computación II Código: 3069
Ejemplos: Búsqueda en Preorden
1. Considere la siguiente expresión
(a − b) ∗ [c + (d ÷ e)]
a) Construya el grafo del árbol binario posicional etiquetado que represente a esta expresión.
b) Aplique el procedimiento de búsqueda en preorden a este árbol, suponiendo que la visita a
v sólo imprime la etiqueta de v. Nota: esta serı́a la representación prefija o polaca de la
expresión dada.
El resultado que se obtiene al efectuar la búsqueda en preorden al árbol binario etiquetado
anterior corresponde a ∗ − ab + c ÷ de, además esta es la representación prefija o polaca de
la expresión dada.
2. Considere el siguiente árbol binario etiquetado.
Aplique el procedimiento de búsqueda en preorden a este árbol, suponiendo que la visita a v sólo
imprime la etiqueta de v.
Lic. Hernán Vı́quez Céspedes 6
Matemática para Computación II Código: 3069
Al aplicar el procedimiento de búsqueda en preorden al árbol anterior se obtiene como resultado:
F − B − A − D − C − E − G − I − H, tal y como se muestra en la figura siguiente.
Evaluar una expresión en forma polaca
1. Múevase de izquierda a derecha hasta encontrar una cadena de la forma F xy, donde
F es el sı́mbolo de una operación binaria y x e y son números.
2. Se evalúa xF y y se sutituye la respuesta en vez de la cadena F xy.
3. Se continua el procedimiento hasta que sólo quede un número.
Ejemplo: Evaluar expresión polaca
En la búsqueda anterior el resultado fue ∗ − ab + c ÷ de, suponga que a = 6, b = 4, c = 5, d = 2, e = 2 y
evalúe la forma polaca.
La evaluación es la siguiente:
∗2 + 5 ÷ 22 ⇒ pues6 − 4 = 2
∗2 + 51 ⇒ pues2 ÷ 2 = 1 ÷
∗26 ⇒ pues2 · 5 + 1 = 6
12 ⇒ pues2 · 6 = 12
Por lo tanto, al evaluar la notación polaca se obtiene como resultado 12.
Lic. Hernán Vı́quez Céspedes 7
Matemática para Computación II Código: 3069
Búsqueda o recorrido en Inorden
Paso 1: Búsque en el subárbol izquierdo, si este existe.
Paso 2: Visite la raı́z.
Paso 3: Búsque en el subárbol derecho, si este existe.
Ejemplos: Búsqueda en Inorden
1. En el árbol binario del ejemplo anterior construido para la expresión (a − b) ∗ [c + (d ÷ e)], realice
una búsqueda en entreorden y muestre el resultado.
El resultado de la búsqueda en inorden para el árbol binario etiquetado dado corresponde a a − b ∗
c+d÷e, además esta representación obtenida se conoce con el nombre infija de la expresión anterior.
2. Considere el siguiente árbol binario etiquetado.
Aplique el procedimiento de búsqueda en inorden a este árbol, suponiendo que la visita a v sólo
imprime la etiqueta de v.
Al aplicar el procedimiento de búsqueda en inorden al árbol anterior se obtiene como resultado:
A − B − C − D − E − F − G − H − I, tal y como se muestra en la figura siguiente.
Lic. Hernán Vı́quez Céspedes 8
Matemática para Computación II Código: 3069
Búsqueda o recorrido en Postorden
Paso 1: Búsque en el subárbol izquierdo, si este existe.
Paso 2: Búsque en el subárbol derecho, si este existe.
Paso 3: Visite la raı́z.
Ejemplos: Búsqueda en Postorden
1. En el árbol binario construido para la expresión (a − b) ∗ [c + (d ÷ e)], realice una búsqueda en
postorden y muestre el resultado.
El resultado de la búsqueda en postorden para el árbol binario etiquetado dado corresponde a
ab − cde ÷ +∗, además esta representación obtenida se conoce con el nombre postfija de la ex-
presión anterior.
2. Considere el siguiente árbol binario etiquetado.
Aplique el procedimiento de búsqueda en postorden a este árbol, suponiendo que la visita a v sólo
imprime la etiqueta de v.
Al aplicar el procedimiento de búsqueda en postorden al árbol anterior se obtiene como resultado:
A − C − E − D − B − H − I − G − F , tal y como se muestra en la figura siguiente.
Lic. Hernán Vı́quez Céspedes 9
Matemática para Computación II Código: 3069
Árboles binarios de búsqueda
Definición: Árbol binario de búsqueda
Suponga que T es un árbol binario. Entonces T se denomina árbol binario de búsqueda si cada nodo N
de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor en el subárbol izquierdo de
N y es menor que cualquier valor en el subárbol derecho de N .
Ejemplo: Árbol binario de búsqueda
A continuación se presenta un árbol binario de búsqueda con raı́z 8 y hojas 1,4,7 y 13.
Nota: Para una fácil comprensión del concepto de árbol binario de búsqueda, queda resumido en que es
un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacı́o) contiene valores
menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacı́o) contiene valores mayores.
Ejemplo: Eliminación e inserción en un árbol binario de búsqueda
1. Considere el árbol binario de búsqueda T de la figura anterior. Suponga que se proporciona el dato
ITEM = 20, y que se desea encontrar o insertar ITEM en T. Al simular el algoritmo 1.1 de la página
10 de la unidad didáctica se obtienen los pasos siguientes:
a) ITEM=20 se compara con la raı́z R = 8. Puesto que 20 > 8, se procede con el hijo derecho
de 8, que es 10.
b) ITEM=20 se compara con 10. Puesto que 20 > 10, se procede al hijo derecho de 10, que es
14.
c) ITEM=20 se comprara con 14. Puesto que 20 > 14 y 14 no tiene hijo derecho, 20 se inserta
como el hijo dercho de 14.
Lic. Hernán Vı́quez Céspedes 10
Matemática para Computación II Código: 3069
La inserción de 20 en el árbol binario de búsqueda se muestra en la siguiente figura.
2. Considere el árbol binario de búsqueda inicial. Suponga que se desea eliminar ITEM=14 de T .
Primero se encuentra el nodo N tal que N = 14. Observe que N = 14 tiene exactamente un hijo
M = 13. N = 14 se elimina de T al sustituir la ubicación de N en el nodo padre P (14) por la
ubicación de M = 13. (Esto es sustituye N = 14 por M = 13), tal y como se muestra en la
siguiente figura.
Definición: Cola prioritaria
Sea S una cola de prioridad. Es decir, S es un conjunto donde es posible insertar o eliminar elementos
periódicamente, pero donde siempre se elimina el mayor elemento actual (el elemento con prioridad más
alta).
Definición: Montı́culo
Suponga que H es un árbol binario completo. Entonces H se denomina montı́culo (heap) o máxheap, si
cada nodo N tiene la siguiente propiedad: el valor de N es mayor que o igual al valor de cada uno de los
hijos de N .
Lic. Hernán Vı́quez Céspedes 11
Matemática para Computación II Código: 3069
Ejemplo: Representación de un montı́culo
Un ejemplo de un árbol H con la caracterı́stica de montı́culo es el siguiente
Nota: Note que los montı́culos tienen la caracterı́stica de que cada nodo padre tiene un valor mayor que
el de cualquiera de sus nodos hijos.
Ejemplo: Inserción de un montćulo
Considere el montı́culo H de la figura anterior. Suponga que se desea insertar IT EM = 9 en H. Al
simular el algoritmo 1.3 de la página 14 de la Unidad Didáctica, primero se adjunta ITEM como el último
elemento del árbol completo; es decir, como el hijo derecho de 12.
Observe que este algoritmo parte de un elemento y lo inserta en un montı́culo aplicando su criterio de
ordenación. Si se supone que el monticulo está estructurado de forma que la raı́z es mayor que sus hijos,
comparamos el elemento a insertar (incluido en la primera posición libre) con su padre. Si el hijo es menor
que el padre, entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo
por el padre.
¿Y si la nueva raı́z sigue siendo más grande que su nuevo padre?. Se vuelve a hacer otra vez dicho
paso hasta que el montı́culo quede totalmente ordenado. En la imagen adjunta se puede observar el
ejemplo de cómo realmente se inserta un elemento en un montı́culo. Se aplica la condición de que cada
padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su
padre, siguiendo el método de ordenación, sustituimos el elemento por su padre que es 9 y ası́ quedarı́a el
montı́culo ordenado.
Lic. Hernán Vı́quez Céspedes 12
Matemática para Computación II Código: 3069
Ejemplo: Eliminación de la raı́z de un montćulo
Considere el montı́culo H de la siguiente figura
Aplique el algorı́tmo 1.4 de la página 15 de la Unidad Didáctica para eliminar la raı́z del montı́culo H.
Solución
La idea es remplazar la raı́z con el nodo que ocupa la última posición del montı́culo y luego se crea un
montı́culo con los elementos restantes de la siguiente manera:
a) Paso 1: La raı́z se elimina y se remplaza por el último nodo del montı́culo, en este caso se elimina
la raı́z 60 y se remplaza por el nodo 15, tal y como se muestra en la siguiente figura
b) Paso 2: Se crea un montı́culo con los nodos restantes de la siguiente manera:
Lic. Hernán Vı́quez Céspedes 13
Matemática para Computación II Código: 3069
Definición: Longitudes de caminos ponderados
Suponga que T es un 2-árbol con n nodos externos, y que a cada nodo externo se asigna un peso (no
negativo). La longitud del camino ponderado (o simplemente la longitud del camino) P del árbol T se
define como la suma:
P = W1 L1 + W2 L2 + . . . + Wn Ln
donde cada W es el peso de un nodo externo N y L es la longitud del camino desde la raı́z R hasta el nodo.
Ejemplo: Longitud de camino
En la siguiente figura se muestra un árbol binario T donde los nodos externos tienen pesos.
La longitud de caminos ponderados para el árbol T es:
P = 19(3)+23(3)+11(4)+13(4)+29(3)+2(7)+3(7)+5(6)+7(5)+17(4)+31(3)+37(3)+41(3) = 804
Algoritmo de Huffman
La codificación de Huffman funciona en una lista de pesos wi al construir un árbol binario con una longitud
de caminos ponderados mı́nimos y procede al encontrar los dos peos más pequeños w1 y w2 , vistos como
nodos externos, y reemplazándolos con un nodo interno de peso w1 + w2 . El procedimiento se repite paso
a paso hasta que se alcanza el nodo raı́z. Un nodo externo individual puede ser codificado por una cadena
binaria de 0s (para las ramas izquierdas) y 1s (para las ramas derechas).
El procedimiento se resume a continuación para los pesos 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 y 41 dados
por los primeros 13 primos, y el árbol resultante se muestra a continuación. Como queda claro en el
diagrama, las rutas a los pesos más grandes son más cortas que las de los pesos más pequeños. En este
ejemplo, el número 13 se codificarı́a como 1010.
Lic. Hernán Vı́quez Céspedes 14
Matemática para Computación II Código: 3069
1. Algoritmo de Huffman
2 3 5 7 11 13 17 19 23 29 31 37 41
5 5 7 11 13 17 19 23 29 31 37 41
10 7 11 13 17 19 23 29 31 37 41
17 11 13 17 19 23 29 31 37 41
17 24 17 19 23 29 31 37 41
24 34 19 23 29 31 37 41
24 34 42 29 31 37 41
34 42 53 31 37 41
42 53 65 37 41
42 53 65 37 78
95 65 78
95 143
238
2. Árbol T
Árboles generales
La siguiente figura es una ilustración de un árbol general T con 13 nodos,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
A menos que se establezca lo contrario, la raı́z de un árbol T es el nodo en la parte superior del diagrama
y los hijos de un nodo se ordenan de izquierda a derecha.
Lic. Hernán Vı́quez Céspedes 15
Matemática para Computación II Código: 3069
En consecuencia, 1 es la raı́z de T , y 1 tiene tres hijos: el primer hijo 2, el segundo hijo 3 y el tercer hijo
4. Observe que:
a) 3 tiene sólo un hijo. c) 4 tiene dos hijos.
b) 3 y 5 tienen tres hijos. d) Ninguno de 11, 12, 13, 6, 7, 8, 9, 10 tiene hijos.
Nota: El último grupo de nodos, los que no tienen hijos, se denominan nodos terminales.
Lic. Hernán Vı́quez Céspedes 16
