Árboles

Cursos Propedéuticos 2015

Dr. René Cumplido

M. en C. Luis Rodríguez Flores
 Contenido de la sección

• Introducción
• Árbol genérico
– Definición y representación
• Árboles binarios
– Definición, implementación, aplicaciones y recorridos
• Árboles binarios de Búsqueda
– Definición y principales operaciones (insertar,
eliminar, buscar)
 Introducción

Hasta ahora, en todas las estructuras existen al

menos dos operaciones:

• Insertar un elemento en el conjunto.

• Buscar y/o descartar un elemento

¿Que limitaciones existen respecto a la

complejidad de sus operaciones básicas?
 Introducción

Una lista no ordenada tiene:

• Costo de inserción O(1).

• Costos de búsqueda O(n).

En el segundo caso la repetición de n operaciones

sobre la estructura da origen a complejidad n2.
 Introducción

Una lista ordenada en forma ascendente por

prioridad, permite:

• Seleccionar el mínimo con costo O(1).

• Insertar manteniendo el orden tiene costo
promedio O(n) en el peor caso.
 Introducción

La estructura de un árbol binario garantiza que las

operaciones de inserción y eliminación sean de
complejidad O( log2 (n) )
 ¿Qué es un árbol?

Un árbol es un grafo A que tiene un único nodo llamado

raíz que:
• Si tiene 0 relaciones se llama nodo hoja.
• Si tiene un un número finito de relaciones donde cada una
de esas relaciones es un sub-árbol.

– Por tanto, un árbol es una estructura no secuencial.

 Ejemplo de un árbol

B C D

E F G H I
 Nomenclatura básica

• Todo nodo nj, exceptuando el raíz, está conectado

exclusivamente a otro nodo nk donde:
– nj es el padre de nk (e.g., B es el padre de E)
– nk es uno de los hijos de nj (e.g., E es un hijo de B)
– Nodos con el mismo padre son “hermanos”
– Nodos sin hijos son llamados “hojas”
• Si existe una trayectoria del nodo nj al nodo nk entonces:
– nj es antecesor de nk (e.g., A es antecesor de E)
– nk es descendiente de nj (e.g., E es descendiente de E)
Ejemplo
 Más nomenclatura

• La trayectoria del nodo n1 a nk se define como la

secuencia de nodos n1,n2,…,nk, tal que ni es el
padre de ni+1. Entonces:
– La longitud de una trayectoria es el número de
ramas recorridas, es decir, K-1.
– Nivel o profundidad del nodo ni es la longitud de la
trayectoria que va del nodo raíz a ni.
• C tiene profundidad 1, mientras que I tiene profundidad 2.
– La altura del nodo ni es longitud de la trayectoria más
larga de ni a una hoja.
• G tiene altura 0, B altura 1 y A (raíz) altura 2.
 Implementación

typedef struct {
• Dos formas de implementar:
TipoDato dato;
struct NodoArbol *hijo1; – Tener un apuntador a cada uno
struct NodoArbol *hijo2; de los hijos. Problema cuando
:
struct NodoArbol *hijoN; NO sabemos el número de hijos.
} NodoArbol; – Mantener los hijos de un nodo en
una lista ligada. No hay ninguna
typedef struct { restricción sobre número de hijos.
TipoDato dato;
struct NodoArbol *hijo; • Así, un nodo del árbol consiste en
struct NodoArbol *hermano; un dato, un apuntador al primer
} NodoArbol;
hijo y un apuntador a la lista de
hermanos.
 Árboles binarios

• Un árbol binario es un
árbol donde cada nodo Raíz

puede tener como máximo

dos hijos.
• Recursivamente un árbol
binario puede definirse
como: un árbol vacío, o un
nodo raíz con un subárbol
Árbol Árbol
izquierdo y un subárbol izquierdo derecho
derecho.
 Árboles binarios

Un árbol binario es una estructura de datos de tipo árbol en

donde cada uno de los nodos del árbol puede tener 0, 1,
ó 2 subárboles llamados de acuerdo a su caso como:

• Si el nodo raíz tiene 0 relaciones se llama hoja.

