Posted on

Adrián Mejía

, Author

Las estructuras de datos en forma de árbol tienen muchos usos, y es bueno tener una comprensión básica de su funcionamiento. Los árboles son la base de otras estructuras de datos muy utilizadas como Mapas y Conjuntos. También se utilizan en las bases de datos para realizar búsquedas rápidas. El HTML DOM utiliza una estructura de datos en forma de árbol para representar la jerarquía de los elementos. Este post explorará los diferentes tipos de árboles como los árboles binarios, los árboles de búsqueda binaria, y cómo implementarlos.

En el post anterior exploramos las estructuras de datos Graph, que son un caso generalizado de los árboles. ¡Empecemos a aprender qué son las estructuras de datos de árboles!

Este post forma parte de una serie de tutoriales:

Aprendiendo Estructuras de Datos y Algoritmos (DSA) para Principiantes

  1. Introducción a la complejidad temporal de los algoritmos y a la notación Big O

  2. Ocho complejidades temporales que todo programador debería conocer

  3. Estructuras de Datos para Principiantes: Arrays, HashMaps y Listas

  4. Estructuras de datos de grafos para principiantes

  5. Estructuras de datos de árboles para principiantes 👈 estás aquí

  6. Árboles de búsqueda binaria autoequilibrados

  7. Apéndice I: Análisis de algoritmos recursivos

Árboles: conceptos básicos

Un árbol es una estructura de datos donde un nodo puede tener cero o más hijos. Cada nodo contiene un valor. Al igual que los grafos, la conexión entre los nodos se llama aristas. Un árbol es un tipo de grafo, pero no todos los grafos son árboles (más adelante).

Estas estructuras de datos se llaman «árboles» porque la estructura de datos se parece a un árbol 🌳. Comienza con un nodo raíz y se ramifica con sus descendientes, y finalmente, hay hojas.

Aquí hay algunas propiedades de los árboles:

  • El nodo más alto se llama raíz.
  • Un nodo sin hijos se llama nodo hoja o nodo terminal.
  • La altura (h) del árbol es la distancia (número de aristas) entre la hoja más lejana y la raíz.
    • Atiene una altura de 3
    • Itiene una altura de 0
  • La profundidad o nivel de un nodo es la distancia entre la raíz y el nodo en cuestión.
    • H tiene una profundidad de 2
    • B tiene una profundidad de 1

Implementar una estructura de datos de árbol simple

Como vimos anteriormente, un nodo de árbol es sólo una estructura de datos con un valor y enlaces a sus descendientes.

Aquí tienes un ejemplo de nodo árbol:

1
2
3
4
5
6
 
class TreeNode {
constructor(value) {
this.value = value;
this.descendants = ;
}
}

Podemos crear un árbol con 3 descendientes de la siguiente manera:

1
2
3
4
5
6
7
8
9
10
 
// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');
// associate root with is descendants
abe.descendants.push(homer);
homer.descendants.push(bart, lisa, maggie);

¡Eso es todo; tenemos una estructura de datos en forma de árbol!

El nodo abe es la raíz y bart, lisa y maggie son los nodos hoja del árbol. Observa que el nodo del árbol puede tener diferentes descendientes: 0, 1, 3, o cualquier otro valor.

Las estructuras de datos en forma de árbol tienen muchas aplicaciones como:

  • Mapas
  • Conjuntos
  • Bases de datos
  • Colas de prioridad
  • Consultar un LDAP (Lightweight Directory Access Protocol)
  • Representar el Modelo de Objetos del Documento (DOM) para HTML en sitios web.

Árboles binarios

Los nodos de los árboles pueden tener cero o más hijos. Sin embargo, cuando un árbol tiene como máximo dos hijos, entonces se llama árbol binario.

Árboles binarios completos, completos y perfectos

Dependiendo de cómo estén dispuestos los nodos en un árbol binario, éste puede ser completo, completo y perfecto:

  • Árbol binario completo: cada nodo tiene exactamente 0 o 2 hijos (pero nunca 1).
  • Árbol binario completo: cuando todos los niveles, excepto el último, están llenos de nodos.
  • Árbol binario perfecto: cuando todos los niveles (incluido el último) están llenos de nodos.

Mira estos ejemplos:

Estas propiedades no son siempre mutuamente excluyentes. Se puede tener más de una:

  • Un árbol perfecto es siempre completo y lleno.
    • Los árboles binarios perfectos tienen precisamente `2^k – 1` nodos, donde k es el último nivel del árbol (empezando por el 1).
  • Un árbol completo no es siempre full.
    • Como en nuestro ejemplo «completo», ya que tiene un padre con un solo hijo. Si eliminamos el nodo gris de más a la derecha, entonces tendríamos un árbol completo y lleno pero no perfecto.
  • Un árbol completo no siempre es completo y perfecto.

