Ensayo De La Constitucion De La Republica De Honduras

ÁRBOLES

Son una de las estructuras de datos comunes en la programación de software para almacenar y procesar datos que se definen como estructuras jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz, además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

Representan las estructuras no lineales y dinámicas de datos más importantes en computación;dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa; no lineales puesto que a cada elemento del árbol pueden seguirle varios elementos.

Los árboles pueden ser construidos con estructuras estáticas y dinámicas;las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.

Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, en la toma de decisiones, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro.

CLASIFICACIÓN DE LOS ÁRBOLES

ÁRBOLES BINARIOS

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho; no pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a NULL, es decir que no almacena ningún dato, entonces este es llamado un nodo externo;en el caso contrario el hijo es llamado un nodo interno y losusos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de HUFFMAN.

Los árboles binarios se clasifican en:

1. ÁRBOL BINARIO DE BÚSQUEDA AUTO-BALANCEABLE O EQUILIBRADO

Es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como larotación de árboles, en momentos clave.

1. ÁRBOL AVL

Es un tipo especial de árbol binario ideado por los matemáticos rusos ADELSON VELSKII Y LANDIS; fue el primer árbol de búsqueda binario auto balanceable que se ideó este tipo de árbol está siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa;gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n); el factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial;si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos; los árboles AVL más profundos son los árboles de Fibonacci.

3. ÁRBOL ROJO NEGRO

Es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación,la estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978;es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempoO(log n), donde n es el número de elementos del árbol.

Es usado en informática para organizar información compuesta por datos comparables (como por ejemplo números); en los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora de implementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas. Así,todas las referencias de los nodos internos a las hojas van a parar al nodo centinela.

En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo.

Se deben satisfacer lo siguiente para tener un árbol rojo-negro válido:

 Todo nodo es o bien rojo o bien negro.

 La raíz es negra.

 Todas las hojas son negras (las hojas son los hijos nulos).

 Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").

 Cada camino simple desde un nodo a una hoja descendiente contiene el mismo número de nodos negros, ya sea contando siempre los nodos negros nulos, o bien no contándolos nunca (el resultado es equivalente). También es llamada "Propiedad del camino", y al número de nodos negros de cada camino, que es constante para todos los caminos, se le denomina "Altura negra del árbol", y por tanto el camino no puede tener dos rojos seguidos.

 El camino más largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol. El resultado es que dicho árbol está aproximadamente equilibrado.

4. ÁRBOL AA

Es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperarinformación ordenada de manera eficiente; los árboles AA reciben el nombre de su inventor ARNE ANDERSSON y son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda, a diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho; En otras palabras, ningún nodo rojo puede ser un hijo izquierdo,

...