EXPLORANDO LAS ESTRUCTURAS DE DATOS EN PYTHON: árboles

En nuestro último post sobre las estructuras en Python hablamos de las pilas y colas. Hoy vamos a adentrarnos en una estructura mas compleja, pero muy útil, sobre todo en ciencia de datos.

los árboles son una de las estructuras de datos más valiosas gracias a su capacidad de almacenar información de forma jerárquica. Básicamente, usamos árboles cuando necesitamos representar relaciones de orden o niveles entre los elementos de información que manipulamos.

• Un árbol está compuesto por un número determinado de nodos, cada uno representando una unidad de información.
• Todo árbol tiene un nodo especial llamado raíz. Funciona como el punto de partida, el elemento principal a partir del cual se construye la estructura.
• Los nodos restantes se enlazan entre sí mediante líneas denominadas ramas. Estas ramas simulan las conexiones o relaciones jerárquicas entre los elementos.

Imaginemos un árbol genealógico. La persona más antigua (por ejemplo, el tatarabuelo) sería la raíz. Sus hijos serían los siguientes nodos conectados a la raíz por ramas. A su vez, cada hijo tendría sus propios hijos que se conectarían como nodos a su respectivo padre (nodo superior), y así sucesivamente.

• Nodo raíz (Root node): Es el nodo inicial y fundamental del árbol. Funciona como el punto de partida de la estructura y, generalmente, almacena el valor más importante. En el siguiente ejemplo, el nodo raíz es A:

      A
     / \
    B   C
   / \ / \
  D   E   F
     / \
    G   H

• Nivel de un nodo (Level of a node): Representa la distancia que tiene un nodo respecto al nodo raíz. Se mide en el número de conexiones (ramas) que hay que atravesar para llegar a él. Por ejemplo, en el diagrama anterior, el nivel de los nodos D, E y F es dos.

• Nodos hermanos (Sibling nodes): Se refiere a dos nodos que se encuentran en el mismo nivel dentro del árbol. Siguiendo el ejemplo, los nodos B y C son hermanos.

• Nodo hijo y padre (Child and parent node): Existe una relación padre-hijo entre nodos conectados directamente. El nodo hijo (child node) se encuentra en un nivel inferior al nodo padre (parent node). En el ejemplo, el nodo F es hijo del nodo C, y a su vez, C es padre de F.

• Grado de un nodo (Degree of a node): Indica la cantidad de hijos que posee un nodo. Por ejemplo, en el diagrama, el nodo B tiene un grado de dos (dos hijos: D y E).

• Grado de un árbol (Degree of a tree): Corresponde al valor máximo del grado que se puede encontrar entre todos los nodos del árbol. En el ejemplo, el árbol tiene un grado de dos (máximo número de hijos por nodo es 2).

• Subárbol (Subtree): Es una parte del árbol completo que se considera como un árbol independiente. Se elige un nodo específico como raíz del subárbol, y todos sus hijos como nodos integrantes. Por ejemplo, un subárbol con raíz en el nodo E del diagrama anterior estaría formado por el propio nodo E como raíz y sus hijos G y H.

• Nodo hoja (Leaf node): Representa un nodo que no tiene hijos. En la figura, los nodos D, G, H y F son nodos hoja.

• Nodo interno (Internal node): Es cualquier nodo que no sea ni raíz ni hoja. Un nodo interno tendrá al menos un padre y al menos un hijo.

• Jerarquía: La estructura del árbol permite visualizar claramente los diferentes niveles de importancia o clasificación entre los datos.
• No linealidad: A diferencia de un arreglo simple donde los elementos van uno tras otro, los árboles no siguen un orden secuencial. La información se organiza en base a las conexiones jerárquicas.

Los árboles que hemos visto hasta ahora pueden tener cualquier grado (número de hijos por nodo). Sin embargo, existen tipos específicos de árboles con restricciones en su estructura:

Un árbol binario es aquel en el que cada nodo tiene como máximo dos hijos. Dicho de otra manera, su grado es igual a 2.

Un árbol completo se caracteriza porque todos sus niveles están completamente llenos, excepto posiblemente el último nivel.

Un árbol perfecto es un caso especial de árbol completo donde todos los nodos hoja se encuentran en el mismo nivel. Como se ve en el ejemplo de la anterior imagen, el árbol binario de la derecha sí es perfecto, ya que todas sus hojas (D, E, F) están en el nivel 2.

En un árbol ordenado, los hijos de un nodo se organizan de acuerdo a un criterio específico. Este criterio puede ser un orden numérico (creciente o decreciente), alfabético u otro tipo de comparación. Por ejemplo, un árbol binario puede ordenarse de izquierda a derecha en forma ascendente, donde los nodos en el mismo nivel aumentan su valor al recorrer de izquierda a derecha.

Imaginemos un árbol que almacena nombres de personas. Podría ordenarse alfabéticamente:

     Pedro
      / \
   Ana   Roberto
  /   \     \
David Elena Daniel

• Sistemas de archivos: Las carpetas y subcarpetas de un computador se organizan como un árbol, donde la raíz es el directorio principal y cada subcarpeta funciona como un nodo con sus respectivos archivos (nodos hoja).
• Árboles de decisión: En inteligencia artificial, se usan para modelar la toma de decisiones. La raíz representa la pregunta inicial, y las ramas las posibles respuestas que conducen a diferentes resultados.

Gracias por leer este post y te espero en el siguiente, no olvides comentar compartir, cualquier duda déjala en los comentarios.