Árbol de búsqueda binaria (BST)

Los árboles de búsqueda binaria o BST para abreviar son una aplicación particular de los árboles binarios. Los BST tienen como máximo dos nodos (como todos los árboles binarios). Sin embargo, los valores son para que el valor de los hijos de la izquierda debe ser menor que el padre, y los hijos de la derecha debe ser mayor.

Duplicados: Algunos BST no permiten duplicados mientras que otros añaden los mismos valores como hijo derecho. Otras implementaciones pueden mantener un recuento en un caso de duplicidad (vamos a hacer esto más adelante).

¡Implementemos un Árbol de Búsqueda Binaria!

Implementación de BST

BST son muy similares a nuestra implementación anterior de un árbol. Sin embargo, hay algunas diferencias:

  • Los nodos pueden tener, como máximo, sólo dos hijos: izquierda y derecha.
  • Los valores de los nodos tienen que ser ordenados como left < parent < right.

Aquí está el nodo del árbol. Muy similar a lo que hicimos antes, pero añadimos algunos getters y setters útiles para los hijos de la izquierda y la derecha. Fíjate que también se mantiene una referencia al padre, y la actualizamos cada vez que añadimos hijos.

TreeNode.jsCode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
const LEFT = 0;
const RIGHT = 1;
class TreeNode {
constructor(value) {
this.value = value;
this.descendants = ;
this.parent = null;
}
get left() {
return this.descendants;
}
set left(node) {
this.descendants = node;
if (node) {
node.parent = this;
}
}
get right() {
return this.descendants;
}
set right(node) {
this.descendants = node;
if (node) {
node.parent = this;
}
}
}

Ok, hasta aquí, podemos añadir un hijo izquierdo y otro derecho. Ahora, vamos a hacer la clase BST que hace cumplir la regla left < parent < right.

BinarySearchTree.js linkUrl linkText
1
2
3
4
5
6
7
8
9
10
11
12
13
 

class BinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
add(value) { /* ... */ }
find(value) { /* ... */ }
remove(value) { /* ... */ }
getMax() { /* ... */ }
getMin() { /* ... */ }
}

Vamos a implementar la inserción.

Inserción de nodos BST

Para insertar un nodo en un árbol binario, hacemos lo siguiente:

  1. Si un árbol está vacío, el primer nodo se convierte en la raíz, y ya está.
  2. Comparar el valor de la raíz/padre si es mayor ir a la derecha, si es menor ir a la izquierda. Si es el mismo, entonces el valor ya existe por lo que se puede aumentar el recuento de duplicados (multiplicidad).
  3. Repite #2 hasta que encontremos un hueco vacío para insertar el nuevo nodo.

Hagamos una ilustración de cómo insertar 30, 40, 10, 15, 12, 50:

Podemos implementar la inserción de la siguiente manera:

BinarySearchTree.prototype.addFull Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
add(value) {
const newNode = new TreeNode(value);
if (this.root) {
const { found, parent } = this.findNodeAndParent(value);
if (found) { // duplicated: value already exist on the tree
found.meta.multiplicity = (found.meta.multiplicity || 1) + 1;
} else if (value < parent.value) {
parent.left = newNode;
} else {
parent.right = newNode;
}
} else {
this.root = newNode;
}
this.size += 1;
return newNode;
}

Estamos utilizando una función de ayuda llamada findNodeAndParent. Si encontramos que el nodo ya existe en el árbol, entonces incrementamos el contador multiplicity. Veamos cómo se implementa esta función:

BinarySearchTree.prototype.findNodeAndParentFull Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
findNodeAndParent(value) {
let node = this.root;
let parent;
while (node) {
if (node.value === value) {
break;
}
parent = node;
node = ( value >= node.value) ? node.right : node.left;
}
return { found: node, parent };
}

findNodeAndParent recorre el árbol, buscando el valor. Comienza en la raíz (línea 2) y luego va a la izquierda o a la derecha en función del valor (línea 10). Si el valor ya existe, devolverá el nodo found y también el padre. En caso de que el nodo no exista, se devuelve igualmente el parent.

BST Node Deletion

Sabemos cómo insertar y buscar el valor. Ahora, vamos a implementar la operación de borrado. Es un poco más complicado que añadir, así que vamos a explicarlo con los siguientes casos:

Borrar un nodo hoja (0 hijos)

1
2
3
4
5
6
7
 
 30 30
/ \ remove(12) / \
10 40 ---------> 10 40
\ / \ \ / \
15 35 50 15 35 50
/
12*

Eliminamos la referencia del padre del nodo (15) para que sea nula.

