Tipos abstractos

Los tipos de datos abstractos son aquellos que:

Se definen especificando constructores/operaciones.
Pueden haber varias implementaciones para el mismo TAD.
El problema muestra qué necesitamos representar y qué operaciones tener.

Para especificarlo debemos:

Indicar su nombre
Especificar constructores $(\proc, \; \fun)$ los cuales permiten crear elementos del tipo especificado.
Especificar operaciones $(\proc, \; \fun)$ que permiten manipular elementos del tipo especificado.
Especificar tipos de cada constructor/operación, explicar su función mediante lenguaje natural
Definir precondiciones (restricciones)
Especificar operaciones de destrucción que liberan memoria del tipo (en caso necesario)

Su implementación:

Definir un nuevo tipo con el nombre de TAD especificado. Se utilizan tipos concretos/definidos.
Implementar constructores respetando los tipos.
Implementar operaciones respetando los tipos.
Implementar operacion de destrucción si es que se ha reservado al contstruir los elementos.
Pueden surgir nuevas restricciones que dependen de cómo implementamos el tipo.
Pueden necesitarse operaciones auxiliares no especificadas en el tipo.

Listas

Colecciones de elementos de un mismo tipo, de tamaño variable. Todas son vacías o tienen un elemento al comienzo.

Especificación de listas

\begin{aligned} & \\ &\spec \; List \; \of \; \where \\ &\\ &\cons \\ &\quad \fun \; empty() \; \ret \; l : List \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea una lista vacía} \;\; -\} \\ &\\ &\quad \proc \; addl (\bfin \; e : T, \; \inout \; l : List \; \of \; T) \\ &\quad\{- \;\; \textnormal{Agrega el elemento} \; e \; \textnormal{al comienzo de una lista} \; l \;\; -\} \\ &\\ &\destroy \\ &\quad \proc \; destroy(\inout \; l : List \; \of \; T) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso que sea necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_empty(l : List \; \of \; T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; l \;\textnormal{es vacía.} \;\; -\} \\ &\\ &\quad \fun \; head(l : List \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el primer elemento de} \; l \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty(l) \;\; -\} \\ &\\ &\quad \proc \; tail(\inout \; l : List \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Elimina el primer elemento de} \; l \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty(l) \;\; -\} \\ &\\ &\quad \proc \; addr(\inout \; l : List \; \of \; T, \; \bfin \; e : T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Agrega el elemento} \; e \; \textnormal{al final de la lista} \; l \;\; -\} \\ &\\ &\quad \fun \; length(l : List \; \of \; T) \; \ret \; n : \nat \\ &\quad\{- \;\; \textnormal{Devuelve la cantidad de elementos de} \; l \;\; -\} \\ &\\ &\quad \proc \; concat(\inout \; l : List \; \of \; T, \; \bfin \; l0 : List \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Agrega al final de} \; l \; \textnormal{todos los elementos de} \; l- \; \textnormal{en el mismo orden} \;\; -\} \\ &\\ &\quad \fun \; index(l : List \; \of \; T, \; n : \nat) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el} \; n\textnormal{ésimo elemento de la lista} \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; length(l) > n \;\; -\} \\ &\\ &\quad \proc \; take(\inout \; l : List \; \of \; T, \; n : \nat) \\ &\quad\{- \;\; \textnormal{Deja en} \; l \; \textnormal{los primeros} n \; \textnormal{elementos, elimina el resto} \;\; -\} \\ &\\ &\quad \proc \; drop(\inout \; l : List \; \of \; T, \; n : \nat) \\ &\quad\{- \;\; \textnormal{Elimina los primeros} \; n \; \textnormal{de} \; l \;\; -\} \\ &\\ &\quad \fun \; copy\_list(l1 : List \; \of \; T) \; \ret \; l2 : List \; \of \; T \\ &\quad\{- \;\; \textnormal{Copia los elementos de} \; l1 \; \textnormal{en la nueva lista} \; l2 \;\; -\} \\ &\\ \end{aligned}

