Arboles Binarios

ÁRBOLES. ÁRBOLES BINARIOS.

Hasta ahora nos hemos dedicado a estudiar TADes que de una u otra forma eran de naturaleza lineal, o unidimensional. En los tipos abstractos de datos lineales existen exactamente un elemento previo y otro siguiente (excepto para el primero y el último, si los hay); en las estructuras no lineales, como conjuntos o árboles, este tipo de secuencialidad no existe, aunque en los árboles existe una estructura jerárquica, de manera que un elemento tiene un solo predecesor, pero varios sucesores.

Una exploración algo amplia en el campo de la ciencia de la computación nos lleva a situaciones en que las representaciones lineales son inadecuadas, tanto en sentido conceptual como práctico. Un paso importante lo representan los árboles binarios, y el siguiente vendrá dado con el estudio de la noción general de árbol. En capítulos posteriores, lo extenderemos hasta llegar a los grafos.

Un árbol impone una estructura jerárquica sobre una colección de objetos. Ejemplos claros de utiización de árboles se presentan tanto dentro como fuera del área de computación (indices de libros, árboles genealógicos, etc.); en Informática constituyen una de las estructuras más utilizadas, con aplicaciones que van desde los árboles sintácticos utilizados para la representación y/o interpretación de términos de un lenguaje o expresiones aritméticas, pasando por los arboles de activación de procedimientos recursivos, hasta la representación de datos que se desea mantener ordenados con un tiempo de acceso relativamente bajo. En general, se usarán árboles siempre que se quiera representar información jerarquizada, cuando esta converja en un solo punto.

...