muchos

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Estructuras de datos: Arboles binarios de
busqueda, Mont´culos
ı
´
Algoritmos
´
´
Dep. de Computacion - Fac. de Informatica
˜
Universidad de A Coruna

Santiago Jorge
sjorge@udc.es

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

Table of Contents

1

´Arboles binarios de busqueda
´

2

Mont´culos
ı

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Referencias bibliograficas

´
M. A. Weiss. Arboles. En Estructuras de datos y algoritmos,
´
cap´tulo 4, paginas 93–154. Addison-Wesley Iberoamericana,
ı
1995.
M. A. Weiss. Colas de prioridad (mont´culos). EnEstructuras de
ı
´
datos y algoritmos, cap´tulo 6, paginas 181–220. Addison-Wesley
ı
Iberoamericana, 1995.
˜
´
R. Pena Mar´. Implementacion de estructuras de datos. En
ı
˜
´
Diseno de Programas. Formalismo y abstraccion, cap´tulo 7,
ı
´
´
paginas 257–290. Prentice Hall, segunda edicion, 1998.
G. Brassard y T. Bratley. Estructura de datos. En Fundamentos
´
de algoritmia, cap´tulo5, paginas 167–210. Prentice Hall, 1997.
ı

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Pseudocodigo

Table of Contents

1

´
Arboles binarios de busqueda
´

2

Mont´culos
ı

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´Pseudocodigo

Preliminares

El camino de un nodo n1 a otro nk es la secuencia
de nodos n1 , n2 , . . . , nk tal que ni es el padre de ni +1 .
La profundidad de un nodo n es la longitud del camino
entre la ra´z y n.
ı
La ra´z tiene profundidad cero.
ı

´
Para un arbol binario de busqueda, el valor medio
´
de la profundidad es O (log n).
´
Si la insercion en un ABB no es aleatoria,
eltiempo computacional aumenta.
´
Para mantener el equilibrio: Arboles AVL, Splay Trees, . . .

´
La altura de n es el camino mas largo de n a una hoja.
´
La altura de un arbol es la altura de la ra´z.
ı

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Pseudocodigo

´
Operaciones basicas

´
Buscar: devuelvela posicion del nodo con la clave x.

Insertar: coloca la clave x. Si ya estuviese,
no se hace nada (o se “actualiza” algo).
Eliminar: borra la clave x.
´
Si x esta en una hoja, se elimina de inmediato.
Si el nodo tiene un hijo, se ajusta un apuntador
antes de eliminarlo.
Si el nodo tiene dos hijos, se sustituye x por la clave
´
˜
´
mas pequena, w, del subarbol derecho.
´
´
Acontinuacion se elimina en el subarbol derecho el nodo con w
(que no tiene hijo izquierdo)

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Pseudocodigo

´
Eliminacion perezosa

˜
Si se espera que el numero de eliminaciones sea pequeno,
´
´
la eliminacion perezosa es una buena estrategia.
´
´
Al eliminar unelemento, se deja en el arbol marcandolo
como eliminado.
Habiendo claves duplicadas, es posible decrementar el campo
con la frecuencia de apariciones.
Si una clave eliminada se vuelve a insertar, se evita la sobrecarga
de asignar un nodo nuevo.

´
Si el numero de nodos reales en el arbol es igual al numero de
´
´
´
´
nodos “eliminados”, se espera que la profundidad del arbol solo
´aumente en uno (¿por que?).
´
˜
La penalizacion de tiempo es pequena.

Algoritmos

´
Arboles binarios de busqueda, Mont´culos
´
ı

´
Arboles binarios de busqueda
´
Mont´culos
ı

´
Pseudocodigo

´
´
Implementacion de arboles binarios de busqueda (i)
´

tipo
PNodo = ˆNodo
Nodo = registro
Elemento : TipoElemento
Izquierdo, Derecho : PNodo
fin registro
ABB = PNodo...