Para usar el tipo de las listas basta con especificarlas. No es necessario conocer la implementación para usar el TAD.

Sus constructores $empty, \; addl$ permiten crear listas vacías o agregar un elemento nuevo, respectivamente.
Las operaciones permiten manipular listas de acuerdo a la funcionalidad del TAD.

Ejemplo de uso:

\begin{aligned} &\fun \; promedio(l : List \; \of \; real) \; \ret \; r : \real \\ &\quad \var \; largo : \nat \\ &\quad \var \; elem : \real \\ &\quad \var \; laux : List \; \of \; \real \\ &\\ &\quad laux := copy(l) \\ &\quad r:=0.0 \\ &\quad largo := length(l) \\ &\quad \do \; (\textnormal{not} \; is\_empty(laux)) \\ &\quad \quad elem := head(laux) \\ &\quad \quad r := r + elem \\ &\quad \quad tail(laux) \\ &\quad \od \\ &\quad destroy(laux) \\ &\quad r:= r \; / \; largo \\ &\bfend \; \proc \end{aligned}

Implementación de listas

La implementación del TAD lista utiliza punteros, dicha implementación es una lista enlazada.
Cada elemento de la lista estará alojado en un nodo conteniendo además un puntero hacia el siguiente.
Una lista será un puntero a un nodo (se sigue un patrón recursivo)

\begin{aligned} &\impt \; List \; \of \; T \; \where \\ &\\ &\type \; Node \; \of \; T = \tuple \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad elem : T \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad next : \pointer \; \too \; (Node \; \of \; T) \\ &\quad\quad\quad\quad\quad\quad\quad\quad \; \bfend \; \tuple \\ &\\ &\type \; List \; \of \; T = \pointer \; \too \; (Node \; \of \; T) \\ \end{aligned}

El constructor $empty$ (lista vacía) se implementa fácilmente con el puntero $\null$

\begin{aligned} &\fun \; empty() \; \ret \; l : List \; \of \; T \\ &\quad l := \null \\ &\bfend \; \fun \end{aligned}

Lo que falta es la implementación del constructor $addl$ (para agregar un elemento nuevo):

Para agregar un elemento a una lista $l$ , definimos un puntero $p$ y reservamos memoria al mismo.
El puntero $p$ apunta a un nodo (el cual contiene un elemento y un puntero).
El campo $elem$ que apunta el puntero $p$ es el elemento $e$ que queremos agregar a $l$

Ahora definimos el siguiente elemento de la lista, $next$ . El cual, es el que ya está apuntado por la lista $l$

Entonces $l$ no debe apuntar a $e_1$ sino a $e$ (nuevo primer elemento)

En el código tenemos:

