Antes de iniciar la clase, el profe atendió dudas acerca del primer proyecto que se entregaba el mismo día.

Árboles de Datos

Son una estructura de almacenamiento de datos, combina ventajas tanto de los arreglos como de las litas enlazadas. Su funcionamiento permite realizar búsquedas de datos de manera mas rápida y sencilla, aparte de que se pueden agregar y eliminar elementos. Son las estructuras que más se utilizan para manejo de muchos datos, los cuales se les quiere acceder de manera eficiente y rápida. Los arboles están compuestos por nodos (elementos) y aristas, cuya función visual es mostrar a cuales sub-árboles una raíz tiene relación.

Existen varios tipos de árboles, los principales son:

• Árboles binario
• Árboles Heap
• Árboles AVL
• Árboles Splay
• Árboles B, B+, B*
• Árboles de expresión
• Árboles n-arios

Los árboles presentan niveles, los nodos que se encuentran en el mismo nivel no tiene relación alguna, un nodo puede tener hijos los cuales a su vez son sub-árboles. Para manejo y bases de datos se utilizan árboles B.

Raíz: es el nodo en la parte más alta del árbol. Solo hay una raíz por árbol.

En los árboles se debe cumplir que:

• Cualquier nodo (excepto la raíz), tiene exactamente una arista que va hacia arriba a otro nodo, este nodo se conoce como "padre".
• Cualquier nodo puede tener aristas hacia abajo, estas aristas muestran una relación con nodos que se encuentren debajo, estos nodos se llaman "hijos".
• Un nodo que no tiene hijos o sus referencias son nulas se le llama hoja.
• Nodos con el mismo padre son hermanos.
• El largo de un ruta es la cantidad de aristas entre un nodo y otro. El largo de una ruta de un nodo a sí mismo es 0.
• La profundidad de un nodo es el largo de la ruta desde la raíz del árbol y el nodo a revisar.
• La raíz presenta una profundidad de cero.
• La altura de un nodo es el largo de la ruta más larga desde un nodo hasta el nodo hoja que se encuentre en un nivel más alto, o en otras palabras que se encuentre más abajo dentro del mismo sub-árbol.
• Un nodo es visitado si al recorrer el árbol, se hace una operación con ese nodo.
• Atravesar un árbol es recorrer y visitar todos los nodos en un orden específico.

Árbol binario

• Los nodos tienen un máximo de dos hijos.
• A sus hijos se le llaman hijo derecho e izquierdo
• Para ser un árbol binario de búsqueda se debe cumplir que el hijo izquierdo sea menor al padre y el hijo derecho sea mayor al padre.

Dependiendo de el orden de inserción de los datos en un árbol, este puede llegar a estar desbalanceado.