arboles - estructura de datos

´
Arboles
binarios de busqueda
´
Mont´ıculos

´
Estructuras de datos: Arboles
binarios de
busqueda,
Mont´ıculos
´
Algoritmos
´ - Fac. de Informatica
´
Dep. de Computacion
˜
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
´

2Mont´ı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). En Estructuras de
´
datos y algoritmos, cap´ıtulo 6, paginas
181–220.Addison-Wesley
Iberoamericana, 1995.
˜ Mar´ı. Implementacion
´ de estructuras de datos. En
R. Pena
˜ de Programas. Formalismo y abstraccion,
´ cap´ıtulo 7,
Diseno
´
´ 1998.
paginas
257–290. Prentice Hall, segunda edicion,
G. Brassard y T. Bratley. Estructura de datos. En Fundamentos
´
de algoritmia, cap´ıtulo 5, 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 profundidadde 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).
´ en un ABB no es aleatoria,
Si la insercion
el tiempo computacional aumenta.
´
Para mantener el equilibrio: Arboles
AVL, Splay Trees, . . .

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

Algoritmos

´
Arboles
binarios de busqueda,
´
Mont´ıculos

´
Arboles
binarios de busqueda
´
Mont´ıculos

´
Pseudocodigo

´
Operaciones basicas

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

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 elnodo tiene un hijo, se ajusta un apuntador
antes de eliminarlo.
Si el nodo tiene dos hijos, se sustituye x por la clave
´ pequena,
˜ w, del subarbol
´
mas
derecho.
´ se elimina en el subarbol
´
A continuacion
derecho el nodo con w
(que no tiene hijo izquierdo)

Algoritmos

´
Arboles
binarios de busqueda,
´
Mont´ıculos

´
Arboles
binarios de busqueda
´
Mont´ıculos

´
Pseudocodigo

´ perezosaEliminacion

˜
Si se espera que el numero
de eliminaciones sea pequeno,
´
´ perezosa es una buena estrategia.
la eliminacion
´
´
Al eliminar un elemento, 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 elnumero
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?).
´ de tiempo es pequena.
˜
La penalizacion

Algoritmos

´
Arboles
binarios de busqueda,
´
Mont´ıculos

´
Arboles
binarios de busqueda
´
Mont´ıculos

´
Pseudocodigo

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

tipo
PNodo = ˆNodo
Nodo= registro
Elemento : TipoElemento
Izquierdo, Derecho : PNodo
fin registro
ABB = PNodo
procedimiento CrearABB (var A)
A := nil
fin procedimiento

Algoritmos

´
Arboles
binarios de busqueda,
´
Mont´ıculos

´
Arboles
binarios de busqueda
´
Mont´ıculos

´
Pseudocodigo

´ de arboles
´
Implementacion
binarios de busqueda
(ii)
´
funci´
on Buscar (x, A) : PNodo
si A = nil entonces devolver nil
sino...