lab de algoritmos(Representacion y manipulacion de arboles)

Un arbol es una estructura de datos que es conformada por nodos y toma la apariencia de un arbol, el arbol siempre tiene una raiz que es donde comienzan los datos lo que le sigue son los nodos y las hojas puede haber arboles de diferentes tamaños y formas son muy variados por ejemplo arboles que solo tienen la raiz y una hoja o arboles con la raiz 10 nodos y 20 hojas.
cuando hay una sucesion de nodos de forma que entre cada 2 nodos consecutivos de la sucesion haya una relacion de parentesco decimos que es un recorrido de arbol, existen dos tipos de sucesion de arbol el primero es en profundidad por que se listan los nodos expandiendo al hijo actual de cada nodo hasta llegar a una hoja, donde se buelve al nodo anterior probando por el siguiente hijo y asi sucesivamente. el segundo es por anchura el cual antes de listar los nodos de nivel n+1 deben de estar listados todos los de nivel n.

otros recorridos de arbol son:

en preorden el cual consiste en recorrer la raiz despues cada uno de sus hijos
en inorden consiste en primero recorrer los hijos menores luego la raiz y despues los hijos mayores en orden simetrico
en postorden consiste en recorrer cada uno de los hijos en orden posterior y despues la raiz

existen varos tipos de arboles los cuales son:

Arboles binarios


como su nombre lo indica es aquel arbol que tiene dos hijos en cada nodo uno del lado izquierdo y otro del lado derecho si el nodo solo tiene un hijo al espacio vacio se le denomina nodo externo y en el caso contrario donde si tiene datos se le llama nodo interno,
se dice que el arbol binario esta lleno cuando todos sus nodos tienen dos hijos o cuando tienen cero hijos, se le llama perfecto cuando todas sus hojas estan en la misma altura
se pueden construir apartir de lenguajes de programación en un lenguaje con registros y referencias se construyen de forma en la cual se almacenan datos cada uno de esos nodos tiene una referencia o puntero a la derecha o izquierda denominados hijos cuando un nodo no tiene hijos el puntero se puede definir como nulo para indicar que no existe dicho nodo






 arbol binario de busqueda auto-balanceable

es un arbol binario de busqueda el cual intenta mantener su altura, o el numero de niveles de nodos bajo la raiz, esto es importante ya que mmuchas operaciones en un arbol de busqueda tardan un tiempo proporcional a la altura del arbol y si no se balancea puede tomar una gran altura el arbol y tardar demasiado tiempo en una busqueda que si estubiera ordenado tardaria menos de ela mitad del tiempo que tardo  para conseguir que un arbol este balanceado se le hacen modificaciones al arbol como la rotacion de arboles

tiempos en que tardan varias operaciones dependiendo del numero de nodos en el arbol n:

para algunas implementaciones estos tiempos son el peor caso mientras que para otras estan bien

rotaciones de arbol binario de busqueda

la rotacion del arbol consiste en tener un equilibrio como si fuera una balanza para que no se cargue el arbol hacia la derecha ni se cargue hacia la izquierda se puede rotar hacia la derecha o hacia la izquierda 

rotacion simple hacia la derecha 
 

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).



rotacion simple hacia la izquierda

es igual que el de rotacion a la derecha solo que en este caso el hijo que tomara la el puesto de raiz por asi decirlo sera el hijo derecho




una imagen de varios tipos de arboles


para declarar un arbol binario en lnguaje C hay dos maneras declarandolo con estructura de memoria dinamica o con arreglo indexado la primera viene siendo:

typedef struct nodo {
    int clave;
    struct nodo *izdo, *dcho;
}

 Nodo;

y la segunda:

typedef struct tArbol
{
  int clave;
  tArbol hIzquierdo, hDerecho;
} tArbol;
tArbol árbol[NUMERO_DE_NODOS]; 

 esto es todo por mi parte mis fuentes de consulta fueron:

http://es.wikipedia.org/wiki/%C3%81rbol_de_b%C3%BAsqueda_binario_auto-balanceable 

 http://es.wikipedia.org/wiki/%C3%81rbol_%28inform%C3%A1tica%29 

http://www.monografias.com/trabajos36/arboles/arboles2.shtml