Los Tries son estructuras de datos de tipo árbol, estos cuentan con nodos y almacenan información que se relaciona entre si, por ejemplo podemos almacenar una palabra, cada nodo almacena un carácter y posteriormente podemos buscar carácter por carácter si la palabra existe, si tenemos palabras con letras iguales (mercado, mercenario) los nodos no se repiten, siendo una estructura eficiente.

Estructura basica

Empezaremos creando el objeto Trie con el nodo principal:

function Trie() {

  var node = {

    data: "*",

    isWord: false,

    children: [],

    charactersUsed: 0

  }

  this._root = node;

}

es necesario crear un nodo principal ( que generalmente guarda el carácter *) ya que este es el que tendrá los nodos hijos donde empezaremos a insertar información o buscarla, los atributos del nodo son:

• data: La información que guarda el nodo

• isWord: para saber si es una palabra el conjunto de caracteres que estamos buscando

• children: array de los nodos hijos

• characteresUsed: numero de nodos que van encadenados

GetChild

El primero método es necesario para buscar un valor en el array de los nodos hijos (children)

Trie.prototype = {

  constructor: Trie,



  getChild: function(char, node) {

    for (index in node.children) {

      if (node.children[index].data === char) {

        return node.children[index];

      }

    }

    return null

  }

}

este método recibe el valor a buscar (char) y el nodo que tiene los hijos, con un for recorremos el array children hasta encontrar el valor, si este no existe regresamos null.

Find

Este método nos permite buscar una palabra o una serie de caracteres dentro de la estructura, es necesario que todos los caracteres estén presentes para que la búsqueda regrese true:

  find: function(word) {

    var current = this._root;

    for (char in word) {

      var nextNode = this.getChild(word[char], current);

      if (nextNode === null) {

        return null;

      }

      current = nextNode;

    }

    return current;

  }

el método recibe una palabra y por cada carácter de la palabra buscamos el nodo que contenga el mismo valor si no tenemos todos los caracteres de la palabra almacenados regresamos null.

Add

Este método almacena una serie de caracteres o una palabra dentro de la estructura:

  add: function(word) {

    var current = this._root;

    for (char in word) {

      var nextNode = this.getChild(word[char], current);



      if (nextNode === null) {

        nextNode = {

          data: word[char],

          isWord: false,

          children: [],

          charactersUsed: 0

        }

        current.children.push(nextNode);

      }

      current.charactersUsed += 1;

      current = nextNode;

    }

    current.isWord = true;

  }

Recibe una palabra y almacena cada carácter, si el carácter ya esta dentro de la estructura omite el paso de crear un nuevo nodo, se agrega current.charactersUsed += 1 para saber cuantas palabras o cadena de caracteres comparten el nodo.

Creando un nuevo Trie

Para crear una nueva estructura:

var trie = new Trie();

agregamos una nueva palabra:

trie.add("mario");

buscamos si la cadena existe:

console.log(trie.find("mario"));

o podemos buscar cadenas que no existan y nos regresara null:

console.log(trie.find("oi"));

esta estructura puede ser util para crear usuarios únicos, juegos de adivinar palabras o simplemente para almacenar datos que tengan valores en común.