Informatica

´ 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 binariosde 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). En Estructuras de ı ´ datos yalgoritmos, 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´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 lasecuencia 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, el tiempo computacional aumenta.
´ Para mantener el equilibrio: Arboles AVL, SplayTrees, . . .

´ 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: devuelve la posicion del nodo con la clave x.

Insertar: coloca la clave x. Si ya estuviese, no sehace 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.
´ ´ A continuacion 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 un elemento, se deja en el arbol marcandolo como eliminado. Habiendo claves duplicadas, es posible decrementar el campo con lafrecuencia 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 procedimiento CrearABB (var A) A := nil fin procedimiento

Algoritmos

´ Arboles binarios de busqueda, Mont´culos ´ ı

´ Arboles binarios de busqueda ´...