\begin{aligned} &\proc \; addl (\bfin \; e : T, \; \inout \; l : List \; \of \; T) \\ &\quad \var \; p : \pointer \; \too \; (Node \; \of \; T) \\ &\quad alloc(p) \\ &\quad p \to elem := e \\ &\quad p \to next := l \\ &\quad l := p \\ &\bfend \; \proc \\ &\\ &\fun \; is\_empty(l : List \; \of \; T) \; \ret \; b : \bool \\ &\quad b := (l = \null) \\ &\bfend \; \fun \\ &\\ &\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty(l) \;\; -\} \\ &\fun \; head(l : List \; \of \; T) \; \ret \; e : T \\ &\quad e := (l \to elem) \\ &\bfend \; \fun \\ &\\ &\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty(l) \;\; -\} \\ &\proc \; tail(\inout \; l : List \; \of \; T) \\ &\quad \var \; p : \pointer \; \too \; (Node \; \of \; T) \\ &\quad p := l \\ &\quad l := l \to next \\ &\quad free(p) \\ &\bfend \; \proc \\ &\\ &\proc \; addr(\inout \; l : List \; \of \; T, \; \bfin \; e : T) \\ &\quad var \; p,q : \pointer \; \too \; (Node \; \of \; T) \\ &\quad alloc(p) \\ &\quad q \to elem := e \\ &\quad q \to next := \null \\ &\quad \if \; \neg is\_empty(l) \; \then \\ &\quad\quad p := l \\ &\quad\quad \while \; (p \to next \not=\null) \; \do \\ &\quad\quad\quad p := p \to next \\ &\quad\quad \od \\ &\quad\quad p \to next := q \\ &\quad \else \\ &\quad\quad l := q \\ &\quad \fi \\ &\bfend \; \proc \\ &\\ &\fun \; length(l : List \; \of \; T) \; \ret \; n : \nat \\ &\quad \var \; p : \pointer \; \too \; (Node \; \of \; T) \\ &\quad n := 0 \\ &\quad p := l \\ &\quad \while \; (p \not=\null) \; \do \\ &\quad \quad n := n + 1 \\ &\quad \quad p := p \to next \\ &\quad \od \\ &\bfend \; \fun \\ \end{aligned}

Contador

El TAD contador se define por sus operaciones de inicializar un valor, incrementarlo, comprobar si su valor es el inicial y decrementarlo en caso de no serlo.

La inicialización e incrementación son los constructores (generan todos los valores posibles del contador).
La comprobación solo examina el contador,
La decrementación no genera más valores que los obtenibles por inicializar/incrementar (no se decrementa si el valor es nulo)

Especificación de Contador

\begin{aligned} &\spec \; Counter \; \where \\ &\\ &\cons \\ &\quad \proc \; init(\out \; c: Counter) \\ &\quad\{- \;\; \textnormal{Crea un contador inicial} \;\; -\} \\ &\\ &\quad \proc \; inc(\inout \; c : Counter) \\ &\quad\{- \;\; \textnormal{Incrementa el contador}\; c \;\; -\} \\ &\\ &\destroy \\ &\quad \proc \; destroy(\inout \; c : Counter) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_init(c : Counter) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; c \;\textnormal{es el valor inicial} \;\; -\} \\ &\\ &\quad \proc \; dec(\inout \; c : Counter) \\ &\quad\{- \;\; \textnormal{Decrementa el contador} \; c \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_init(c) \;\; -\} \\ \end{aligned}

Implementación de Contador

La implementación de un contador es sencilla, se puede hacer con un natural.

\begin{aligned} &\impt \; Counter \; \where \\ &\\ &\type \; Counter = \nat \\ &\\ &\proc \; init(\out \; c : Counter) \\ &\quad c := 0 \\ &\bfend \; \proc \\ &\\ &\proc \; inc(\inout \; c : Counter) \\ &\quad c := c + 1 \\ &\bfend \; \proc \\ &\\ &\fun \; is\_init(c : Counter) \; \ret \; b : \bool \\ &\quad b := (c = 0) \\ &\bfend \; \fun \\ &\\ &\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_init(c) \;\; -\} \\ &\proc \; dec(\inout \; c : Counter) \\ &\quad c := c - 1 \\ &\bfend \; \proc \\ &\\ &\proc \; destroy(\inout \; c : Counter) \\ &\quad \skip \\ &\bfend \; \proc \\ \end{aligned}

Todas las operaciones son $\bigO(1)$ (constantes).

Pila

Una pila es una colección de datos de mismo tipo inicializada en vacía. Se pueden apilar y desapilar elementos, comprobar si hay primer elemento o examinarlo.
La pila sigue el principio LIFO (Last In, First Out)

Especificación de pila