Borrar un nodo con un hijo.

1
2
3
4
5
 
 30 30
/ \ remove(10) / \
10* 40 ---------> 15 40
\ / \ / \
15 35 50 35 50

En este caso, vamos al padre (30) y sustituimos el hijo (10) por un hijo del hijo (15).

Eliminar un nodo con dos hijos

1
2
3
4
5
 
 30 30
/ \ remove(40) / \
15 40* ---------> 15 50
/ \ /
35 50 35

Estamos eliminando el nodo 40, que tiene dos hijos (35 y 50). Reemplazamos el hijo del padre (30) (40) por el hijo derecho (50). Luego mantenemos el hijo izquierdo (35) en el mismo lugar de antes, por lo que tenemos que hacerlo hijo izquierdo de 50.

Otra forma de eliminar el nodo 40 es mover el hijo izquierdo (35) hacia arriba y luego mantener el hijo derecho (50) donde estaba.

1
2
3
4
5
 
 30
/ \
15 35
\
50

Cualquiera de las dos formas está bien siempre que se mantenga la propiedad del árbol de búsqueda binario: left < parent < right.

Eliminar la raíz.

1
2
3
4
5
 
 30* 50
/ \ remove(30) /
15 50 ---------> 35
/ /
35 15

Eliminar la raíz es muy similar a eliminar los nodos con 0, 1 o 2 hijos comentados anteriormente. La única diferencia es que después hay que actualizar la referencia de la raíz del árbol.

Aquí tienes una animación de lo que hemos discutido.

La animación mueve hacia arriba el hijo/subárbol de la izquierda y mantiene el hijo/subárbol de la derecha en su sitio.

Ahora que tenemos una buena idea de cómo debería funcionar, vamos a implementarlo:

BinarySearchTree.prototype.removeFull Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
remove(value) {
const nodeToRemove = this.find(value);
if (!nodeToRemove) return false;
// Combine left and right children into one subtree without nodeToRemove
const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove);
if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) {
nodeToRemove.meta.multiplicity -= 1; // handle duplicated
} else if (nodeToRemove === this.root) {
// Replace (root) node to delete with the combined subtree.
this.root = nodeToRemoveChildren;
this.root.parent = null; // clearing up old parent
} else {
const side = nodeToRemove.isParentLeftChild ? 'left' : 'right';
const { parent } = nodeToRemove; // get parent
// Replace node to delete with the combined subtree.
parent = nodeToRemoveChildren;
}
this.size -= 1;
return true;
}

Aquí tienes algunos puntos destacados de la implementación:

  • Primero, buscamos si el nodo existe. Si no existe, devolvemos false, ¡y ya está!
  • Si el nodo a eliminar existe, entonces combinamos los hijos de la izquierda y de la derecha en un subárbol.
  • Reemplazamos el nodo a eliminar con el subárbol combinado.

La función que combina el subárbol de la izquierda en el de la derecha es la siguiente:

BinarySearchTree.prototype.combineLeftIntoRightSubtreeFull Code
1
2
3
4
5
6
7
8
 
combineLeftIntoRightSubtree(node) {
if (node.right) {
const leftmost = this.getLeftmost(node.right);
leftmost.left = node.left;
return node.right;
}
return node.left;
}

Por ejemplo, digamos que queremos combinar el siguiente árbol, y estamos a punto de eliminar el nodo 30. Queremos mezclar el subárbol izquierdo del 30 con el derecho. El resultado es este:

1
2
3
4
5
6
7
 
 30* 40
/ \ / \
10 40 combine(30) 35 50
\ / \ -----------> /
15 35 50 10
\
15

¡Si hacemos del nuevo subárbol la raíz, entonces el nodo 30 ya no existe!

Transversal de Árbol Binario

Hay diferentes formas de recorrer un Árbol Binario, dependiendo del orden en que se visiten los nodos: dentro del orden, antes del orden y después del orden. Además, podemos utilizar losDFSyBFSque aprendimos en el post de gráficos.Vamos a repasar cada uno de ellos.

In-OrderTraversal

Los traversales in-order visitan los nodos en este orden: izquierda, padre, derecha.

BinarySearchTree.prototype.inOrderTraversalFull Code
1
2
3
4
5
 
* inOrderTraversal(node = this.root) {
if (node.left) { yield* this.inOrderTraversal(node.left); }
yield node;
if (node.right) { yield* this.inOrderTraversal(node.right); }
}

Usemos este árbol para hacer el ejemplo:

1
2
3
4
5
6
7
 
 10
/ \
5 30
/ / \
4 15 40
/
3

El recorrido en orden imprimiría los siguientes valores: 3, 4, 5, 10, 15, 30, 40. Si el árbol es un BST, entonces los nodos serán ordenados en orden ascendente como en nuestro ejemplo.

