Introducción a los árboles en la programación: el oxígeno de la codificación eficiente

Muchas veces desea guardar información en su programa y acceder a ella muchas veces. Y a menudo lo almacenará en una estructura de datos muy simple: una matriz. ¡Y a menudo funciona muy bien! Pero a veces solo se necesita mucho tiempo para terminar.

Y así, para optimizar este tipo de programa, mucha gente inteligente desarrolló algunas cosas extrañas que llamamos estructuras de datos . Hoy abordaré algunos conceptos básicos sobre este tema y discutiré una estructura específica que a menudo se pregunta durante las entrevistas de codificación y que vuelve locos a todos: los árboles.

No me sumergiré mucho en el código, solo en la teoría de cómo funciona todo. Hay millones de ejemplos de código en línea, ¡así que solo eche un vistazo a uno después de comprender cómo funcionan los árboles!

Entonces, ¿qué es realmente una estructura de datos?

Según Wikipedia:

"Una estructura de datos es una organización de datos y un formato de almacenamiento que permite un acceso y una modificación eficientes"

Básicamente, esto significa que no es más que un código escrito para crear una forma compleja de almacenar datos. Hay muchas estructuras de datos que puede implementar y cada una tiene una tarea específica. Pueden ir desde los realmente simples, como listas enlazadas, hasta estructuras realmente complejas, como gráficos.

Los árboles son lo suficientemente complejos como para ser realmente rápidos en lo que hacen, pero lo suficientemente simples como para que sean comprensibles. Y una cosa en la que son realmente buenos es encontrar valores con un uso mínimo de memoria.

Pero, ¿cómo se mide la eficiencia de una estructura de datos?

¿Alguna vez has visto alguna notación extraña que la gente usa en línea como O (n)? Eso se llama notación Big O, y es la forma estándar de evaluar el rendimiento de estructuras y algoritmos. La gran O que usamos es la representación del peor de los casos: tener algo que sea O (n) (siendo n el número de elementos dentro) significa que en el peor de los casos se necesita tiempo n , lo cual es realmente bueno.

Dentro del paréntesis, escribimos n, que es el equivalente a escribir la expresión y = x →. Escala proporcionalmente. Pero a veces tenemos diferentes expresiones:

  • O (1)
  • O (registro (n))
  • En)
  • O (n²)
  • O (n³)
  • ¡En!)
  • O (e ^ n)

Cuanto menor sea el resultado de una función, más eficiente será una estructura.

Hay varios tipos de árboles. Hablaremos de BST (árboles de búsqueda binaria) y árboles AVL (árboles equilibrados automáticamente) que tienen diferentes propiedades:

Ok, hablaste de toda esta extraña notación ... entonces, ¿cómo funcionan los árboles?

El nombre árbol proviene de su representación real: tiene una raíz, hojas y ramas, y a menudo se representa así:

Hay algunas denominaciones que usamos, a saber, padre e hijo, que tienen una relación única. Si x es padre de y, entonces y es hijo de x . En esta imagen, 2 es padre de 5, luego 5 es hijo de 2. Cada nodo, cada posición con un valor, solo puede tener 1 padre y 2 hijos.

Pero además de todo esto, no hay un patrón que se siga, por lo que este árbol no es realmente tan útil… Así que deberíamos agregar algunas reglas más para hacer una buena estructura de datos.

Árboles de búsqueda binaria

¡Ahí es cuando entran los árboles de búsqueda binaria! En lugar de colocar nodos secundarios al azar, siguen un orden específico:

  • Si no hay nodos, el primer valor que se ingresa se convierte en la raíz del árbol.
  • Si hay nodos, entonces la inserción toma los siguientes pasos: comenzando en la raíz, si el valor que está ingresando es menor que el nodo actual, pase por la rama izquierda, de lo contrario, pase por la derecha. Si estás en un lugar vacío, ¡ahí es donde pertenece tu valor!

Esto puede parecer un poco confuso al principio, pero escribamos un pseudocódigo para simplificarlo:

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) { if n is NULL: return createNode(v) else if n.value < v: n.right = insert(n.right, v) else: n.left = insert(n.left, v) return n}

Ahora, ¿qué está pasando aquí? Primero comprobamos si el lugar donde estamos ahora está vacío. Si es así, creamos un nodo en ese lugar con la función createNode. Si no está vacío, entonces debemos ver dónde debemos colocar nuestro nodo.

Esta demostración muestra cómo funciona:

De esta forma podemos buscar cualquier valor en el árbol sin tener que pasar por todos los nodos. ¡Excelente!

Pero no siempre va tan bien como en el gif anterior. ¿Y si obtenemos algo como esto?

En este caso, el comportamiento del árbol le hace pasar por todos los nodos. Es por eso que la peor eficiencia de un BST es de O (n), lo que lo hace lento.

Eliminar de la BST también es fácil:

  • Si un nodo no tiene hijos → elimine el nodo
  • Si un nodo tiene un hijo → conecte el nodo padre a su nodo nieto y elimine el nodo
  • Si un nodo tiene 2 hijos → sustituya el nodo por su hijo mayor (el hijo más a la derecha a la izquierda) → vea la imagen a continuación

Así que ahora sabes todo lo que necesitas sobre BST. Bastante bien, ¿eh?

Pero, ¿y si quisiera SIEMPRE tener un árbol eficiente? ¿Qué harías?

Si tiene esa necesidad, los árboles AVL pueden hacerlo bastante bien. A cambio, son millones de veces más complejos que los BST, pero siguen la misma organización que antes.

An AVL tree is a self-balancing tree that has specific operations (called rotations) that allow the tree to stay balanced . This means that each node in the tree will have a difference of height between its two child branches of maximum 1.

With this, the tree will always have a height of log(n) (n being the number of elements) and this allows you to search for elements in a really efficient way.

So now you see how good and perfect balanced trees are. But how to make them is the real question. I have mentioned the word depth before, so let’s first understand it.

Height is what allows us to understand if our tree is balanced or not. And with it we’re able to determine where the problem is and apply the balancing functions: rotations. These are really simple functions that consist of exchanging nodes between each other in order to remove the height difference, but they might look really strange at first.

There are 4 operations:

  • Rotation Left
  • Rotation Right
  • Rotation Left-Right
  • Rotation Right-Left

Wow that was strange… how do rotations work?

Rotations are strange at first, and I suggest checking out some animations of them working.

Try with your own trees on this website: //www.cs.usfca.edu/~galles/visualization/AVLtree.html

It allows you to dynamically see the rotations happening and is a great tool!

There are only four cases, so understanding them will be easy.

That’s all for now!

Trees are pretty easy to understand, and with practice you can work with them easily. Applying them in your code is a major key to make your programs a lot more efficient.

If you have any questions about something you didn’t understand, disagree with, or would like to suggest, feel free to contact me through Twitter or by email!

Email: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt