Splay Trees
Los splay trees son árboles binarios de búsqueda que tienen un método distinto de realizar las operaciones, el cual garantiza un costo amortizado de por operación sin necesidad de almacenar información de balanceo como los árboles AVL o Red-Black. Más aún, una secuencia de accesos a los nodos con distintas probabilidades entrega un costo amortizado de , donde es la entropía de esas probabilidades.
Como la estructura anterior, en el splay tree incluso las operaciones de lectura modifican el árbol. Sus respuestas no cambian, pero se hacen más eficientes gracias a las modificaciones.
📄️ Operaciones
La idea principal del splay tree es que el nodo que acaba de accederse debe
📄️ Análisis
Note que todas las operaciones del árbol tienen un costo proporcional a la
📄️ Búsquedas con distintas probabilidades de acceso
El mayor interés de los splay trees es que se acercan a los árboles óptimos