Árboles (trees)
Continuamos con estructuras de datos, y en esta ocasión nos toca hablar de árboles, que son un tipo especial de “grafo”. Así que si todavía no has leído el artículo de Eli sobre ese tema, te recomiendo empezar por ahí:
Qué es un árbol?
Los árboles (trees) son una estructura de datos muy común, que se define de forma recursiva como una colección de nodos, empezando por un nodo raíz, donde cada nodo es una estructura de datos que contiene un valor, y opcionalmente una lista de referencias a otros nodos (sus hijos), con la limitación de que ninguna referencia esté duplicada, y que ninguna apunte al nodo raíz.
A Tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root node. From Wikipedia
Qué quiere decir todo esto, bueno, básicamente que un árbol es una estructura no lineal, que tiene un principio — el nodo raíz — y este nodo va a contener referencias a otros nodos — sus hijos — los cuales van a ser el mismo tipo de estructura (un nodo), y por lo tanto podrán contener o no su propia lista de referencias a otros nodos.
De hecho, podemos pensar en nodos que contienen nodos, o alternativamente directamente en árboles que contienen “sub-árboles”. Es común usar ambas palabras (nodo y árbol) para referirnos al mismo tipo de objeto, pero visto desde dos puntos de vista.
Como desarrolladores web, la forma más fácil de visualizar esta estructura de datos es imaginándonos el árbol del DOM (Document Object Model). En esta estructura, partimos de un nodo raíz (<html>), y cada nodo hijo (elemento del DOM) tiene un padre, y puede o no contener uno o más hijos. Para quien conozca HTML resulta obvio que un nodo sólo puede tener un padre, ya que no puede ser hijo directo de más de un nodo!
Diferencias entre árboles y grafos
Conceptualmente, podríamos decir que los árboles se enfocan en representar “jerarquías”, mientras que los grafos son una estructura más genérica usada para representar “redes”.
Hemos dicho que los árboles son un tipo de grafo, de hecho son grafos acíclicos dirigidos y mínimamente conectados. Veamos las diferencias entre ambas estructuras en más detalle:
Rutas
Los árboles son un tipo especial de grafo, que tiene sólo una posible ruta entre dos vértices. En un grafo pueden haber más de una ruta entre dos vertices.
Ciclos
Los árboles no permiten ciclos, mientras que los grafos pueden contener ciclos así como nodos que hacen referencia a sí mismos.
Nodo raíz
En un árbol siempre hay un nodo raíz, y sólo uno. En un grafo no existe el concepto de nodo raíz.
Relación padre-hijo
Los árboles se caracterizan por las relaciones padre/hijo. Cada hijo debe tener un padre y sólo un padre. En grafos no existe este tipo de relación.
Número de aristas
Los árboles siempre van a tener un número de aristas igual a n — 1, porque todos los elementos van a tener un padre, menos el nodo raíz. En los grafos el número de aristas es independiente del número de vértices y depende de la complejidad de cada grafo en particular.
Terminología
Para poder hablar de árboles con más soltura, primero necesitamos definir una serie de términos que van aparecer una y otra vez.
Nodo
El “nodo” es la estructura básica que usamos para construir un “árbol”. Todos los elementos de un árbol son nodos. A su vez, cada nodo es un sub-árbol. Los nodos se caracterizan por tener un valor, y referencias a otros nodos.
Padres / Hijos
Los “hijos” de un nodo son los nodos a los cuáles éste hace referencia. Por ejemplo, en un documento HTML las etiquetas (nodos) <head> y <body> son hijos de el nodo <html>. Al mismo tiempo, diríamos que <html> es el nodo “padre” de tanto <head> como <body>.
Nodo raíz
Todo árbol tiene un nodo inicial o nodo raíz, el cual va a ser el único nodo que no tenga un “padre”.
Nodo hoja
Los nodos hoja son aquellos que no tienen hijos (las hojas del árbol).
Nivel
En un árbol, cuando hablamos de “nivel” nos referimos a la distancia, o el número de saltos que debemos dar hasta llegar al nodo raíz. Podemos verlo también como el “nivel de anidación”.
Altura o profundidad
La altura o profundidad de un árbol hace referencia al nivel máximo que vamos a encontrar.
Orden o grado
El orden o grado de un árbol determina cuántos hijos puede tener un nodo. Por ejemplo, un árbol de orden 2 sería un árbol binario, donde cada nodo puede tener como máximo dos hijos. Un árbol de orden 3 o ternario permitiría que cada nodo tenga un máximo de tres hijos. Un árbol no está obligado a determinar un orden o grado.
Árbol completo
Un árbol completo es aquel en el que todos los nodos tienen o ningún hijo o el número máximo de hijos.
Árbol degenerado
Cuando un árbol contiene 1 sólo hijo por nodo. Los árboles degenerados tienen la profundidad máxima posible dado un número de elementos. Este tipo de árboles se comportan como listas.
Árbol balanceado
Lo opuesto a un árbol degenerado sería un árbol balanceado, donde el árbol tiene la profundidad mínima posible dado un número de elementos.
Implementación
Ahora que ya hemos cubierto los conceptos principales que definen un árbol como estructura de datos, pasemos a implementar nuestro propio árbol en JavaScript.
Constructores
En nuestro ejemplo, vamos a usar dos constructores, Node (nodo) y Tree (árbol) para diferenciar la funcionalidad y propiedades de cada nodo por separado y el árbol en conjunto.
function Node() {
this.value = val; // valor del nodo
this.children = []; // lista de referencias a los nodos hijos
}function Tree() {
this.root = null; // referencia al nodo raíz
}
Búsqueda
Una vez que hemos definido los constructores Node y Tree, vamos a empezar a implementar los métodos de Tree para que se comporte como un árbol. Antes que nada, me gustaría empezar por el método findBFS(), que nos permite hacer una búsqueda por anchura en nuestro árbol. La razón por la que he querido empezar por este método, es que lo vamos a necesitar para implementar nuestro método add(), que va a ser el próximo paso.
Tree.prototype.findBFS = function (value) { var queue = [this.root]; while (queue.length) {
var node = queue.shift(); if (node.value === value) {
return node;
} for (var i = 0; i < node.children.length; i++) {
queue.push(node.children[i]);
}
} return null;
};
Como vemos, al buscar por anchura (Breadth First Search — BFS) vamos a ir añadiendo los hijos a una cola, con lo cual no van a ser visitados hasta haber visitado primero a todos los hermanos de la generación anterior.
Inserción
Listo, ya podemos buscar en nuestro árbol, pero no tiene mucho sentido hasta que implementemos alguna manera de añadir valores. Para poder insertar un nuevo valor, vamos a necesitar dos cosas: el valor en sí, y el lugar o posición donde queremos que aparezca en la jerarquía, para lo cual vamos a recibir el valor del nodo padre al que le queremos añadir un hijo.
Tree.prototype.add = function (value, toNodeValue) { var node = new Node(value);
var parent = toNodeValue ? this.findBFS(toNodeValue) : null; if (parent) {
parent.children.push(node);
}
else if (!this.root) {
this.root = node;
}
else {
throw new Error('Root node is already assigned');
}
};
Nuestro método add() hace lo siguiente:
- Crea un nuevo objeto de tipo
Node - Si nos han pasado el valor del nodo “padre” buscamos el nodo.
- a) Si hemos encontrado un nodo padre le añadimos el nuevo hijo.
b) Si no hemos encontrado un padre y todavía no hemos especificado un nodo raíz, asignamos el nuevo nodo como raíz.
c) Si no hay padre y ya tenemos un nodo raíz mostramos un error ya que no tenemos dónde añadir el nuevo nodo.
Borrado
Para borrar elementos vamos a tener que recorrer todo el árbol, y cuando encontremos un nodo que contenga el valor que queremos borrar, modificamos la lista children su padre usando Array.prototype.splice().
Tree.prototype.remove = function (value) { // caso especial: si el valor está en el
// nodo raíz reseteamos el árbol
if (this.root.value === value) {
this.root = null;
} var queue = [this.root]; while (queue.length) {
var node = queue.shift(); for (var i = 0; i < node.children.length; i++) {
if (node.children[i].value === value) {
node.children.splice(i, 1);
}
else {
queue.push(node.children[i]);
}
}
}
};
Recorrido
Al igual que con los grafos en general, podemos recorrer lo árboles por “anchura” o “profundidad”. Cuando recorremos por anchura, primero visitamos los “hermanos” antes de entrar en los “hijos”, cubriendo el ancho completo del árbol por cada nivel antes de pasar al siguiente nivel; mientras que la búsqueda por profundidad visita de forma vertical los hijos hasta llegar a las hojas de árbol.
Recorrido por anchura (Breadth First Search — BFS)
El recorrido por anchura lo podemos implementar muy parecido a nuestro método findBFS(), que de hecho hace una búsqueda por anchura. En este caso en vez de buscar un nodo dado un valor, lo que queremos es recorrer el árbol e invocar una función cada vez que encontramos un nodo, pasando una referencia al nodo. De esta manera podemos recorrer el árbol y hacer algo para cada nodo.
Tree.prototype.traverseBFS = function (fn) { var queue = [this.root]; while (queue.length) {
var node = queue.shift(); fn && fn(node); for (var i = 0; i < node.children.length; i++) {
queue.push(node.children[i]);
}
}
};
Recorrido por profundidad (Depth First Search — DFS)
Como alternativa al recorrido por anchura, podemos también recorrer nuestro árbol por profundidad. En este caso, en vez de visitar primero lo hermanos, nos enfocamos en visitar los hijos, aumentando de profundidad en cada paso hasta llegar a un nodo hoja. Como resultado, antes de pasar a un nodo hermano, primero vamos a recorrer sus hijos, y los hijos de sus hijos, etc.
Al hacer un recorrido por profundidad, podemos invocar el callback (y así considerar el nodo como visitado) antes o después de recorrer los hijos. Ambas versiones son útiles, así que vamos a implementar las dos. Para ello vamos a declarar un método traverseDFS() que reciba dos argumentos: el callback a invocar para cada elemento, y el tipo de recorrido (preOrder o postOrder).
Tree.prototype.traverseDFS = function (fn, method) { var current = this.root; if (method) {
this['_' + method](current, fn);
}
else {
this._preOrder(current, fn);
}
};
Pre-order:
Tree.prototype._preOrder = function (node, fn) { if (!node) {
return;
} fn && fn(node); for (var i = 0; i < node.children.length; i++) {
this._preOrder(node.children[i], fn);
}
};
Post-order:
Tree.prototype._postOrder = function (node, fn) { if (!node) {
return;
} for (var i = 0; i < node.children.length; i++) {
this._postOrder(node.children[i], fn);
} fn && fn(node);
};
Resumen
- Un árbol es un conjunto de nodos, donde cada nodo puede apuntar a otros nodos (hijos), y puede ser apuntado por un solo nodo (sólo un padre).
- Los árboles son estructuras no lineales.
- Los árboles son estructuras recursivas.
- Los árboles se usan para representar orden, jerarquía.
- Todo árbol empieza por un nodo raíz: único nodo que no va a tener padre.
- Un árbol no puede tener ciclos.
- Los árboles se pueden recorrer por anchura o profundidad.
