educacion


[arboles enhebradoS]
ESTRUCTURA DE DATOS


ÁRBOLES ENHEBRADOS

El uso y aplicación de los árboles binarios son variadas y se emplean para
representar estructuras de datos en las cuales setienen que tomar decisiones entre puntos diferentes.

En términos matemáticos, un árbol es cualquier conjunto de puntos, llamados vértices, y cualquier conjunto de pares de distintos vértices,llamados lados o ramas, a una secuencia de ramas, se le conoce como ruta de cualquier vértice a cualquier otro vértice. Un árbol es una estructura de datos no lineal, las estructuras de datos lineales secaracterizan por que a cada elemento le corresponde no más que un elemento siguiente.

Arbol enhebrado
Otro tipo de árboles binarios que podemos encontrar son los enhebrados, denominado así porquecontiene hebras hacia la derecha o a la izquierda. En la siguiente figura se ilustra el ejemplo de un árbol enhebrado a la derecha.





Los árboles enhebrados se utilizan para el mejoraprovechamiento de la memoria. Sus ventajas principales son las siguientes: no se requiere el uso de pilas para el recorrido, el recorrido en orden puede hacerse de manera iterativa, por lo tanto no senecesita el uso de la recursividad para realizar los recorridos.
Árbol enhebrado a la derecha. Su estructura fundamental contienen un puntero hacia la derecha, el cual dirige un nodo antecesor.
Árbolenhebrado a la izquierda. Éste contiene un puntero hacia la izquierda, el cual dirige a un nodo antecesor en orden.


Las operaciones de recorrido en un árbol binario de búsqueda, implementadasmediante funciones recursivas o con un stack de los nodos a revisar, son generalmente costosas en tiempo de ejecución.
Para lograr recorridos eficientes en un árbol puede modificarse la estructura delnodo, agregando un puntero al padre, o bien añadiendo un par de punteros al sucesor y predecesor, formando de este modo listas doblemente enlazadas. Una alternativa que demanda menos bits en cada...