\begin{aligned} &\spec \; Stack \; \of \; T \; \where \\ &\\ &\cons \\ &\quad \fun \; empty\_stack() \; \ret \; s: Stack \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea una pila vacía} \;\; -\} \\ &\\ &\quad \proc \; push(\bfin \; e : T, \; \inout \; s : Stack \; \of \; T) \\ &\quad\{- \;\; \textnormal{Agrega el elemento} \; e \; \textnormal{al tope de la pila} \; s \;\; -\} \\ &\\ &\destroy \\ &\quad \proc \; destroy(\inout \; s : Stack \; \of \; T) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_empty\_stack(s : Stack \; \of \; T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; s \;\textnormal{está vacía} \;\; -\} \\ &\\ &\quad \fun \; top(s : Stack \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el elemento en el tope de} \; s \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_stack(s) \;\; -\} \\ &\\ &\quad \proc \; pop(\inout \; s : Stack \; \of \; T) \\ &\quad\{- \;\; \textnormal{Elimina el elemento en el tope de} \; s \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_stack(s) \;\; -\} \\ &\\ &\quad \fun \; is\_full(s : Stack) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \; \textnormal{si} \; s \; \textnormal{está llena} \;\; -\} \\ \end{aligned}

Implementación de pila

Se puede utilizar un arreglo o una lista enlazada para implementar una pila, en este caso se usará un arreglo:

\begin{aligned} &\impt \; Stack \; \of \; T \; \where \\ &\\ &\type \; Stack \; \of \; T = \tuple \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad elems: \array[1..N] \; \of \; T \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad size: \nat \\ &\quad\quad\quad\quad\quad\quad\quad\quad \;\; \bfend \; \tuple \\ &\\ &\proc \; empty(\out \; s: Stack) \\ &\quad s.size := 0 \\ &\bfend \; \proc \\ &\\ &\proc \; push(\bfin \; e : T, \; \inout \; s : Stack) \\ &\quad s.size := s.size + 1 \\ &\quad s.elems[s.size] := e \\ &\bfend \; \proc \\ &\\ &\fun \; top(s: Stack) \; \ret \; e : T \\ &\quad e := s.elems[s.size] \\ &\bfend \; \fun \\ &\\ &\proc \; pop(\inout \; s : Stack) \\ &\quad s.size := s.size - 1 \\ &\bfend \; \proc \\ &\\ &\fun \; is\_empty\_stack(s : Stack) \; \ret \; b : \bool \\ &\quad b := (s.size = 0) \\ &\bfend \; \fun \\ &\\ &\fun \; is\_full(s : Stack) \; \ret \; b : \bool \\ &\quad b := (s.size = N) \\ &\bfend \; \fun \\ &\\ &\proc \; destroy(\inout \; s : Stack) \\ &\quad \while \; (\neg is\_empty\_stack(s)) \; \do \\ &\quad\quad pop(s) \\ &\quad \od \\ &\bfend \; \proc \\ \end{aligned}

Cola

Una cola es una colección de datos de mismo tipo inicializada en vacía. Se puede encolar y decolar elementos, comprobar si es vacía, o examinar el primer elemento.
La cola sigue el principio FIFO (First In, First Out)

Especificación de cola

\begin{aligned} &\spec \; Queue \; \of \; T \; \where \\ &\\ &\cons \\ &\quad \fun \; empty\_queue() \; \ret \; q: Queue \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea una cola vacía} \;\; -\} \\ &\\ &\quad \proc \; enqueue(\bfin \; q : Queue \; \of \; T, \; \inout \; e : T) \\ &\quad\{- \;\; \textnormal{Agrega el elemento} \; e \; \textnormal{al final de la cola} \; q \;\; -\} \\ &\\ &\destroy \\ &\quad \proc \; destroy(\inout \; q : Queue \; \of \; T) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_empty\_queue(q : Queue \; \of \; T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; q \;\textnormal{está vacía} \;\; -\} \\ &\\ &\quad \fun \; first(q : Queue \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el elemento al comienzo de} \; q \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_queue(q) \;\; -\} \\ &\\ &\quad \proc \; deq ueue(\inout \; q : Queue \; \of \; T) \\ &\quad\{- \;\; \textnormal{Elimina el elemento al comienzo de} \; q \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_queue(q) \;\; -\} \\ \end{aligned}

