Árboles

Instituto Tecnológico de Costa Rica. Escuela de Computación. Algoritmos y Estructuras de Datos 1 1º Semestre de 2011. Grupo 2.  Prof. Ivannia Cerdas Quesada.

TareaInvestigación sobre árboles Estudiante: Werner Juárez Quirós. Carné: 200760527. Entregado: 05/abr/2011. 

Árbol Splay
Descripción: árbol de búsqueda binarioautobalanceable, donde después de cada operación realizada (sea inserción, eliminación o búsqueda) se hace un llamado a una operación llamada “splay”. Esta operación coloca,mediante rotaciones, el nodo operado (el que se eliminó, inserto o buscó) en la raiz del árbol. Operaciones: En todas ellas “x” es el elemento operado, en otras palabras “x”es el elemento que se quiere colocar como raiz. Zig: únicamente existe X y P (padre de x), por lo q X pasaría a ser la raiz realizando una rotación a la derecha. Existela variante zag, en la cual X es el hijo derecho de P, por lo que la operación sería una rotación a la izquiera en lugar de una a la derecha.

Zig-zig: X y P sonambos hijos izquierdos, por lo que primero se rota a la derecha P y luego a la derecha X. Hay una variante llamada zag-zag donde ambos nodos son hijos derechos, por lo quelas rotaciones serían a la izquierda.

Zig-zag: X es hijo derecho y P es hijo izquierdo, por lo que primero se rota a la izquierda X y luego se rota nuevamente X peroa la derecha, por lo que X quedaría ahora como raiz de el subárbol. ambos hijos izquierdos, por lo que primero se rota a la derecha P y luego a la derecha X. Hay unavariante llamada zag-zig, en la que X es hijo izquierdo y P es hijo derecho, por lo que primero se rota X a la derecha y luego nuevamente X pero a la izquierda.