Clase 21

Se ve la insercion en un arbol AVL Repaso de rotacion sencilla o una doble

Casos de insercion de desbalanceo

Simples Left - Left : n.left = n1.right; n1.right = n; n = n1;

Right - Right : n.right= n1.left; n1.left = n; n = n1;

Dobles Right - Lef n1.left = n2.right; n2.right = n1; n.right= n1.left; n1.left = n; n = n1;

Arboles Splay

Es una implementacion eficiente de arbol binario, que mejora la velocidad de busqueda. Cuando se busca un nodo en el splay mueve el nodo a la raiz. Los elementos que son muy visitados se encuentran cerca de la raiz

Rotaciones

Zig simple:

• Cuando el padre del nodo es la raiz: La misma rotacion simple del AVL

Zig-Zag

• X(hijo), Y(padre), V(abuelo): Misma rotacion doble de AVL. Y es hijo izq y X es un hijo der

Operaciones

Insertar

El nodo insertado se rota para que sea la raiz

Buscar

Si el nodo se encuentra, este pasa a ser la raiz. Si no se encuentra, el ultimo nodo preguntado pasa a ser la raiz

Find Min

Al encontrar el min, este pasa e ser la raiz

Delete Min

Aplica Find Min Y el .derecha se vuelve raiz

Delete

El nodo a eliminar va a la raiz, eliminar la raiz, quedan dos subarboles R L. Hacer Find Max a L, pero sin eliminar el Max La nueva raiz de L en su .right va ser R Se aplica lo mismo pero con R y con Find Min.