Implementación de cola

Se puede utilizar un arreglo o una lista enlazada para implementar una pila, en este caso se usará un arreglo:

\begin{aligned} &\impt \; Queue \; \of \; T \; \where \\ &\\ &\type \; Queue \; \of \; T = \tuple \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad elems: \array[0..N-1] \; \of \; T \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad fst: \nat \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad size: \nat \\ &\quad\quad\quad\quad\quad\quad\quad\quad \;\;\; \bfend \; \tuple \\ &\\ &\proc \; empty(\out \; q: Queue) \\ &\quad q.fst := 0 \\ &\quad q.size := 0 \\ &\bfend \; \proc \\ &\\ &\proc \; enqueue(\inout \; q : Queue, \; \bfin \;e: elem) \\ &\quad q.elems[(q.fst + q.size) \; \textnormal{ mod } \; N] := e \\ &\quad q.size := q.size + 1 \\ &\bfend \; \proc \\ &\\ &\fun \; first(q : Queue) \; \ret \; e : T \\ &\quad e := q.elems[q.fst] \\ &\bfend \; \fun \\ &\\ &\proc \; dequeue(\inout \; q : Queue) \\ &\quad q.size := q.size - 1 \\ &\quad q.fst := (q.fst + 1) \; \textnormal{ mod } \; N \\ &\bfend \; \proc \\ &\\ &\fun \; is\_empty\_queue(q : Queue) \; \ret \; b : \bool \\ &\quad b := (q.size = 0) \\ &\bfend \; \fun \\ &\\ &\fun \; is\_full(q : Queue) \; \ret \; b : \bool \\ &\quad b := (q.size = N) \\ &\bfend \; \fun \\ &\\ &\proc \; destroy(\inout \; q : Queue) \\ &\quad \while \; (\neg is\_empty\_queue(q)) \; \do \\ &\quad\quad dequeue(q) \\ &\quad \od \\ &\bfend \; \proc \\ \end{aligned}

Ejemplo de buffer de datos:

\begin{aligned} &\proc \; buffer() \\ &\quad \var \; d: data \\ &\quad \var \; q: Queue \; \of \; data \\ &\quad empty\_queue(q) \\ &\quad \do \; (\neg finish()) \\ &\quad\quad \if \; there\_is\_product() \; \then \\ &\quad\quad\quad d:= get\_product() \\ &\quad\quad\quad enqueue(q,d) \\ &\quad\quad\ \else \; \if \; there\_is\_demand() \land \neg is\_empty(q) \; \then \\ &\quad\quad\quad d:= first(q) \\ &\quad\quad\quad consume(d) \\ &\quad\quad \fi \\ &\quad \od \\ &\bfend \; \proc \end{aligned}

Sus funciones auxiliares:

$finish()$ devuelve $True$ si el servicio productor-consumidor ha finalizado.
$there\_is\_product(), \; there\_is\_demand()$ comprueban si hay producción o demanda respectivamente.
$get\_product()$ obtiene un producto desde el productor, y $consume(d)$ le envía al consumidor el producto $d$ .

Conjunto finito de elementos

Como su nombre lo indica, es un conjunto de elementos de un mismo tipo con una cantidad dinámica pero no infinita.

Como constructores tenemos:

El conjunto vacío.
Agregar un elemento a un conjunto.

Como operaciones tenemos:

Chequear si un elemento pertenece al conjunto.
Chequear si el conjunto es vacío.
Unir un conjunto a otro.
Intersecar un conjunto con otro.
Obtener la diferencia entre dos conjuntos.

Especificación de conjunto finito de elementos

