Árboles binarios en Erlang

En primer lugar, es importante definir qué es un árbol. En nuestro caso, son nodos hasta abajo. Los nodos son tuplas que contienen una clave, un valor asociado a la clave y luego otros dos nodos. De estos dos nodos, necesitamos uno que tenga una clave más pequeña y otro que tenga una clave más grande que el nodo que los contiene. ¡Así que aquí está la recursividad! Un árbol es un nodo que contiene nodos, cada uno de los cuales contiene nodos, que a su vez también contienen nodos. Esto no puede continuar para siempre (no tenemos infinitos datos para almacenar), por lo que diremos que nuestros nodos también pueden contener nodos vacíos.

Para representar nodos, las tuplas son una estructura de datos apropiada. Para nuestra implementación, podemos definir estas tuplas como {node, {Key, Value, Smaller, Larger}} , donde Smaller y Larger pueden ser otro nodo similar o un nodo vacío ({nodo, nil} ). 

Comencemos a construir un módulo para nuestra implementación de árbol muy básica. La primera función, vacía/0, devuelve un nodo vacío. El nodo vacío es el punto de partida de un nuevo árbol, también llamado raíz:

-module(tree).

-export([empty/0, insert/3, lookup/2]).

 

empty() -> {node, 'nil'}.

Al usar esa función y luego encapsular todas las representaciones de nodos de la misma manera, ocultamos la implementación del árbol para que la gente no necesite saber cómo está construido. Toda esa información puede estar contenida únicamente en el módulo. Si alguna vez decide cambiar la representación de un nodo, puede hacerlo sin romper el código externo.

Para agregar contenido a un árbol, primero debemos entender cómo navegar recursivamente a través de él. Procedamos de la misma manera que lo hicimos con todos los demás ejemplos de recursividad, intentando encontrar el caso base. Dado que un árbol vacío es un nodo vacío, nuestro caso base es lógicamente un nodo vacío. Entonces, cada vez que lleguemos a un nodo vacío, ahí es donde podemos agregar nuestra nueva clave/valor. El resto del tiempo, nuestro código tiene que recorrer el árbol intentando encontrar un nodo vacío donde poner contenido.

Para encontrar un nodo vacío comenzando desde la raíz, debemos aprovechar el hecho de que la presencia de nodos más pequeños y más grandes nos permite navegar comparando la nueva clave que tenemos que insertar con la clave del nodo actual. Si la nueva clave es más pequeña que la clave del nodo actual, intentamos encontrar el nodo vacío dentro de Smaller, y si es más grande, dentro de Larger. Sin embargo, hay un último caso: ¿qué pasa si la nueva clave es igual a la clave del nodo actual? Allí tenemos dos opciones: dejar que el programa falle o reemplazar el valor por el nuevo. Esta es la opción que tomaremos aquí. Poner en una función toda esta lógica funciona de la siguiente manera:

insert(Key, Val, {node, 'nil'}) ->

    {node, {Key, Val, {node, 'nil'}, {node, 'nil'}}};

insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->

    {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};

insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->

    {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}};

insert(Key, Val, {node, {Key, _, Smaller, Larger}}) ->

    {node, {Key, Val, Smaller, Larger}}.

Tenga en cuenta aquí que la función devuelve un árbol completamente nuevo. Esto es típico de los lenguajes funcionales que tienen una sola asignación. Si bien esto puede considerarse ineficiente, la mayoría de las estructuras subyacentes de dos versiones de un árbol a veces resultan ser las mismas y, por lo tanto, la VM las comparte y las copia solo cuando es necesario.

Lo que queda por hacer en esta implementación de árbol de ejemplo es crear una función de búsqueda/2 que le permitirá encontrar un valor de un árbol proporcionando su clave. La lógica necesaria es extremadamente similar a la que se usa para agregar contenido nuevo al árbol: recorremos los nodos y verificamos si la clave de búsqueda es igual, menor o mayor que la clave del nodo actual. Tenemos dos casos base: uno cuando el nodo está vacío (la clave no está en el árbol) y otro cuando se encuentra la clave. Como no queremos que nuestro programa falle cada vez que buscamos una clave que no existe, devolveremos el átomo "indefinido". De lo contrario, devolveremos {ok, Valor}. La razón de esto es que si solo devolviéramos Valor y el nodo contuviera el átomo 'indefinido', no tendríamos forma de saber si el árbol devolvió el valor correcto o no pudo encontrarlo. Al agrupar los casos exitosos en una tupla de este tipo, facilitamos la comprensión de cuál es cuál. Aquí está la función implementada:

lookup(_, {node, 'nil'}) ->

undefined;

lookup(Key, {node, {Key, Val, _, _}}) ->

{ok, Val};

lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->

lookup(Key, Smaller);

lookup(Key, {node, {_, _, _, Larger}}) ->

lookup(Key, Larger).

Y hemos terminado. Probémoslo haciendo una pequeña libreta de direcciones de correo electrónico. Compile el archivo e inicie el shell:

1> T1 = tree:insert("Jim Woodland", "jim.woodland@gmail.com", tree:empty()).

{node,{"Jim Woodland","jim.woodland@gmail.com",

{node,nil},

{node,nil}}}

2> T2 = tree:insert("Mark Anderson", "i.am.a@hotmail.com", T1).

{node,{"Jim Woodland","jim.woodland@gmail.com",

{node,nil},

{node,{"Mark Anderson","i.am.a@hotmail.com",

{node,nil},

{node,nil}}}}}

3> Addresses = tree:insert("Anita Bath", "abath@someuni.edu", tree:insert("Kevin Robert", "myfairy@yahoo.com", tree:insert("Wilson Longbrow", "longwil@gmail.com", T2))).

{node,{"Jim Woodland","jim.woodland@gmail.com",

{node,{"Anita Bath","abath@someuni.edu",

{node,nil},

{node,nil}}},

{node,{"Mark Anderson","i.am.a@hotmail.com",

{node,{"Kevin Robert","myfairy@yahoo.com",

{node,nil},

{node,nil}}},

{node,{"Wilson Longbrow","longwil@gmail.com",

{node,nil},

{node,nil}}}}}}}

Y ahora puedes buscar direcciones de correo electrónico con él:

4> tree:lookup("Anita Bath", Addresses).

{ok, "abath@someuni.edu"}

5> tree:lookup("Jacques Requin", Addresses).

undefined

¡Esto concluye nuestro ejemplo de libreta de direcciones funcional construida a partir de una estructura de datos recursiva distinta de una lista!