Los árboles son estructuras de datos que nos permiten organizar información de forma no lineal, lo que supone un cambio importante respecto a las listas, pilas o colas que hemos visto anteriormente. A diferencia de estas estructuras lineales, donde cada nodo apunta a un único siguiente, en los árboles cada nodo puede apuntar a varios nodos hijos, o incluso a ninguno, y a su vez, cada nodo tiene un único nodo padre, salvo la raíz que no tiene ninguno.
Para entender mejor esta estructura, pensemos en un nodo como una unidad que contiene un valor, por ejemplo un número, y que puede apuntar a otros nodos. El nodo raíz es el punto de partida del árbol, el único que no tiene padre. Desde ahí, cada nodo puede tener varios hijos, y los nodos que no tienen hijos se llaman hojas. Por ejemplo, en un árbol donde el nodo raíz es 16, este puede apuntar a los nodos 8 y 24, que a su vez apuntan a otros nodos, y así sucesivamente. Los nodos 7, 13 y 21 serían hojas porque no apuntan a ningún otro nodo.
Una característica fundamental de los árboles es que no pueden contener ciclos. Esto significa que no podemos tener un nodo que, siguiendo sus hijos, vuelva a apuntar a sí mismo o a un nodo anterior, ni que un nodo tenga más de un padre. Si esto ocurriera, estaríamos ante un grafo con ciclos, no un árbol.
Para representar un árbol en código, una forma sencilla es definir un nodo que contenga un valor y una lista de hijos, que a su vez son nodos. Esto permite expresar la estructura de forma recursiva, ya que cada hijo es a su vez un subárbol.
class Nodo {
int valor;
List<Nodo> hijos;
Nodo(int valor) {
this.valor = valor;
this.hijos = new ArrayList<>();
}
}
Algunas propiedades importantes de los árboles nos ayudan a describir su estructura. El nivel de un nodo indica la distancia que hay desde ese nodo hasta la raíz, contando el número de saltos. Por ejemplo, la raíz tiene nivel 0, sus hijos nivel 1, y así sucesivamente. La profundidad o altura del árbol es el nivel máximo que tiene algún nodo dentro del árbol.
Otro concepto relevante es el orden del árbol, que indica el número máximo de hijos que puede tener un nodo. Por ejemplo, un árbol de orden 2, conocido como árbol binario, permite que cada nodo tenga hasta dos hijos. Esto es importante para controlar la complejidad y la forma en que crece el árbol, prefiriendo que crezca en profundidad más que en anchura para facilitar su manejo.
Existen términos especiales para ciertos tipos de árboles según su orden y estructura. Un árbol completo es aquel en el que todos los nodos tienen el número máximo de hijos permitido, salvo las hojas que no tienen ninguno. Por ejemplo, un árbol binario completo es aquel donde cada nodo tiene dos hijos o es una hoja.
En próximos pasos, nos centraremos en los árboles binarios para explorar operaciones fundamentales como insertar, eliminar, localizar y recorrer nodos. Estas operaciones son clave para aprovechar la eficiencia que ofrecen los árboles binarios, especialmente en aplicaciones como bases de datos donde la rapidez en la búsqueda es crucial.
Así, los árboles nos ofrecen una forma poderosa y flexible de organizar datos, con propiedades y restricciones que los hacen únicos y muy útiles en programación.