C++ / tree

Bienvenidos sean a este post, que es el concepto de tree.

En el post anterior vimos como podemos garantizarnos para la busqueda binaria que el contenedor a procesar tenga los elementos ordenados gracias al algoritmo sort. Pero existe un contenedor que de manera predeterminada realiza esta accion y es set, del cual hablamos en este post. porque tiene como estructura un arbol balanceado y como mencionamos en su momento, siempre ordenara los valores internamente a medida que los recibe. Si recuerdan cuando hablamos de como realiza la busqueda el buscador binario en este post, este siempre pone los valores menores al nodo que evaluamos a su izquierda y los mayores a la derecha. Y el nodo siempre sera el valor del medio del rango informado. Esto se repetira hasta tener una coincidencia o no. Con esto comentado, podemos representar a los nodos del arbol binario como un struct que posee al elemento y dos punteros que apuntan a los nodos hijos. Veamos el siguiente ejemplo:

template <typename T>
struct nodo_tree
{
  T elemento;
  nodo_tree<T>* izquierda;
  nodo_tree<T>* derecha;
};

Es lo que comentamos anteriormente, tenemos una variable para recibir al elemento que estara asociado al nodo y dos punteros para el valor menor (izquierda) y mayor (derecha). Si bien, STL no provee un contenedor separado para los tree si tiene uno basado en la implementacion de tree. Como mencionamos anteriormente ,este contenedor es set. Y no solo tiene un tree balanceado sino que esta todo el tiempo ordenando los elementos a medida que los recibe. Veamos un ejemplo simple para repasar a set:

#include <iostream>
#include <set>

int main(int argc, char **argv)
{
        std::set<int> c{10,2,7,3,5,1,8,9,4,6};
        for(int v : c)
                std::cout << v << " ";
        std::cout << std::endl;

        return 0;
}

Este es un ejemplo muy simple, donde primero definimos una variable de tipo set y este almacenara una serie de valores pero observen como los ingresamos. Lo siguiente es mostrar los valores en el set, y el ultimo endl es simplemente para dar un efecto de Enter cuando finalice el bucle. Compilemos y veamos como es la salida:

$ ./tree
1 2 3 4 5 6 7 8 9 10
$

Se realizo lo comentado anteriormente, donde sin importar como ingresemos los valores estos seran ordenados automaticamente. El concepto de tree balanceado tambien se aplica a map pero este trabaja de una manera distinta porque utiliza una clave para elemento y a este le asociamos el valor. Analicemos el siguiente ejemplo:

#include <iostream>
#include <map>
#include <string>

int main(int argc, char **argv)
{
        std::map<int, std::string> m;
        m[0] = "Hola";
        m[1] = "Mundo";
        m[2] = "Como";
        m[3] = "Estas?";

        for(int i = 0; i < m.size(); i++)
                std::cout << m[i] << std::endl;

        return 0;
}

En este implementamos un map donde las claves seran de tipo entero y tendremos valores de tipo string asociados. Para recuperarlos, al ser tipo numericos podemos usar un bucle normal que cuente en base al tamaño del mismo, gracias a size, y mostrarlo como si fuera un array comun y corriente. Compilemos y veamos como es la salida:

$ ./tree
Hola
Mundo
Como
Estas?
$

Observen que nos devolvio los valores, inclusive podrian ordenarlos con sort. Tambien podemos usarlo de manera inversa usando claves de tipo string y asociarlos a valores numericos. Si bien no se ordenara automaticamente como set, si podemos hacerlo externamente o como en este ejemplo simplemente respetando el orden de ingreso de los valores.

Estos dos tipos son muy utiles y muy eficientes para la mayoria de los casos donde podemos utilizarlo pero existe uno mas eficiente pero eso sera tema para el proximo post. Antes de finalizar les dejo los posts donde hablamos mas profundamente sobre set y map:

En resumen, hoy hemos visto a tree, que es, para que se utiliza, si bien no es manipulado por STL, si es utilizado por algunos contenedores, hablamos sobre la estructura y como es tanto para set como para map. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.