trabajos

Árboles.
Un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja.
Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar durante laejecución de un programa. No-lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Características y propiedades de los árboles.
1.* NODO indica un elemento, o ítem, de información.
2.* Todo árbol que no es vacío, tiene un único nodo raíz.
3.* Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.
4.* Un nodo X esantecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.
5.*Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.
6.* Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
7.* Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
8.* Grado es el número dedescendientes directos de un determinado nodo. Grado de árboles el máximo grado de todos los nodos del árbol.
9.* Niveles el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene nivel 1.
10.*Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Tipo de árboles.

Árboles Binarios.
Un árbol binario es una estructura dedatos 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. Usos comunes de los árboles binarios son los árboles binarios de búsqueda,los montículos binarios y Codificación de Huffman.
Árbol de búsqueda binario auto-balanceable.
Un á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úsquedabinaria 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 la rotación de árboles, en momentos clave.
Árboles AVL.
Un árbol AVL es un tipoespecial 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ó
Árboles Rojo-Negro.
Un á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 porRudolf 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 tiempo O(log n), donde n es el número de elementos del árbol
ÁrbolAA.
Los árboles AA 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. De esta manera se simula un árbol 2-3 en lugar de un árbol 2-3-4, lo que simplifica las operaciones de...