• Si el nodo raíz tiene 1 relación a la izquierda, el segundo
elemento de la relación es el subárbol izquierdo.
• Si el nodo raíz tiene 1 relación a la derecha, el segundo
elemento de la relación es el subárbol derecho.

* Si cada nodo que NO es una hoja tiene un subárbol izquierdo y un

subárbol derecho, entonces se trata de un árbol binario completo.
 Árboles binarios

Cuales de las siguientes

figuras representa un árbol
binario?
 Árboles binarios

• En un primer caso se tiene que el número de

nodos n es tres; un nivel (m elementos entre los
nodos en una trayectoria desde la raíz a las
hojas) y altura h igual dos.
 Árboles binarios

Con dos niveles: n=7=23-1 Con tres niveles:

m=2 h=3 n=15=24-1 m=3 h=4

En un caso general para árboles binarios completos: n = 2h -1, h = m +1 y

h=log2 (n+1), despejando h de la primera relación.
 Árboles binarios
• La altura, es el concepto importante para la
complejidad, ya que define el número de nodos
a revisar en una trayectoria desde la raíz hasta
las hojas.

• Cual es la altura h del árbol anterior?:

• Si conocemos h, cual es el valor de n?:
 Árboles binarios

• Árboles binarios llenos: Cada nodo del árbol o

es una hoja o un nodo interno con exáctamente
dos hijos.

• Árbol binario completo: es aquel en el que todos

los nodos tienen dos hijos y todas las hojas
están en el mismo nivel.
– cada nodo,excepto las hojas, tiene el máximo de
hijos que puede tener.
 Árboles binarios

(a) (b)

¿Son completos?
¿Son llenos?
 Implementación con arreglos

Posición 0 1 2 3 4 5 6 7 8 9 10 11
Padre -- 0 0 1 1 2 2 3 3 4 4 5
Hijo Izquierdo 1 3 5 7 9 11 -- -- -- -- -- --
Hijo Derecho 2 4 6 8 10 -- -- -- -- -- -- --
Hermano Izq -- -- 1 -- 3 -- 5 -- 7 -- 9 --
Hermano Der -- 2 -- 4 -- 6 -- 8 -- 10 -- --
 Implementación con apuntadores

• Los nodos del árbol son Estructura del

estructuras que nodo del árbol
almacenan los datos, y
apuntadores a los
subárboles de ese nodo.
Representación
Árbol del Árbol

D S

L Y
A
 Implementación

• Cada nodo del árbol consiste en:

typedef struct NodoArbol – Un dato (cualquier tipo)
*Arbol;
– Un apuntador al hijo izquierdo
struct NodoArbol { – Un apuntador al hijo derecho
TipoDatol dato;
struct NodoArbol *izq; • Inicialmente el nodo raíz apunta
struct NodoArbol *der; a NULL.
};
• En las hojas del árbol, los
apuntadores hacia los hijos
izquierdo y derecho son NULL.
 Operaciones con árboles binarios

• Con los árboles binarios es posible definir

algunas operaciones primitivas, estas
operaciones permiten obtener información de un
nodo y sirven para desplazarse en el árbol,
hacia arriba o hacia abajo.
 Operaciones con árboles binarios

• info(p) que devuelve el contenido del nodo apuntado por p.

• left(p) devuelve un apuntador al hijo izquierdo del nodo
apuntado por p, o bien, devuelve NULL si el nodo apuntado
por p es una hoja.
• right(p) devuelve un apuntador al hijo derecho del nodo
apuntado por p, o bien, devuelve NULL si el nodo apuntado
por p es una hoja.
• father(p) devuelve un apuntador al padre del nodo apuntado
por p, o bien, devuelve NULL si el nodo apuntado por p es la
raíz.
• brother(p) devuelve un apuntador al hermano del nodo
apuntado por p, o bien, devuelve NULL si el nodo apuntado
por p no tiene hermano.
 Operaciones con árboles binarios

Estas otras operaciones son lógicas, tienen que ver con la

identidad de cada nodo:

• isLeft(p) devuelve el valor true si el nodo actual es el

