¿Qué es un árbol binario?
Un árbol binario es un tipo de estructura de datos utilizada en la programación de computadoras para almacenar, ordenar y acceder a información. Los árboles binarios son la variedad más simple de árbol, pero son muy útiles y fáciles de implementar. Una implementación típica de un árbol binario se basa en un nodo raíz vinculado a una serie de nodos que conforman el árbol en sí mediante variables de puntero. Este tipo de árbol deriva su nombre del hecho de que ningún nodo dentro del árbol puede tener más de dos hijos.
Las estructuras de datos de árbol vienen en muchas variedades. Están formados por diferentes nodos, que están organizados en un patrón jerárquico. Un solo nodo, la raíz, es el punto de acceso a través del cual se puede buscar o manipular todo el árbol de datos. Este nodo raíz apunta al nodo superior dentro del propio árbol.
Cualquier nodo dentro de un árbol, salvo el nodo superior, tendrá un nodo padre que se encuentra encima de él en la jerarquía del árbol. También puede tener nodos secundarios, que se encuentran debajo de él. Se accede a un nodo dado a través de los que están arriba en el árbol y proporciona acceso a los que están debajo de él.
Las estructuras de datos de árbol binario permiten que cada nodo no tenga más de dos hijos. Por lo tanto, un nodo dado puede tener cero, uno o dos nodos secundarios adjuntos. Los árboles binarios ordinarios permiten nodos con cualquier número de hijos en cualquier punto del árbol. Tampoco imponen restricciones sobre cómo se organizan los valores almacenados en los nodos que comprenden un árbol.
Las estructuras de datos son más útiles cuando mejoran la velocidad con la que una computadora puede acceder a los datos, y se utilizan versiones modificadas de árboles binarios para mejorar su eficiencia. Un árbol de búsqueda binaria es aquel en el que todos los valores de datos ubicados en la rama descendente izquierda de un nodo dado tienen valores iguales o menores que el valor almacenado en ese nodo. Los valores en el lado derecho de un nodo en un árbol binario ordenado deben, a su vez, ser mayores que el valor en el nodo base. Este ordenamiento de datos permite escribir un algoritmo de búsqueda mucho más eficiente.
La forma de un árbol binario también es importante para determinar la eficiencia de un algoritmo de búsqueda. La variedad menos eficiente de un árbol binario es aquella en la que cada nodo tiene un solo hijo. Es posible que una computadora deba examinar cada elemento de datos en todo el árbol para ubicar una sola pieza de información en esta configuración. El árbol binario más eficiente, en cambio, es uno en el que todos los nodos, excepto aquellos en la parte inferior del árbol, tienen dos hijos y donde todos los nodos de las hojas, los nodos inferiores del árbol, están a la misma distancia de la raíz.