Los datos se almacenan comúnmente en estructuras de árbol binario utilizando algoritmos especializados. Muchas ventajas provienen de almacenamiento de datos en una estructura de árbol. Por ejemplo, buscar un árbol binario ordenado es mucho más rápido que la clasificación de una estructura de datos secuenciales, tales como una matriz. Una estructura de datos de árbol puede asumir muchos tipos de patrones durante el curso de acceso a datos y modificación. La comprensión de estos patrones puede ayudar a diseñar mejores algoritmos para optimizar un algoritmo de árbol.
Los componentes básicos de un árbol binario
Un árbol binario consiste en nodos, que almacenan los datos y puntos de otros nodos en el árbol. El nodo raíz es el punto de partida del árbol y ocupa el nivel superior. Puede tener hasta dos nodos secundarios. Estos nodos secundarios también pueden tener hasta dos nodos secundarios. El número de nodos hijos de un nodo dado se llama el grado del nodo. Un nodo sin hijos y un grado de cero se llama una hoja. La longitud en los nodos desde el nodo raíz hasta el nodo más alejado de la hoja es la altura del árbol. La profundidad de un nodo es la distancia desde el nodo raíz a la misma. Cada nodo que tiene la misma profundidad se dice que es en el mismo nivel.
Árbol binario completo
Un árbol binario completo es un árbol en el que cada nodo tiene exactamente dos o cero niños. En otras palabras, cada nodo o bien tiene dos hijos o es una hoja. Un ejemplo de un árbol binario completo es la decisión binaria Diagrama, o BDD.
Perfecto Binary Tree
Un árbol binario perfecto tiene las mismas propiedades de la árbol binario completo, pero todos los nodos de hoja están en el mismo nivel, lo que significa que la profundidad de todas las hojas es el mismo en un árbol binario perfecto. Dado que es también un árbol binario completo, todos los nodos excepto los nodos hoja tienen un grado de 2.
Equilibrada árbol binario
Un árbol binario equilibrado es una en la que la profundidad de cada nodo hoja es el mismo o diferente por un valor de uno. Adición y eliminación de nodos de un árbol binario equilibrado puede desequilibrar ella, por lo que una serie de ajustes llamados rotaciones deben tener lugar para reequilibrar el árbol. El mantenimiento de un árbol equilibrado asegura que el tiempo medio de búsqueda para cualquier nodo es óptima. Se requiere importantes gastos para mantener el equilibrio de un árbol.
Degenerada Binary Tree
Un árbol binario degenerada es uno en el que cada nodo excepto el nodo hoja tiene exactamente un nodo hijo. Tiene las mismas características de funcionamiento de una lista enlazada, lo que aumenta el tiempo de búsqueda para cualquier nodo por una cantidad considerable. Por ejemplo, considere un caso en el que el nodo que se busca es el nodo hoja. Todo el árbol debe ser atravesado a fin de encontrar este nodo. Con un árbol binario equilibrado, la búsqueda de un nodo hoja sólo requiere un número de recorridos de nodo igual a la profundidad del nodo hoja. Con árboles de gran tamaño, la diferencia de rendimiento puede ser significativo.