Implementación de la suma de un árbol binario en golang

Golang, o simplemente Go, es uno de los lenguajes más populares actualmente. Según sus desarrolladores, pretende ser tan dinámico como Python pero con el rendimiento de C. Y según encuestas, ha sido el lenguaje más demandado en el año 2020.

Algunas de las características más importantes que podemos citar son.

• Es un lenguaje compilado y es posible obtener ejecutables para varias plataformas. Incluso desde Linux se puede obtener un ejecutable para Windows.
• Es un lenguaje tipado, lo que significa que podemos, al declarar un variable, definir el tipo de dato de esta. Aunque también combina el tipado dinámico. El compilador puede deducir el tipo de una variable según el valor asignado, y luego no es posible asignarle un valor de otro tipo.
• No es un lenguaje orientado a objeto, aunque usando las struct, se puede simular objetos con funciones, pero adolece de conceptos como la herencia por ejemplo.
• Y para mi la característica más importante, es un lenguaje concurrente de forma nativa. Lo que significa que se puede implementar algoritmos que ejecuten varios procesamientos de forma simultánea.

En este artículo lo que pretendo es mostrar como podemos implementar un programa concurrente usando Go. Para esto usaremos un árbol binario de enteros. E implementaremos un método Sum, que devolverá la suma total de todos los nodos.

Primero haremos el algoritmo de forma recursiva y luego haremos el mismo algoritmo pero usando una lógica concurrente.

Crearemos una struct, donde almacenaremos los datos de un árbol. Un árbol binario es una estructura de datos recursiva. Tendría el valor de la raíz, una referencia al árbol izquierdo y una referencia al árbol derecho. Lo árboles hijos pueden ser null.

No me pienso detener mucho en las interioridades del lenguaje, pero básicamente a esto se le podría llamar una clase en Go. Recordar que Go no es un lenguaje que abrase el paradigma POO. Explicaré ahora los elementos más importante de este código.

1. En la línea 1 definimos el nombre del paquete. Donde un paquete puede estar formado por varios ficheros.
2. En la línea 3 definimos la estructura que almacenará los datos del árbol. Si se fijan bien el nombre de la estructura, esta empieza con letra minúscula. Esta es la forma que tiene Go, para indicar que esta estructura no será accesible desde fuera del paquete, es decir, será privada. Esto también se aplica a las funciones. Si una función comienza con letra minúscula será privada al paquete.
3. Línea 9. Una vez más decir que Go no es un lenguaje orientado a objetos, por lo tanto no tenemos una estructura de código que sirva para construir objetos. La función NewTree hace la función de constructor de nuestra clase. nodeTree es privado para el paquete, por lo tanto la única forma de crear un árbol es usando esta función, su constructor. La función devuelve la referencia al árbol (símbolo & delante de la variable n). Esto nos permitirá modificarlo en el futuro.
4. En las líneas 14 y 19 tenemos los métodos que nos permiten asignar un hijo derecho o izquierdo a un árbol. Si se fijan, existe una diferencia entre la forma en que se declaró el método NewTree y el método SetLeft. Este último tiene delante lo siguiente (tree *nodeTree). Esta es la forma que tiene Go de adicionarles nuevos métodos a cualquier tipo de dato.

En la función main podremos un código que nos permita crear un árbol como el que está en la imagen y de paso veremos como sería el proceso de crear un objeto y acceder a sus métodos.

Lo siguiente que vamos a hacer implementar el algoritmo de Sum. Primero lo haremos de forma recursiva y luego lo haremos utilizando un algoritmo recurrente. Aclarar que el algoritmo recurrente no es que sustituya al recursivo sino que hace las llamadas recursivas de forma asíncrona.

Este algoritmo no lleva mucha explicación. Básicamente si el árbol es null se retorna 0 y sino, se suma el valor del árbol, más la suma del hijo izquierdo y la suma del hijo derecho.

Si se fijan en el algoritmo anterior, la computadora necesita procesar todo el árbol izquierdo y después es que empieza a sumar el árbol derecho. Es aquí donde el poder de Go entra en acción, porque este lenguaje tiene soporte nativo para algoritmos concurrentes. El objetivo ahora es crear un algoritmo que permita sumar todos los valores del hijo izquierdo y derecho de forma simultánea.

Para hacer este algoritmo necesitamos dos métodos, Sum (con mayúsculas) que será el visible fuera del paquete y sum (con minúscula) que es el que va a hacer el procesamiento real. Necesitamos dos métodos porque tenemos que inicializar un channel y los usuarios de nuestro paquete no tienen por qué lidiar con esto.

Aquí tenemos tres cosas importantes, el channel (chan), la palabra reservada go y el operados <-.

• Los channels (chan) es un tipo de dato que nos permite enviar y recibir mensajes entre procesos que corren de forma concurrentes.
• La palabra reservada go, nos permite ejecutar cualquier función de forma asíncrona.
• El operador <- nos permite pasar datos desde y hacia un channel.

Explicación del algoritmo Sum.

1. En la línea 2 creamos un channel por el que vamos a recibir la suma total del árbol.
2. En la línea 3 ejecutamos la función sum de forma concurrente. Usando la palabra reservada go.
3. En la línea 4 esperemos la suma que viene por el canal y retornamos el dato.

Ahora explicaremos el método sum que es realmente el más interesante.

1. Desde la línea 8 a la 10 es el caso base de nuestro algoritmo recursivo. Básicamente estamos diciendo que si el árbol es null enviamos 0 al canal y terminamos el algoritmo.
2. En la línea 12 creamos un canal donde esperamos que nos envíen dos valores, la suma del hijo izquierdo y la suma del hijo derecho.
3. En las líneas 13 y 14 está la parte más importante del algoritmo, donde está la magia. Mandamos a sumar el hijo izquierdo y el hijo derecho de forma concurrente y a los dos le pasamos el canal que creamos en la línea 12. Ambos métodos van a poner en el canal el resultado de la suma.
4. Finalmente en la línea 15, sumamos el valor del árbol, más los dos valores que tenemos en el canal, que es la suma de la izquierda y la suma de la derecha.

Conclusión

En el artículo se tomo como pretexto un árbol para demostrar la caracterísitica estrella de Go, la implementación de algoritmos concurrentes. Desde mi punto de vista el lenguaje es muy fácil de aprender y se debería tener encuenta en aquellos problemas donde se necesita realizar operaciones de forma simultáneas.

En la url https://go.dev puedes ver el sitio oficila del lenguaje y comenzar a aprender este increible tecnología.