¿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 la información. Los árboles binarios son la variedad más simple de árboles, 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 componen el árbol en sí por 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 los árboles 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 o manipularse. Este nodo raíz apunta al nodo superior dentro del árbol mismo.
Cualquier nodo dentro de un árbol, salvo por el nodo más alto, tendrá un nodo principal que se encuentra encima en la jerarquía del árbol. También puede tener nodos infantiles, que se encuentran debajo de él. Un nodo dado es ACCESsed a través de los que están por encima del árbol y proporciona acceso a los que están debajo de él.
Las estructuras de datos de árboles binarios permiten que cada nodo no tenga más de dos hijos. Por lo tanto, un nodo dado puede tener nodos de cero, uno o dos hijos unidos a él. Los árboles binarios ordinarios permiten nodos con cualquier número de niños en cualquier momento 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 las versiones modificadas de los árboles binarios se utilizan para mejorar su eficiencia. Un árbol de búsqueda binario es aquel en el que todos los valores de datos ubicados en la rama descendente izquierda desde un nodo dado tienen valores que son iguales o menos 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 enel nodo base. Este pedido de datos permite que se escriba 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 uno en el 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 información en esta configuración. El árbol binario más eficiente, en contraste, es uno en el que cada nodo salvo para aquellos en el fondo del árbol tiene dos hijos y donde todos los nodos de la hoja, los nodos inferiores en el árbol, están a la misma distancia de la raíz.