PDF de programación - Estructuras de datos: Árboles binarios de búsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Estructuras de datos: Árboles binarios de

búsqueda, Montículos

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Table of Contents

1

Árboles binarios de búsqueda

2 Montículos

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Table of Contents

1

Árboles binarios de búsqueda

2 Montículos

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

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 árbol binario de búsqueda, el valor medio
de la profundidad es O(log n).

Si la inserción en un ABB no es aleatoria,
el tiempo computacional aumenta.

Para mantener el equilibrio: Árboles AVL, Splay Trees, . . .

La altura de n es el camino más largo de n a una hoja.

La altura de un árbol es la altura de la raíz.

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Operaciones básicas

Buscar: devuelve la posición 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 está 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
más pequeña, w, del subárbol derecho.

A continuación se elimina en el subárbol derecho el nodo con w
(que no tiene hijo izquierdo)

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Eliminación perezosa

Si se espera que el número de eliminaciones sea pequeño,
la eliminación perezosa es una buena estrategia.

Al eliminar un elemento, se deja en el árbol marcándolo
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 número de nodos reales en el árbol es igual al número de
nodos “eliminados”, se espera que la profundidad del árbol sólo
aumente en uno (¿por qué?).

La penalización de tiempo es pequeña.

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de árboles binarios de búsqueda (i)

tipo

PArbol = ˆNodo
Nodo = registro

Elemento : TipoElemento
Izquierdo, Derecho : PArbol

fin registro

ABB = PArbol

procedimiento CrearABB (var A)

A := nil

fin procedimiento

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de árboles binarios de búsqueda (ii)

función Buscar (x, A) : PArbol

si A = nil entonces devolver nil
sino si x = Aˆ.Elemento entonces devolver A
sino si x < Aˆ.Elemento entonces

devolver Buscar (x, Aˆ.Izquierdo)

sino devolver Buscar (x, Aˆ.Derecho)

fin función

función BuscarMin (A) : PArbol

si A = nil entonces devolver nil
sino si Aˆ.Izquierdo = nil entonces devolver A
sino devolver BuscarMin (Aˆ.Izquierdo)

fin función

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de árboles binarios de búsqueda (iii)

procedimiento Insertar (x, var A)

si A = nil entonces

nuevo (A);
si A = nil entonces error ‘‘sin memoria’’
sino

Aˆ.Elemento := x;
Aˆ.Izquierdo := nil;
Aˆ.Derecho := nil

sino si x < Aˆ.Elemento entonces
Insertar (x, Aˆ.Izquierdo)
sino si x > Aˆ.Elemento entonces
{ si x = Aˆ.Elemento : nada }

Insertar (x, Aˆ.Derecho)

fin procedimiento

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de árboles binarios de búsqueda (iv)

procedimiento Eliminar (x, var A)

si A = nil entonces error ‘‘no encontrado’’
sino si x < Aˆ.Elemento entonces

Eliminar (x, Aˆ.Izquierdo)

sino si x > Aˆ.Elemento entonces

sino

Eliminar (x, Aˆ.Derecho)
{ x = Aˆ.Elemento }

si Aˆ.Izquierdo = nil entonces

tmp := A; A := Aˆ.Derecho; liberar (tmp)

sino si Aˆ.Derecho = nil entonces

tmp := A; A := Aˆ.Izquierdo; liberar (tmp)

sino tmp := BuscarMin (Aˆ.Derecho);
Aˆ.Elemento := tmpˆ.Elemento;
Eliminar (Aˆ.Elemento, Aˆ.Derecho)

fin procedimiento

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Recorridos de un árbol (i)

En orden: Se procesa el subárbol izquierdo, el nodo actual y,
por último, el subárbol derecho. O(n)
procedimiento Visualizar (A)

si A <> nil entonces

Visualizar (Aˆ.Izquierdo);
Escribir (Aˆ.Elemento);
Visualizar (Aˆ.Derecho)

fin procedimiento

Post-orden: Ambos subárboles primero. O(n)
función Altura (A) : número

si A = nil entonces devolver -1
sino devolver 1 + max (Altura (Aˆ.Izquierdo),

fin función

Algoritmos

Árboles binarios de b úsqueda, Montículos

Altura (Aˆ.Derecho))

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Recorridos de un árbol (ii)

