PDF de programación - Estructura de Datos y de la Información - Árboles Binarios de Búsqueda

Estructura de Datos y de la

Información

Árboles Binarios de Búsqueda

Mosqueira ReyRey
Eduardo Mosqueira
Eduardo
Bertha Guijarro Berdiñas
Berdiñas
Bertha Guijarro
Mariano Cabrero Canosa
Mariano Cabrero Canosa

LIDIALIDIA
Laboratorio de Investigación y Desarrollo
Laboratorio de Investigación y Desarrollo
en Inteligencia Artificial
en Inteligencia Artificial

Departamento de Computación
Departamento de Computación
Universidade da Coruña
Universidade da Coruña

1

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

Motivación
•• Motivación
La búsqueda en una lista dinámica ordenada es poco eficiente:
** La búsqueda en una lista dinámica ordenada es poco eficiente:

•• Por término medio habrá que recorrerse la mitad de la lista para

Por término medio habrá que recorrerse la mitad de la lista para verificar si
verificar si
un elemento está o no en ella.
un elemento está o no en ella.
Si la lista está en memoria principal no habrá problema, pero si la lista es una
la lista es una
tabla de una base de datos almacenada en memoria secundaria el rendimiento
endimiento
tabla de una base de datos almacenada en memoria secundaria el r
se verá severamente afectado
se verá severamente afectado

•• Si la lista está en memoria principal no habrá problema, pero si