\begin{aligned} &\spec \; Set \; \of \; T \; \where \\ &\\ &\cons \\ &\quad \fun \; empty\_set() \; \ret \; s : Set \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea un conjunto vacío} \;\; -\} \\ &\\ &\quad \proc \; add(\inout \; s : Set \; \of \; T, \; \bfin \; e : T) \\ &\quad\{- \;\; \textnormal{Agrega el elemento} \; e \; \textnormal{al conjunto} \; s \;\; -\} \\ &\\ &\destroy \\ &\quad \proc \; destroy(\inout \; s : Set \; \of \; T) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_empty(s : Set \; \of \; T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; s \;\textnormal{es vacío} \;\; -\} \\ &\\ &\quad \fun \; member(s : Set \; \of \; T, \; e : T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; e \;\textnormal{pertenece al conjunto} \; s \;\; -\} \\ &\\ &\quad \proc \; union(\inout \; s1 : Set \; \of \; T, \; \bfin \; s2 : Set \; \of \; T) \\ &\quad\{- \;\; \textnormal{Agrega a} \; s1 \; \textnormal{los elementos de} \; s2 \;\; -\} \\ &\\ &\quad \proc \; intersection(\inout \; s1 : Set \; \of \; T, \; \bfin \; s2 : Set \; \of \; T) \\ &\quad\{- \;\; \textnormal{Elimina de} \; s1 \; \textnormal{los elementos que NO pertenezcan a} \; s2 \;\; -\} \\ &\\ &\quad \proc \; diff(\inout \; s1 : Set \; \of \; T, \; \bfin \; s2 : Set \; \of \; T) \\ &\quad\{- \;\; \textnormal{Elimina de} \; s1 \; \textnormal{los elementos que pertenezcan a} \; s2 \;\; -\} \\ \end{aligned}

Árboles binarios

Consisten en nodos que almacenan un elemento y dos subestructuras, que pueden ser otro nodo o el vacío.\

Uno de sus constructores es el árbol vacío,
Su otro constructor es el nodo consistente de un elemento tipo $T$ y dos árboles.

En el nivel $i$ de un árbol hay a lo sumo $2^{i-1}$ nodos, (Por ejemplo, nivel $3 \implies 4$ nodos)

En un árbol “balanceado” la altura es del orden del $\log_2 k$ donde $k$ es el número de nodos.

Podemos recorrer un árbol indicando caminos desde la raíz y representarlos como secuencias donde los elementos indican si bajamos por izquierda o derecha.

Su especificación es:

