ELO320 - Estructuras de Datos y Algoritmos
Tipos de Datos Abstractos
Árbol binario de Búsqueda
Dr. Nicolás Gálvez R.
[Link]@[Link]
Ing. Civil Telemática - Departamento de Electrónica
1er Semestre 2022
1/1
ABB: Árbol binario de búsqueda
Un árbol binario de búsqueda es una implementación del árbol binario que
permite guardar y buscar eficientemente de datos debido a su estructura.
2/1
ABB: Árbol binario de búsqueda
En un árbol binario de búsqueda, los hijos izquierdos guardan información
menor (o igual), y los hijos derechos guardan información mayor, con
respecto a la de su padre.
3/1
ABB: Árbol binario de búsqueda
A partir de esta regla de modelamiento se definen fácilmente las
operaciones de búsqueda, inserción, y eliminación de elementos. Además
de que los recorridos pre-orden, in-orden y post-orden sean efectivos para
determinadas labores.
4/1
ABB: Árbol binario de búsqueda
Por ejemplo, es fácil determinar el lugar y posición de los valores en un
intervalo.
¿Cómo determinan el sucesor y predecesor de un padre?
Sucesor: buscar en la derecha, todo hacia la izquierda.
Antecesor: buscar en la izquierda, todo hacia la derecha.
¿Cuál es su principal caracterı́stica?
Siempre tendrán a lo más un hijo.
5/1
ABB: Operaciones
Las operaciones más comunes de los ABB son:
init(): Inicializar el árbol (root == NULL).
size(): Cantidad de elementos en el árbol.
x preorden(): Operación x en pre-orden.
x inorden(): Operación x en in-orden.
x postorden(): Operación x en post-orden.
search(): Buscar un elemento en el árbol.
insert(): Insertar un elemento en el árbol.
delete(): Eliminar un elemento en el árbol.
clear(): Limpiar el árbol.
6/1
ABB: Recorrer
¿Como se imprimirı́an los datos del siguiente árbol con recorrido
pre-orden, in-orden y post-orden?
Pre-orden: 19 - 6 - 2 - 15 - 7 - 17 - 30 - 21 - 27 - 36
In-orden: 2 - 6 - 7 - 15 - 17 - 19 - 21 - 27 - 30 - 36
Post-orden: 2 - 7 - 17 - 15 - 6 - 27 - 21 - 36 - 30 - 19
7/1
ABB: Recorrer
¿Como se imprimirı́an los datos del siguiente árbol con recorrido
pre-orden, in-orden y post-orden?
Pre-orden: 19 - 6 - 2 - 15 - 7 - 17 - 30 - 21 - 27 - 36
In-orden: 2 - 6 - 7 - 15 - 17 - 19 - 21 - 27 - 30 - 36
Post-orden: 2 - 7 - 17 - 15 - 6 - 27 - 21 - 36 - 30 - 19
7/1
ABB: Recorrer
¿Como se imprimirı́an los datos del siguiente árbol con recorrido
pre-orden, in-orden y post-orden?
Pre-orden: 19 - 6 - 2 - 15 - 7 - 17 - 30 - 21 - 27 - 36
In-orden: 2 - 6 - 7 - 15 - 17 - 19 - 21 - 27 - 30 - 36
Post-orden: 2 - 7 - 17 - 15 - 6 - 27 - 21 - 36 - 30 - 19
7/1
ABB: Recorrer
¿Como se imprimirı́an los datos del siguiente árbol con recorrido
pre-orden, in-orden y post-orden?
Pre-orden: 19 - 6 - 2 - 15 - 7 - 17 - 30 - 21 - 27 - 36
In-orden: 2 - 6 - 7 - 15 - 17 - 19 - 21 - 27 - 30 - 36
Post-orden: 2 - 7 - 17 - 15 - 6 - 27 - 21 - 36 - 30 - 19
7/1
ABB: Buscar
Comenzaremos con la función básica search(): Buscar un
elemento en el árbol.
Se puede hacer de dos formas:
Usando un puntero para recorrer el árbol.
Recursivamente.
8/1
ABB: Buscar
Recursivamente
i n t ∗ s e a r c h ( n o d o t ∗ r a i z , i n t v a l u e ){
i f ( r a i z == NULL | | r a i z −>d a t o == v a l u e ) //{} o m i t i d a s
return raiz ;
e l s e i f ( v a l u e < r a i z −>d a t o )
r e t u r n s e a r c h ( r a i z −>h i j o i z q , v a l u e ) ;
e l s e i f ( v a l u e > r a i z −>d a t o ) // e l s e
r e t u r n s e a r c h ( r a i z −>h i j o d e r , v a l u e ) ;
Usando Puntero
i n t ∗ s e a r c h ( n o d o t ∗ r a i z , i n t v a l u e ){
nodo t ∗ rec = r a i z ;
w h i l e ( r e c !=NULL){
i f ( r e c−>d a t o == v a l u e ){
return rec ;
} e l s e i f ( v a l u e < r e c−>d a t o ){
r e c = r e c−>h i j o i z q ;
} e l s e i f ( v a l u e > r e c−>d a t o ){
r e c = r e c−>h i j o d e r ;
}
r e t u r n r e c ; // NULL s i no l o e n c u e n t r a o a r b o l v a c ı́ o
}
9/1
ABB: Insertar
Para poder insertar debemos buscar primero el lugar donde debe
realizarse la inserción. La idea es mantener el orden de nuestro ABB.
Nota: Si nuestro árbol no acepta elementos repetidos, al encontrar el
valor se detiene.
10/1
ABB: Insertar
Recursivamente
v o i d i n s e r t ( n o d o t ∗∗ r a i z , i n t v a l u e ){
i f (∗ r a i z == NULL){
∗ r a i z = malloc ( s i z e o f ( node t ) ) ;
(∗ r a i z )−> d a t o = v a l u e ;
(∗ r a i z )−> h i j o i z q = NULL ;
(∗ r a i z )−> h i j o d e r = NULL ;
}else i f ( v a l u e < (∗ r a i z )−>d a t o ){
i n s e r t (&((∗ r a i z )−> h i j o i z q ) , v a l u e ) ;
}else i f ( v a l u e > (∗ r a i z )−>d a t o ){
i n s e r t (&((∗ r a i z )−> h i j o d e r ) , v a l u e ) ;
}
}
11/1
ABB: Insertar
Cree el árbol binario que represente la siguiente secuencia de
enteros:
10 − 5 − 7 − 14 − 12 − 18 − 15
Spoiler
12/1
ABB: Insertar
Cree el árbol binario que represente la siguiente secuencia de
enteros:
10 − 5 − 7 − 14 − 12 − 18 − 15
Spoiler
12/1
ABB: Eliminar
Al igual que en insertar, deberemos buscar el nodo a eliminar. Pero para
poder eliminarlo, tendremos que considerar los siguientes casos:
Nodo objetivo es una hoja (no tiene hijos).
Nodo objetivo tiene un sólo hijo.
Nodo objetivo tiene dos hijos.
13/1
ABB: Eliminar hoja.
Es el caso más sencillo, solo corresponde a liberar el nodo desde el
puntero del padre.
14/1
ABB: Eliminar nodo con 1 hijo.
Caso intermedio. acá se elimina el nodo encontrado, pero su posición es
ocupada por su único hijo. Se eleva ese sub-árbol, un nivel.
15/1
ABB: Eliminar nodo con 2 hijos.
Caso recursivo o iterativo. Cuenta de dos pasos:
Reemplazar el nodo objetivo por una copia de su sucesor o
antecesor (uds. eligen).
Borrar el sucesor o antecesor original.
16/1
ABB: Insertar
Recursivamente
i n t d e l e t e ( n o d o t ∗∗ r a i z , i n t v a l u e ){
// ¿Cómo l o programan ?
// N e c e s i t a r á n a l g u n a f u n c i ón e x t r a .
}
17/1
Ejercicios
Para el siguiente conjunto {1, 4, 5, 10, 16, 17, 21}, dibuje
árboles binarios de búsqueda con altura 2, 3, 4, 5, y 6.
Escriba funciones recursivas para recorrer un árbol binario de
búsqueda en pre-orden y post-orden.
Asuma que tiene números entre 1 y 1000 en un árbol binario
de búsqueda y quiere buscar el nodo 363. ¿Cuál de las
siguientes secuencias de nodos NO podrı́a ser una secuencia
de nodos examinados en el árbol para llegar al nodo 363?
1 2, 252, 401, 398, 330, 344, 397, 363.
2 924, 220, 911, 244, 898, 258, 362, 363.
3 925, 202, 911, 240, 912, 245, 363.
4 2, 399, 387, 219, 266, 382, 381, 278, 363.
5 935, 278, 347, 621, 299, 392, 358, 363.
18/1
