ARBOLES

El ARBOL es una estructura del tipo JERARQUICA, cada arbol nace de un nodo o raiz principal y desciende en otros nodos que pueden descender en mas o no descender en nada y quedar como hojas. Los arboles pueden ser del tipo BINARIO, aqui cada arbol nace de una raiz y luego tiene un subarbol a su izquierda y un subarbol a su derecha(y asi sucesivamente), no obstante tambien existen arboles mas elementales como que tenga un solo subarbol de alguno de los lados o que haya un solo nodo y el arbol este vacio.

Una implementacion del arbol binario en java seria:

public class Nodo {
	private Info informacionDelNodo;
	private Nodo nodoIzquierdo;
	private Nodo nodoDerecho;
}

Los arboles binarios se pueden recorrer de 3 maneras:

• PRE-ORDEN(RID): RAIZ-IZQUIERDA-DERECHA
• POST-ORDEN(IDR): IZQUIERDA-DERECHA-RAIZ
• IN-ORDEN(IRD): IZQUIERDA-RAIZ-DERECHA

El post-orden es interesante porque es como se organizan las operaciones aritmeticas para procesarlas en la cpu. El in-orden es interesante porque al pasar a un arbol binario de busqueda a este recorrido nos lo devuelve ordenado.

La manera de organizar los arboles binarios de busqueda suele ser que lo menor que la raiz se encuentre a la izquierda y lo mayor a la derecha. Pero es posible que el arbol se degenere si hay mayor cantidad de nodos menores o mayores(tiende a irse para un costado), en este caso las busquedas van a tardar mas ya que no se descarta la mitad del arbol en cada busqueda, por eso si queremos recuperar esta eficiencia debemos balancear el arbol(un arbol balanceado es aquel que tiene una cantidad igual o parecida de nodos en ambos lados).

HEAP

El HEAP o MONTICULO es un tipo de arbol especial puesto que debe cumplir de 2 CONDICIONES:

1. El arbol debe estar COMPLETO o CASI COMPLETO, es decir, todos los niveles deben estar completos o el ultimo nivel debe tener todas sus hojas de izquierda a derecha sin huecos

1. El arbol tiene que estar definido por MINIMO o MAXIMO:
   • Si el arbol es MINIMO, entonces el valor clave siempre es menor que todos sus descendientes.
   • Si el arbol es MAXIMO, entonces el valor clave siempre es mayor que todos sus descendientes.

INSERCION: COMPLEJIDAD O(log n):

Cuando quiero agregar un valor nuevo a este arbol, para no romper con estas condiciones lo que se hace es lo siguiente, se agrega el nuevo nodo abajo a la izquierda(el ultimo de izquierda a derecha) y luego se va comparando e intercambiando con todos los demas nodos hasta encontrar donde debe ir su valor.

EXTRACCION: COMPLEJIDAD O(log n):