\begin{aligned} &\type \; Direction = \enumerate \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad Left \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad Right \\ &\quad\quad\quad\quad\quad\quad\quad\quad \bfend \; \enumerate \\ &\\ &\type \; Path = List \; \of \; Direction \\ &\\ &\spec \; Tree \; \of \; \where \\ &\\ &\cons \\ &\quad \fun \; empty\_tree() \; \ret \; t : Tree \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea un árbol vacío} \;\; -\} \\ &\\ &\quad \fun \; node(tl: Tree \; \of \; T, \; e : T, \; tr: Tree \; \of \; T) \; \ret \; t : Tree \; \of \; T \\ &\quad\{- \;\; \textnormal{Crea el nodo con elemento} \; e \; \textnormal{y subárboles} \; tl, \; tr \;\; -\} \\ &\destroy \\ &\quad \proc \; destroy(\inout \; tr : Tree \; \of \; T) \\ &\quad\{- \;\; \textnormal{Libera memoria en caso que sea necesario} \;\; -\} \\ &\\ &\ops \\ &\quad \fun \; is\_empty\_tree(t : Tree \; \of \; T) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; t \;\textnormal{es vacío} \;\; -\} \\ &\\ &\quad \fun \; root(t : Tree \; \of \; T) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el elemento de la raíz de} \; t \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_tree(t) \;\; -\} \\ &\\ &\quad \fun \; left(t : Tree \; \of \; T) \; \ret \; tl : Tree \; \of \; T \\ &\quad\{- \;\; \textnormal{Devuelve el subárbol izquierdo de} \; t \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_tree(t) \;\; -\} \\ &\\ &\quad \fun \; right(t : Tree \; \of \; T) \; \ret \; tr : Tree \; \of \; T \\ &\quad\{- \;\; \textnormal{Devuelve el subárbol derecho de} \; t \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; \textnormal{not} \; is\_empty\_tree(t) \;\; -\} \\ &\\ &\quad \fun \; height(t : Tree \; \of \; T) \; \ret \; n : \nat \\ &\quad\{- \;\; \textnormal{Devuelve la distancia entre la raíz de} \; t \; \textnormal{y la hoja más profunda} \;\; -\} \\ &\\ &\quad \fun \; is\_path(t : Tree \; \of \; T, \; p : Path) \; \ret \; b : \bool \\ &\quad\{- \;\; \textnormal{Devuelve} \; True \;\textnormal{si} \; p \;\textnormal{es un camino válido en} \; t \;\; -\} \\ &\\ &\quad \fun \; subtree\_at(t : Tree \; \of \; T, \; p : Path) \; \ret \; t0 : Tree \; \of \; T \\ &\quad\{- \;\; \textnormal{Devuelve el subárbol de} \; t \; \textnormal{al seguir el camino} \; p \; \textnormal{en} \; t \;\; -\} \\ &\\ &\quad \fun \; elem\_at(t : Tree \; \of \; T, \; p : Path) \; \ret \; e : T \\ &\quad\{- \;\; \textnormal{Devuelve el elemento al seguir el camino} \; p \; \textnormal{en} \; t \;\; -\} \\ &\quad\{- \;\; \mathbf{PRE:} \; is\_path(t,p) \;\; -\} \\ \end{aligned}

Implementación de árboles binarios

Su implementación es similar a la de listas enlazadas. Se define un tipo $Node$ como tupla con un elemento y dos punteros a sí mismo:

\begin{aligned} &\impt \; Tree \; \of \; T \; \where \\ &\\ &\type \; Node \; \of \; T = \tuple \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad left: \pointer \; \too \; (Node \; \of \; T) \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad value: T \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad right: \pointer \; \too \; (Node \; \of \; T) \\ &\quad\quad\quad\quad\quad\quad\quad\quad \; \; \bfend \; \tuple \\ &\\ &\type \; Tree \; \of \; T = \pointer \; \too \; (Node \; \of \; T) \\ &\\ &\fun \; empty\_tree() \; \ret \; t : Tree \; \of \; T \\ &\quad t := \null \\ &\bfend \; \fun \\ &\\ &\fun \; node(tl: Tree \; \of \; T, \; e : T, \; tr: Tree \; \of \; T) \; \ret \; t : Tree \; \of \; T \\ &\quad alloc(t) \\ &\quad t \to left := tl \\ &\quad t \to value := e \\ &\quad t \to right := tr \\ &\bfend \; \fun \end{aligned}

Árboles binarios de búsqueda

Un arbol binario de búsqueda o ABB es aquel árbol $t$ donde:

1) Los valores alojados en el subárbol izquierdo de $t$ deben ser menores que el alojado en la raíz de $t$ .
2) Los valores alojados en el subárbol derecho de $t$ deben ser mayores que el alojado en la raíz de $t$ .
3) Las condiciones anteriores deben cumplirse para todos los subárboles de $t$

Si el algoritmo está “balanceado”, es un algoritmo logarítmico.

Si queremos agregar un elemento $e$ se sigue este procedimiento:

1) Si $t$ es vacío, se forma el nodo que consta del elemento $e$ y los dos subárboles vacíos.
2) En caso contrario, se compara el elemento $e$ con la raíz del árbol $t$ .

Si $e$ es menor que la raíz, se agrega al subárbol izquierdo.
Si $e$ es mayor o igual a la raíz, se agrega al subárbol derecho.