En una lista ordenada estática se pueden aplicar algoritmos de
** En una lista ordenada estática se pueden aplicar algoritmos de
búsqueda mejores (p.ep.e., dicotómica), pero el almacenamiento es
., dicotómica), pero el almacenamiento es
búsqueda mejores (
limitado
limitado

Solución: Árboles Binarios de Búsqueda o
•• Solución: Árboles Binarios de Búsqueda o
ABBABB
Un ABB es un árbol binario en el que sus TODOS sus
** Un ABB es un árbol binario en el que sus TODOS sus
nodos verifican:
nodos verifican:

k

•• Tienen asociada una clave de ordenación
Tienen asociada una clave de ordenación
Su subárbol izquierdo (si existe) contiene valores menores
•• Su subárbol izquierdo (si existe) contiene valores menores
que su clave y el subárbol derecho (si existe) contiene
que su clave y el subárbol derecho (si existe) contiene
valores mayores.
valores mayores.

claves
menores

que k

claves
mayores

que k

2

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

Ventajas
•• Ventajas
El número de accesos al árbol es menor que en una lista enlazada
** El número de accesos al árbol es menor que en una lista enlazada
Por ejemplo, en un árbol lleno que tenga nn nodos el camino más largo
nodos el camino más largo
** Por ejemplo, en un árbol lleno que tenga
que hay que recorrer es log22((nn+1), +1),
que hay que recorrer es log

=15,
•• Si Si nn=15,
–– recorrido máximo en un ABB=log
–– recorrido máximo en una lista es

recorrido máximo en un ABB=log2216=4
16=4
recorrido máximo en una lista es nn=15=15

•• Si n=1023,
Si n=1023,

–– recorrido máximo en un ABB=log
–– recorrido máximo en una lista es

1024=10
recorrido máximo en un ABB=log221024=10
recorrido máximo en una lista es nn=1023
=1023

46

25

73

12

36

62

90

5

15

30

40

54

70

78

95

3

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

••

Inconvenientes
Inconvenientes
Árboles equilibrados
** Árboles equilibrados

Las búsquedas son más eficientes cuando el árbol está equilibradoo
•• Las búsquedas son más eficientes cuando el árbol está equilibrad
•• Un árbol equilibrado es aquel en el que las ramas izquierda y
Un árbol equilibrado es aquel en el que las ramas izquierda y
derecha de cada nodo tienen aproximadamente la misma altura (el
derecha de cada nodo tienen aproximadamente la misma altura (el
árbol lleno sería el árbol equilibrado perfecto con todos los nodos dos
árbol lleno sería el árbol equilibrado perfecto con todos los no
con subárboles izqizq y y dchdch de la misma altura)
de la misma altura)
con subárboles
Si los nodos que se van insertando en el árbol aparecen en orden
•• Si los nodos que se van insertando en el árbol aparecen en orden
aleatorio el árbol tenderá a ser equilibrado
aleatorio el árbol tenderá a ser equilibrado

Árboles “degenerados”
** Árboles “degenerados”

46

73

•• Si los nodos del árbol que se van insertando en el árbol aparece

•• El caso peor ocurre cuando el árbol está “degenerado”, es decir,
El caso peor ocurre cuando el árbol está “degenerado”, es decir,
sigue siendo un árbol pero su estructura es equivalente a una lista sta
sigue siendo un árbol pero su estructura es equivalente a una li
enlazada (todos los nodos sólo tienen un hijo)
enlazada (todos los nodos sólo tienen un hijo)
Si los nodos del árbol que se van insertando en el árbol aparecen n
con un orden determinado el árbol tenderá a ser degenerado.
con un orden determinado el árbol tenderá a ser degenerado.
Los datos en la realidad suelen tener un cierto grado de
** Los datos en la realidad suelen tener un cierto grado de
orden por lo que para que los árboles BB sean eficientes es
orden por lo que para que los árboles BB sean eficientes es
necesario hacer reequilibrados ⇒⇒⇒⇒⇒⇒⇒⇒ áárboles AVL
rboles AVL
necesario hacer reequilibrados

árbol

degenerado

90

95

4

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

Especificación del TAD Árbol Binario de Búsqueda
•• Especificación del TAD Árbol Binario de Búsqueda
Tipos
** Tipos

••

tArbolBin y y tInfo
tInfo
tArbolBin

Funciones (se resaltan las nuevas)
** Funciones (se resaltan las nuevas)

•• Generadoras
Generadoras

ArbolVacio fi
–– ArbolVacio
tArbolBin
tArbolBin
tInfo) ) fi
tArbolBin, , tInfo
InsertarABB ((tArbolBin
–– InsertarABB

tArbolBin, boolean
tArbolBin, boolean

•• Observadoras
Observadoras

HijoIzquierdo(tArbolBin) ) fi
–– HijoIzquierdo(tArbolBin
HijoDerecho(tArbolBin) ) fi
–– HijoDerecho(tArbolBin
tArbolBin) ) fi
–– RaizRaiz ((tArbolBin
tInfo
tInfo
tArbolBin) ) fi
EsArbolVacio ((tArbolBin
–– EsArbolVacio
boolean
boolean
tInfo) ) fi
tArbolBin, , tInfo
BusquedaABB ((tArbolBin
–– BusquedaABB

tArbolBin
tArbolBin
tArbolBin
tArbolBin

tArbolBin
tArbolBin

•• Destructoras
Destructoras

–– EliminarArbol
–– EliminarABB

tArbolBin) ) fi
EliminarArbol ((tArbolBin
tInfo) ) fi
tArbolBin, , tInfo
EliminarABB ((tArbolBin

tArbolBin
tArbolBin

tArbolBin, boolean
tArbolBin, boolean

** Funciones internas de la implementaci

Funciones internas de la implementacióónn

–– ConstruirArbol

ConstruirArbol ((tArbolBin

tArbolBin, , tInfo

tArbolBin) ) fi
tInfo, , tArbolBin

tArbolBin, boolean
tArbolBin, boolean

5

fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

•• Búsqueda (

Se compara la clave a buscar con la raíz del arbol
arbol

Búsqueda (pseudocódigo
pseudocódigo))
** Se compara la clave a buscar con la raíz del
Si el árbol es NULO la búsqueda acaba sin éxito
•• Si el árbol es NULO la búsqueda acaba sin éxito
•• Si clave = valor de la raíz la búsqueda acaba con éxito
Si clave = valor de la raíz la búsqueda acaba con éxito
izquierdo
Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo
•• Si clave < valor de la raíz la búsqueda continúa por el subárbol
•• Si clave > valor de la raíz la búsqueda continúa por el subárbol
Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho
derecho

Búsqueda (código y ejemplo)
•• Búsqueda (código y ejemplo)



function BuscaABB(A:tArbolBin; valor:tInfo): tArbolBin;
begin
if A=nil
then BuscaABB:=nil
else
if valor=A^.Info
then BuscaABB:=A
else if valor<A^.info
then BuscaABB:=BuscaABB(A^.HI, valor)
else BuscaABB:=BuscaABB(A^.HD, valor)
end;

30 < 46

46

25

30 > 25

73

30 < 36

12

36

62

90

30

54

70

6

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

••

Inserción (pseudocódigo
pseudocódigo))
Inserción (
** Se compara la clave a insertar con la raíz del

Se compara la clave a insertar con la raíz del arbol
arbol

•• Si el árbol es NULO insertamos una hoja con la clave en esa posi
Si el árbol es NULO insertamos una hoja con la clave en esa posiciónción
•• Si clave < valor de la raíz la búsqueda continúa por el subárbol
Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo
izquierdo
derecho
•• Si clave > valor de la raíz la búsqueda continúa por el subárbol
Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho
•• Si clave = valor (claves repetidas) no se hace nada. Este funcio
Si clave = valor (claves repetidas) no se hace nada. Este funcionamiento podría
namiento podría
ser distinto: reemplazar el antiguo con el nuevo, lanzar un error, permitir
r, permitir
ser distinto: reemplazar el antiguo con el nuevo, lanzar un erro
duplicados, etc.
duplicados, etc.

••

Inserción (código y ejemplo)
Inserción (código y ejemplo)



function InsertarABB(var A:tArbolBin; valor:tInfo):boolean;
begin
if (A=nil) then
InsertarABB:=ConstruirArbol(nil, nil, valor, A)
else
if valor<A^.info
then InsertarABB:=InsertarABB(A^.HI, valor)
else if valor>A^.info
then InsertarABB:=InsertarABB(A^.HD, valor)
else InsertarABB:=true
end;



40 < 46



INSERCIÓN CLAVE 40

46

25

40 > 25

73

12

36

40 > 36

árbol nil
se crea
el nodo

62

90

30

40

54

70

7

Árboles

Árboles Binarios de Búsqueda

LIDIALIDIA

•• Borrado (

Borrado (pseudocódigo
pseudocódigo))
Se busca en el árbol la posición del nodo a eliminar
** Se busca en el árbol la posición del nodo a eliminar
Si es un nodo hoja ⇒⇒⇒⇒⇒⇒⇒⇒ se actualiza el puntero del padre a nil y se borra
se actualiza el puntero del padre a nil y se borra
** Si es un nodo hoja
el nodo
el nodo
Si es un nodo con un solo hijo ⇒⇒⇒⇒⇒⇒⇒⇒ se actualiza el puntero del padre para
se actualiza el puntero del padre para
que apunte al hijo y se borra el nodo
que apunte al hijo y se borra el nodo
Si es un nodo con dos hijos
** Si es un nodo con dos hijos

** Si es un nodo con un solo hij