Clase 19

Estructuras de Datos Jerarquicas

Arboles(Especializacion de los grafos) Small at top, big at bot. Existen Binarios, heap, avl, display, Family B, Expression, N-arios

Combina ventajas de Arreglos(busqueda rapida, acceso indexado) ordenados y listas enlazadas(Facil insercion y delete)

Nodos conectados por aristas

Nodos, almacena datos y referencia a otros nodos hijos

Implementacion en sistemas de archivo, En bases de datos se guardan como variacion de la familia B, en algoritmos de compresion, arboles de expresion

• Recorrer. Proceso Nodo A ----> Nodo B
• Ruta.Path. Nodos visitados
• Raiz. NodoTope
• Arista, Todos poseen una hacia al anterior. Nodo posee solo un padre
• **NodoHoja.Leaf.**No tiene hijos
• Hermanos.Siblings. Poseen mismo padre
• Largo.length. Cantidad de Aristas
• Profundidad.Depth. Cantidad de Aristas hacia nodo especifico
• Altura.height. largo hasta las hojas mas bajas
• Visitado. Ejecutado funcion sobre nodo

Arboles Binarios

(hijo izq y der) max 2 hijos

izq<Nodopadre. der>Nodopadre. Balanceo, Condicion para que sea arbol binario

Arboles Binarios de Busqueda

Estructuras de datos lineales Arreglos o linked list, usando memoria dinamica .Se define un boolean constains() para observar si tiene item. De definen findMin( node) y find max

Operaciones sobre los elementos

compareTo

si es igual return 0, mayor o menor retorna un valor mayor o menor respecivamente

isEmpty

retorna true si esta vacio, false si no

Contains

retorna true si el arbol contiene el elemento buscado, si el arbol no esta vacio, hace llamadas recursivas en sus subarboles

findMin/find max

si el arbol esta vacio retorna null, si no esta vacio llama a otro findMin pero con la raiz como parametro, si el .left != null se vuelve a llamar con el nodo.left (Max igual pero con la derecha), cuando sea == null retorna el nodo

Insertar.

Recorre el arbol usando contains