Post-Order Traversal

Post-order traversal visitan los nodos en este orden: izquierda, derecha, padre.

BinarySearchTree.prototype.postOrderTraversalFull Code
1
2
3
4
5
 
* postOrderTraversal(node = this.root) {
if (node.left) { yield* this.postOrderTraversal(node.left); }
if (node.right) { yield* this.postOrderTraversal(node.right); }
yield node;
}

El recorrido post-orden imprimiría los siguientes valores: 3, 4, 5, 15, 40, 30, 10.

Pre-Order Traversal y DFS

Pre-order traversal visitan los nodos en este orden: padre, izquierda, derecha.

BinarySearchTree.prototype.preOrderTraversalFull Code
1
2
3
4
5
 
* preOrderTraversal(node = this.root) {
yield node;
if (node.left) { yield* this.preOrderTraversal(node.left); }
if (node.right) { yield* this.preOrderTraversal(node.right); }
}

El recorrido preordenado imprimiría los siguientes valores: 10, 5, 4, 3, 30, 15, 40. Este orden de números es el mismo resultado que obtendríamos si ejecutáramos la búsqueda en profundidad (DFS).

BinarySearchTree.prototype.dfsFull Code
1
2
3
4
5
6
7
8
9
10
11
12
 
* dfs() {
const stack = new Stack();
stack.add(this.root);
while (!stack.isEmpty()) {
const node = stack.remove();
yield node;
// reverse array, so left gets removed before right
node.descendants.reverse().forEach(child => stack.add(child));
}
}

Si necesitas un repaso sobre DFS, lo cubrimos en detalle en el post Graph.

Búsqueda por el ancho (BFS)

De forma similar a DFS, podemos implementar un BFS cambiando el Stack por un Queue:

BinarySearchTree.prototype.bfsFull Code
1
2
3
4
5
6
7
8
9
10
11
 
* bfs() {
const queue = new Queue();
queue.add(this.root);
while (!queue.isEmpty()) {
const node = queue.remove();
yield node;
node.descendants.forEach(child => queue.add(child));
}
}

El orden BFS es: 10, 5, 30, 4, 15, 40, 3

Árboles equilibrados vs. no equilibrados

Hasta ahora, hemos hablado de cómo add, remove y find elementos. Sin embargo, no hemos hablado de los tiempos de ejecución. Pensemos en los peores escenarios.

Digamos que queremos sumar números en orden ascendente.

¡Terminaremos con todos los nodos en el lado derecho! Este árbol desequilibrado no es mejor que un LinkedList, por lo que encontrar un elemento llevaría O(n). 😱

Buscar algo en un árbol desequilibrado es como buscar una palabra en el diccionario página a página. Cuando el árbol está equilibrado, puedes abrir el diccionario por la mitad, y a partir de ahí, sabes si tienes que ir a la izquierda o a la derecha dependiendo del alfabeto y de la palabra que estés buscando.

¡Necesitamos encontrar una manera de equilibrar el árbol!

Si el árbol estuviera equilibrado, podríamos encontrar elementos en O(log n) en lugar de pasar por cada nodo. Hablemos de lo que significa un árbol equilibrado.

Si buscamos 7 en el árbol no equilibrado, tenemos que ir del 1 al 7. Sin embargo, en el árbol equilibrado, visitamos: 4, 6 y 7. La cosa empeora aún más con los árboles más grandes. Si tiene un millón de nodos, la búsqueda de un elemento inexistente puede requerir que visite todo el millón mientras que en un árbol equilibrado. ¡Sólo necesita 20 visitas! Es una gran diferencia!

Vamos a resolver este problema en el próximo post utilizando árboles auto-equilibrados (árboles AVL).

Resumen

Hemos cubierto mucho terreno para los árboles. Vamos a resumirlo con viñetas:

  • El árbol es una estructura de datos donde un nodo tiene 0 o más descendientes/hijos.
  • Los nodos del árbol no tienen ciclos (acíclicos). Si tiene ciclos, es una estructura de datos Graph en su lugar.
  • Los árboles con dos hijos o menos se llaman: Árbol Binario
  • Cuando un Árbol Binario se ordena de forma que el valor de la izquierda es menor que el padre y el de los hijos de la derecha es mayor, entonces y sólo entonces tenemos un Árbol de Búsqueda Binaria.
  • Se puede visitar un árbol de forma pre/postintencional.
  • Un desequilibrado tiene una complejidad temporal de O(n). 🤦🏻
  • Un equilibrado tiene una complejidad de tiempo de O(log n). 🎉

Deja una respuesta

Tu dirección de correo electrónico no será publicada.