Pre-orden: El nodo se procesa antes. Ej: una función que
marcase cada nodo con su profundidad. O(n)
Orden de nivel: Todos los nodos con profundidad p se procesan
antes que cualquier nodo con profundidad p + 1.

Se usa una cola en vez de la pila implícita en la recursión. O(n)

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Table of Contents

1

Árboles binarios de búsqueda

2 Montículos

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Colas de prioridad

Permiten únicamente el acceso al mínimo (o máximo) elemento.
Operaciones básicas: insertar, eliminarMin (eliminarMax).
Implementaciones simples:

Listas enlazadas efectuando inserciones al frente, O(1), y
recorriendo la lista, O(n), para elminiar el mínimo (máximo).
Listas ordenadas: inserciones costosas, O(n),
eliminaciones eficientes, O(1).
Árboles binarios de búsqueda: tiempo de ejecución medio
O(log n) para ambas operaciones.

A pesar de que las eliminaciones no son aleatorias.
Se eliminan repetidamente nodos de un subárbol. No obstante, el
otro subárbol es aleatorio y tendría a lo sumo el doble de
elementos de los que debería. Y esto sólo incrementa en uno la
profundidad esperada.

Montículos: ambas operaciones se realizan en O(log n)
para el peor caso. No requieren apuntadores.

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Propiedades estructurales de los montículos

Un montículo es un árbol binario completo: todos los niveles
están llenos con la posible excepción del nivel más bajo, que se
llena de izquierda a derecha.
Un árbol binario completo de altura h tiene entre 2h y 2h+1 − 1
nodos.

Su altura es la parte entera de log2 n.

Esta regularidad facilita su representación mediante un vector.
Para cualquier elemento en la posición i del vector, el hijo
izquierdo está en la posición 2i, el hijo derecho en 2i + 1, y el
padre en i ÷ 2.

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Propiedades de orden de los montículos

El mínimo (o máximo) está en la raíz.
Y como todo subárbol es también un montículo, todo nodo debe
ser menor (mayor) o igual que todos sus descendientes.

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Ejemplo de montículo de máximos

Algoritmos

Árboles binarios de b úsqueda, Montículos

151312895875345123456789101112151247581393585 Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de montículos (i)

tipo Montículo = registro

Tamaño monticulo : 0..Tamaño máximo
Vector montículo : vector [1..Tamaño máximo]

de Tipo elemento

fin registro

procedimiento Inicializar Montículo ( M )

M.Tamaño monticulo := 0

fin procedimiento

función Montículo Vacío ( M ) : test

return M.Tamaño monticulo = 0

fin función

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de montículos (ii)

procedimiento Flotar ( M, i ) { privado }

mientras i > 1 y

M.Vector montículo[i div 2] < M.Vector montículo[i]

hacer intercambiar M.Vector montículo[i div 2] y

M.Vector montículo[i];

i := i div 2

fin mientras

fin procedimiento
procedimiento Insertar ( x, M )

si M.Tamaño monticulo = Tamaño máximo entonces

error Monticulo lleno

sino M.Tamaño monticulo := M.Tamaño monticulo + 1;
M.Vector monticulo[M.Tamaño monticulo] := x;
Flotar ( M, M.Tamaño monticulo )

fin procedimiento

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de montículos (iii)

procedimiento Hundir ( M, i ) { privado }

repetir

HijoIzq := 2*i;
HijoDer := 2*i+1;
j := i;
si HijoDer <= M.Tamaño monticulo y

M.Vector montículo[HijoDer] > M.Vector montículo[i]

entonces i := HijoDer;
si HijoIzq <= M.Tamaño monticulo y

M.Vector montículo[HijoIzq] > M.Vector montículo[i]

entonces i := HijoIzq;
intercambiar M.Vector montículo[j] y
M.Vector montículo[i];

hasta j=i {Si j=i el nodo alcanzó su posición final}

fin procedimiento

Algoritmos

Árboles binarios de b úsqueda, Montículos

Árboles binarios de b úsqueda
Montículos

Pseudoc ódigo

Implementación de montículos (iv)

función EliminarMax ( M ) : Tipo elemento

si Montículo Va