hijo izquierdo del nodo apuntado por p, y false en caso
contrario.
• isRight(p) devuelve el valor true si el nodo actual es el
hijo derecho del nodo apuntado por p, y false en caso
contrario.
• isBrother(p) devuelve el valor true si el nodo actual es
el hermano del nodo apuntado por p, y false en caso
contrario.
 Operaciones con árboles binarios

• También son útiles las operaciones makeTree,

setLeft y setRight.

• makeTree(x) crea un nuevo árbol binario que consta de

un único nodo con un campo de información x y
devuelve un apuntador a ese nodo.
• setLeft(p,x) acepta un apuntador p a un nodo de árbol
binario sin hijo izquierdo. Crea un nuevo hijo izquierdo
de node(p) con el campo de información x.
• setRight(p,x) es similar, excepto que crea un hijo
derecho.
 Aplicaciones de árboles binarios

Un árbol binario es una estructura de datos útil

cuando se trata de hacer modelos de procesos
en donde se requiere tomar decisiones en uno
de dos sentidos en cada parte del proceso.

Supongamos que tenemos un arreglo en donde

queremos encontrar todos los duplicados. Esta
situación es bastante útil en el manejo de las
bases de datos, para evitar la redundancia.
 Aplicaciones de árboles binarios

• El primer número del arreglo se coloca en la raíz del árbol

con sus subárboles izquierdo y derecho vacíos.

• Luego, cada elemento del arreglo se compara son la

información del nodo raíz y se crean los nuevos hijos con el
siguiente criterio:

– Si el elemento del arreglo es igual que la información del nodo raíz,

entonces notificar duplicidad.
– Si el elemento del arreglo es menor que la información del nodo raíz,
entonces se crea un hijo izquierdo.
– Si el elemento del arreglo es mayor que la información del nodo raíz,
entonces se crea un hijo derecho.
 Aplicaciones de árboles binarios

• Una vez que ya está creado el árbol, se pueden

buscar los elementos repetidos. Si x el elemento
buscado, se debe recorrer el árbol del siguiente
modo:

• Sea k la información del nodo actual p. Si x > k

entonces cambiar el nodo actual a right(p), en
caso contrario, en caso de que x = k informar
una ocurrencia duplicada y en caso de que x ≥ k
cambiar el nodo actual a left(p).
Aplicaciones de árboles binarios
 Recorridos de un árbol
Para obtener el contenido de todos los nodos en
un árbol es necesario recorrer el árbol. Esto es
debido a que solo tenemos conocimiento del
contenido de la dirección de un nodo a la vez.

• El proceso de visitar los nodos en algún orden

se denomina recorrido.

• Cualquier recorrido que lista cada nodo del árbol

exáctamente una vez se denomina una
enumeración de los nodos del árbol.
 Recorridos de un árbol

• ¿cómo lo podemos recorrer?

 Recorridos estándar

• Preorder:
– Visitar nodo void inorder(NodoArbol *nodo) {
if (nodo != NULL) {
– Visitar árbol izquierdo inorder(nodo->izq);
– Visitar árbol derecho visitar(nodo);
inorder(nodo->der);
• Inorder: }
}
– Visitar árbol izquierdo
– Visitar nodo
void postorder(NodoArbol *nodo)
– Visitar árbol derecho {
if (nodo != NULL) {
• Postorder: postorder(nodo->izq);
postorder(nodo->der);
– Visitar árbol izquierdo visitar(nodo);
– Visitar árbol derecho }
}
– Visitar nodo
Ejemplo de recorridos

B C

D E F G

Preorden: A, B, D, E, C, F, G
Inorden: D, B, E, A, F, C, G
Postorden: D, E, B, F, G, C, A
 Árbol binario de búsqueda

• Es un árbol:
– Una colección de nodos que puede ser vacía, o que en su defecto consiste de
un nodo raíz R y un número finito de estructuras tipo árbol T1,…,Tk, llamados
subárboles, los cuales son disjuntos y sus respectivos nodos raíz están
conectados a R.

• Es binario:
– Cada nodo puede tener como máximo dos hijos, en otras palabras, cada nodo
sólo puede tener dos subárboles.

