24 de junio - JoseA4718/Portafolio-I-2020 GitHub Wiki

Se continuó con los árboles AVL y los métodos de rotaciones para arreglar desbalanceos

Árboles Splay

Son árboles binarios, que mantienen los elementos con uso más frecuente en la parte superior del árbol. A este tipo de árbol no le interesa el factor de balanceo, pues no debe cumplir con esa condición. Se vieron los diferentes tipos de rotaciones: zig, zag, zig-zag. Los cuales sirven para tener el valor necesitado, como la raíz del árbol para poder accesarlo. Se estudiaron las operaciones como

• insertion
• find
• findMin
• findMax
• deleteMin
• deleteMax
• remove

Árbol Heap

Es un árbol binario que se pueden implementar con arrays y listas enlazadas esto permite que su inserción sea muy rápida. Los nodos son acomodados en un orden de izquierda a derecha y se les asigna su valor en este mismo orden, de no estar así, el árbol no es considerado un árbol heap, podríamos decir que cada llave del nodo debe ser mayor a la de sus hijos esto para poder aplicar una cola de prioridad.

Siendo k la posición del nodo se pueden aplicar las siguientes operaciones: Para obtener el padre de cierto nodo se aplica (k-1)/2, para obtener el hijo izquierdo de cierto nodo se aplica (k-1)+1, y por último para obtener el hijo derecho de cierto nodo se aplica (k+2)+2

Al final de la clase el profe se reunió con los grupos del proyecto #2 para saber cómo iban avanzando en el mismo.