Un árbol binario es un tipo de estructura de datos que se utiliza en la programación de computadoras para almacenar, clasificar 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 forman el propio árbol 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 á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. Este nodo raíz apunta al nodo superior dentro del propio árbol.
Cualquier nodo dentro de un árbol, a excepción del nodo superior, tendrá un nodo padre que se encuentra por 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 determinado a través de los que están encima de él en el árbol y proporciona acceso a los que están debajo.
Las estructuras de datos de árbol binario permiten que cada nodo no tenga más de dos hijos. Por tanto, un nodo dado puede tener cero, uno o dos nodos hijos 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 componen 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 que son 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 orden 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 necesite 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, por el contrario, es aquel en el que todos los nodos, salvo los que están 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.