• Es de búsqueda porque:
– Los nodos están ordenados de manera conveniente para la búsqueda.
– Todos los elementos almacenados en el subárbol izquierdo de un nodo con valor
K, tienen valores < K.
– Todos los elementos almacenados en el sub-árbol derecho de un nodo con valor
K, tienen valores >= K.
 Ejemplos

• ¿son todos árboles binarios de búsqueda?

2
6 6

2 8 2 8 1 8

1 4 1 4 7

3 3 7 6

4
 Operación INSERTAR

Insertando 5 void insertar(NodoArbol *nodo, int elem){

if (nodo == NULL) {
nodo=(NodoArbol *)malloc(sizeof(NodoArbol));
6 nodo->dato = elem;
nodo->izq = nodo->der = NULL;
2 8 }
else if (elem < nodo->dato)
nodo-izq = insertar(nodo->izq, elem);
1 4 else if (elem > nodo->dato)
nodo->der = insertar(nodo->der, elem);

return nodo;
3 5
}
 Ejercicio

• Construya el árbol binario

de búsqueda, al insertar
secuencialmente los
valores 5, 9, 3, 7, 8, 12,
6, 4.
 Operación BUSCAR

6
boolean buscar(NodoArbol *nodo, int elem) {
if (nodo == NULL)
2 8
return FALSE;
else if (nodo->dato < elem)
return buscar(nodo->izq, elem);
1 4 else if (nodo->dato > elem)
return buscar(nodo->der, elem);
else return TRUE;
3 }

Buscando 4: VERDADERO
Buscando 7: FALSO
 Operación ELIMINAR (1)

• Existen cuatro distintos escenarios:

1. Intentar eliminar un nodo que no existe.
– No se hace nada, simplemente se regresa FALSE.
2. Eliminar un nodo hoja.
– Caso sencillo; se borra el nodo y se actualiza el
apuntador del nodo padre a NULL.
3. Eliminar un nodo con un solo hijo.
– Caso sencillo; el nodo padre del nodo a borrar se
convierte en el padre del único nodo hijo.
4. Eliminar un nodo con dos hijos.
– Caso complejo, es necesario mover más de un
apuntador.
 ELIMINAR (casos sencillos)

Eliminar nodo hoja Eliminar nodo con un hijo

Eliminar 3 Eliminar 4

6 6

2 8 2 8

1 4 1 4

3 3
 ELIMINAR (Caso complejo)
Eliminar nodo con dos hijos
Eliminar 2
6 6

2 8 3 8

1 4 1 4
copiar
valor
3 5 3 5
eliminar

• 1. Remplazar el dato del nodo 2.Eliminar el nodo más

que se desea eliminar con el pequeño del subárbol
dato del nodo más pequeño del derecho (caso fácil)
subárbol derecho
 Otro ejemplo (caso complejo)
Eliminar nodo con dos hijos
Eliminar 2
6 6

1
2 8 3 8

1 4 1 4

3 5 3 5

2 Eliminar 3.
Eliminación de
3.5 3.5
un nodo con
un hijo.
 Ejercicio

• Dibujar el árbol
resultante después de
aplicar las siguientes
eliminaciones de 20,
27, 14 y 22 al
siguiente árbol.
 Implementación ELIMINAR

void eliminar(NodoArbol *nodo, int elem) { else /* encontramos el elemento */

NodoArbol *aux, * hijo; /* tiene dos hijos */
if (nodo->izq && nodo->derecho){
if (nodo == NULL) return; /* no existe nodo */ aux = enontrar_min(nodo->der);
/* recorrer árbol hasta encontrar elem */ nodo->dato = aux->dato;
else if (elem < nodo->dato) nodo->der = eliminar(
nodo-izq = eliminar(nodo->izq, elem); nodo->der; nodo->dato);
else if (elem > nodo->dato) }
nodo->der = eliminar(nodo->der, elem); /* un solo hijo */
else {
aux = nodo;
if (nodo->izq == NULL) hijo = nodo->der;
if (nodo->der == NULL) hijo = nodo->izq;
free(aux);
return hijo;
}
}
return nodo;
}