Árboles Splay

Características del árbol splay: 

Operaciones en los árboles splay  

Búsqueda: 

En la búsqueda en los árboles splay se tiene la característica particular de que modifica la estructura del árbol, si en lo que se efectúa la operación se encuentra el nodo con el valor indicado a este nodo se le hará una biselación (Es decir cuando encuentra el nodo lo va acercando a la raíz hasta que se convierta en la raíz). En el caso de que no se encuentre el nodo se hará la biselación al último nodo se haya accedido. 

Inserción: 

En la inserción de los árboles splay se inserta como en arboles binarios de búsqueda es decir si el nodo a insertar es mayor a la raíz ira al subárbol derecho si es menor que la raíz ira al subárbol izquierdo y así sucesivamente con cada subárbol hasta encontrar su posición, lo único que cambia es que al ser insertado el nodo en su respectiva posición a este se le hará la biselación quedando como raíz. En el caso de que el nodo insertado ya exista en el árbol se le hará la biselación a este nodo. 

Borrado: 

En el borrado de los árboles splay para hacer la operación de borrado se deben de realizar 2 biselaciones, al nodo que se desea eliminar se le hará una biselación para dejarlo en la raíz y después eliminarlo, en este punto tendremos 2 subárboles separados flotando en el aire entonces para deshacer esto se debe hacer una biselación ya sea del valor más alto del subárbol izquierdo o el valor menor del subárbol derecho. 

Biselación: 

La biselación es el uso de rotaciones constantemente hasta llegar al nodo raíz, existen diferentes tipos de rotaciones: 

Rotación simple derecha: Esta rotación se hace de la siguiente forma: se tomara como ejemplo que el nodo que se le hará la biselación será el nodo x y el nodo que esta delante de x será p, entonces al nodo x se le hará una rotación simple a la derecha, al nodo p que esta delante de x también se le moverá a la derecha, si el nodo x tiene un hijo derecho este pasaría a ser hijo izquierdo del nodo p. 

Rotación simple izquierda: Esta rotación se hace de la siguiente forma: se tomara como ejemplo que el nodo que se le hará la biselación será el nodo x y el nodo que esta delante de x será p, entonces al nodo x se le hará una rotación simple a la izquierda, al nodo p que esta delante de x también se le moverá a la izquierda, si el nodo x tiene un hijo izquierdo este pasaría a ser hijo derecho del nodo p. 

Rotación doble derecha: Esta rotación se realiza exactamente igual que la rotación simple derecha con la única diferencia de que se debe de realizar 2 veces. 

Rotación doble izquierda: Esta rotación se realiza exactamente igual que la rotación simple izquierda con la única diferencia de que se debe de realizar 2 veces. 

Rotación simple derecha izquierda: Esta rotación se realiza de la siguiente forma se hace la rotación simple derecha y seguidamente se hace la rotación simple izquierda. 

Rotación simple izquierda derecha: Esta rotación se realiza de la siguiente forma se hace la rotación simple izquierda y seguidamente se hace la rotación simple derecha. 

Referencias