El árbol Splay es una estructura de datos de árbol de búsqueda binaria autoajustable, lo que significa que la estructura del árbol se ajusta dinámicamente en función de los elementos accedidos o insertados. En otras palabras, el árbol se reorganiza automáticamente para que los elementos insertados o a los que se accede con frecuencia se acerquen al nodo raíz.

1. El árbol splay fue introducido por primera vez por Daniel Dominic Sleator y Robert Endre Tarjan en 1985. Tiene una implementación simple y eficiente que le permite realizar operaciones de búsqueda, inserción y eliminación en una complejidad de tiempo amortizado O (log n), donde n es el número de elementos del árbol.
2. La idea básica detrás de los árboles de expansión es llevar el elemento insertado o accedido más recientemente a la raíz del árbol realizando una secuencia de rotaciones de árbol, llamada expansión. La expansión es un proceso de reestructuración del árbol haciendo que el elemento insertado o accedido más recientemente sea la nueva raíz y acercando gradualmente los nodos restantes a la raíz.
3. Los árboles de expansión son muy eficientes en la práctica debido a su naturaleza autoajustable, lo que reduce el tiempo total de acceso a los elementos a los que se accede con frecuencia. Esto los convierte en una buena opción para aplicaciones que requieren estructuras de datos rápidas y dinámicas, como sistemas de almacenamiento en caché, compresión de datos y algoritmos de enrutamiento de red.
4. Sin embargo, la principal desventaja de los árboles splay es que no garantizan una estructura de árbol equilibrada, lo que puede provocar una degradación del rendimiento en los peores escenarios. Además, los árboles de dispersión no son adecuados para aplicaciones que requieren un rendimiento garantizado en el peor de los casos, como sistemas en tiempo real o sistemas críticos para la seguridad.

En general, los árboles de distribución son una estructura de datos potente y versátil que ofrece un acceso rápido y eficiente a elementos insertados o a los que se accede con frecuencia. Se utilizan ampliamente en diversas aplicaciones y proporcionan un excelente equilibrio entre rendimiento y simplicidad.

Un árbol de distribución es un árbol de búsqueda binario autoequilibrado, diseñado para un acceso eficiente a elementos de datos en función de sus valores clave.

• La característica clave de un árbol splay es que cada vez que se accede a un elemento, se mueve a la raíz del árbol, creando una estructura más equilibrada para accesos posteriores.
• Los árboles splay se caracterizan por el uso de rotaciones, que son transformaciones locales del árbol que cambian su forma pero preservan el orden de los elementos.
• Las rotaciones se utilizan para llevar el elemento al que se accede a la raíz del árbol y también para reequilibrar el árbol si se desequilibra después de múltiples accesos.

Operaciones en un árbol splay:

• Inserción: Para insertar un nuevo elemento en el árbol, comience realizando una inserción normal en el árbol de búsqueda binaria. Luego, aplique rotaciones para llevar el elemento recién insertado a la raíz del árbol.
• Supresión : Para eliminar un elemento del árbol, primero ubíquelo utilizando una búsqueda de árbol binario. Luego, si el elemento no tiene hijos, simplemente elimínelo. Si tiene un hijo, promueva ese hijo a su posición en el árbol. Si tiene dos hijos, busque el sucesor del elemento (el elemento más pequeño en su subárbol derecho), intercambie su clave con el elemento que se va a eliminar y, en su lugar, elimine el sucesor.
• Buscar : Para buscar un elemento en el árbol, comience realizando una búsqueda binaria en el árbol. Si se encuentra el elemento, aplique rotaciones para llevarlo a la raíz del árbol. Si no se encuentra, aplique rotaciones al último nodo visitado en la búsqueda, que se convierte en la nueva raíz.
• Rotación : Las rotaciones utilizadas en un árbol de expansión son una rotación en Zig o en Zig-Zig. Se utiliza una rotación en Zig para llevar un nodo a la raíz, mientras que una rotación en Zig-Zig se utiliza para equilibrar el árbol después de múltiples accesos a elementos en el mismo subárbol.

Aquí hay una explicación paso a paso de las operaciones de rotación:

• Rotación en zigzag : Si un nodo tiene un hijo derecho, realice una rotación hacia la derecha para llevarlo a la raíz. Si tiene un hijo izquierdo, realice una rotación hacia la izquierda.
• Rotación Zig-Zig: Si un nodo tiene un nieto que también es hijo derecho o izquierdo de su hijo, realice una doble rotación para equilibrar el árbol. Por ejemplo, si el nodo tiene un hijo derecho y el hijo derecho tiene un hijo izquierdo, realice una rotación de derecha a izquierda. Si el nodo tiene un hijo izquierdo y el hijo izquierdo tiene un hijo derecho, realice una rotación de izquierda a derecha.
• Nota: Los detalles de implementación específicos, incluidas las rotaciones exactas utilizadas, pueden variar según la forma exacta del árbol de distribución.

Rotaciones en el árbol de expansión

• Rotación en zigzag
• Rotación en zag
• Zig – Rotación en Zig
• Zag – Rotación Zag
• Rotación Zig-Zag
• Zag – Rotación en zig

1) Rotación en Zig:

La rotación en zig en los árboles extendidos funciona de manera similar a la rotación única hacia la derecha en las rotaciones del árbol AVL. Esta rotación da como resultado que los nodos se muevan una posición hacia la derecha desde su ubicación actual. Por ejemplo, considere el siguiente escenario:

Rotación en zig (rotación única)

2) Rotación en Zag:

La rotación Zag en los árboles extendidos funciona de manera similar a la rotación única hacia la izquierda en las rotaciones del árbol AVL. Durante esta rotación, los nodos se desplazan una posición hacia la izquierda desde su ubicación actual. Por ejemplo, considere la siguiente ilustración:

bucle mecanografiado para cada uno

Rotación Zag (Rotación única a la izquierda)

3) Rotación Zig-Zig:

La rotación Zig-Zig en los árboles extendidos es una rotación en zig doble. Esta rotación da como resultado que los nodos se desplacen dos posiciones hacia la derecha desde su ubicación actual. Eche un vistazo al siguiente ejemplo para una mejor comprensión:

Rotación Zig-Zig (Doble Rotación a la Derecha)

4) Rotación Zag-Zag:

En los árboles extendidos, la rotación Zag-Zag es una rotación de doble zag. Esta rotación hace que los nodos se muevan dos posiciones hacia la izquierda desde su posición actual. Por ejemplo:

Rotación Zag-Zag (Doble rotación a la izquierda)

5) Rotación en zig-zag:

La rotación en zig-zag en los árboles extendidos es una combinación de una rotación en zig seguida de una rotación en zag. Como resultado de esta rotación, los nodos se desplazan una posición hacia la derecha y luego una posición hacia la izquierda desde su ubicación actual. La siguiente ilustración proporciona una representación visual de este concepto:

Rotación en zig-zag

valor de cadena de

6) Rotación Zag-Zig:

La rotación Zag-Zig en los árboles extendidos es una serie de rotaciones en zag seguidas de una rotación en zig. Esto da como resultado que los nodos se muevan una posición hacia la izquierda, seguido de un desplazamiento una posición hacia la derecha desde su ubicación actual. La siguiente ilustración ofrece una representación visual de este concepto:

Rotación Zag-Zig

A continuación se muestra el código C++ para implementar rotaciones en el árbol Splay:

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->clave = clave;  nodo->izquierda = nodo->derecha = nullptr;  nodo de retorno; } Nodo* rotación derecha(Nodo* x) { Nodo* y = x->izquierda;  x->izquierda = y->derecha;  y->derecha = x;  devolver y; } Nodo* leftRotate(Nodo* x) { Nodo* y = x->derecha;  x->derecha = y->izquierda;  y->izquierda = x;  devolver y; } Nodo* splay(Nodo* raíz, int clave) { if (raíz == nullptr || raíz->clave == clave) return raíz;  if (raíz->clave> clave) { if (raíz->izquierda == nullptr) return raíz;  if (raíz->izquierda->tecla> tecla) { raíz->izquierda->izquierda = splay(raíz->izquierda->izquierda, clave);  raíz = rotación derecha (raíz);  } más si (raíz->izquierda->tecla< key) {  root->izquierda->derecha = splay(root->izquierda->derecha, clave);  if (raíz->izquierda->derecha! = nullptr) raíz->izquierda = leftRotate(raíz->izquierda);  } retorno (raíz->izquierda == nullptr)? raíz: rotación derecha (raíz);  } else { if (root->right == nullptr) return root;  if (raíz->derecha->tecla> tecla) { raíz->derecha->izquierda = splay(raíz->derecha->izquierda, clave);  if (raíz->derecha->izquierda!= nullptr) raíz->derecha = derechaRotar(raíz->derecha);  } más si (raíz->derecha->tecla< key) {  root->derecha->derecha = splay(raíz->derecha->derecha, clave);  raíz = rotación izquierda(raíz);  } return (raíz->derecha == nullptr)? raíz: rotación izquierda (raíz);  } } Nodo* insert(Nodo* raíz, int clave) { if (raíz == nullptr) return nuevoNodo(clave);  raíz = splay(raíz, clave);  si (raíz->clave == clave) devuelve raíz;  Nodo* nodo = nuevoNodo(clave);  if (raíz->clave> clave) { nodo->derecha = raíz;  nodo->izquierda = raíz->izquierda;  raíz->izquierda = nullptr;  } else { nodo->izquierda = raíz;  nodo->derecha = raíz->derecha;  raíz->derecha = nullptr;  } nodo de retorno; } void preOrder(Nodo* nodo) { if (nodo!= nullptr) { cout<< node->llave<< ' ';  preOrder(node->izquierda);  preOrder(nodo->derecha);  } } int main() { Nodo* raíz = nullptr;  raíz = insertar(raíz, 100);  raíz = insertar(raíz, 50);  raíz = insertar(raíz, 200);  raíz = insertar(raíz, 40);  raíz = insertar(raíz, 60);  corte<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>

// Java Program for the above approach class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key) {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x) {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x) {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key) {  if (root == null || root.key == key)  return root;  if (root.key>clave) { if (root.left == null) return raíz;  if (root.left.key> clave) { root.left.left = splay(root.left.left, clave);  raíz = rotación derecha (raíz);  } más si (root.left.key< key) {  root.left.right = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>clave) { raíz.derecha.izquierda = splay(raíz.derecha.izquierda, clave);  if (root.right.left! = nulo) root.right = rightRotate(root.right);  } más si (root.right.key< key) {  root.right.right = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root : leftRotate(root);  }  }  static Node insert(Node root, int key) {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>clave) { nodo.derecha = raíz;  nodo.izquierda = raíz.izquierda;  raíz.izquierda = nulo;  } else { nodo.izquierda = raíz;  nodo.derecha = raíz.derecha;  raíz.derecha = nulo;  } nodo de retorno;  } static void preOrder(Nodo nodo) { if (nodo!= null) { System.out.println();  System.out.print(nodo.key + ' ');  pedido anticipado (nodo.izquierda);  pedido anticipado (nodo.derecha);  } } public static void main(String[] args) { Raíz del nodo = nulo;  raíz = insertar(raíz, 100);  raíz = insertar(raíz, 50);  raíz = insertar(raíz, 200);  raíz = insertar(raíz, 40);  raíz = insertar(raíz, 60);  System.out.println('Recorrido previo al pedido del árbol Splay modificado:');  pedido anticipado (raíz);  } } // Este código es aportado por princekumaras>

class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>clave: si root.left es Ninguno: devuelve root si root.left.key> clave: root.left.left = splay(root.left.left, key) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>clave: root.right.left = splay(root.right.left, clave) if root.right.left: root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>clave: nodo.derecha = raíz nodo.izquierda = raíz.izquierda raíz.izquierda = Ninguno más: nodo.izquierda = raíz nodo.derecha = raíz.derecha raíz.derecha = Ninguno return nodo def pre_order(nodo): si nodo: imprimir (nodo.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': raíz = Ninguno raíz = insertar(raíz, 100) raíz = insertar(raíz , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Recorrido de preorden del árbol Splay modificado:') pre_order(root)>

// C# program for the above approach using System; class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key)  {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x)  {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x)  {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key)  {  if (root == null || root.key == key)  return root;  if (root.key>clave) { if (root.left == null) return raíz;  if (root.left.key> clave) { root.left.left = splay(root.left.left, clave);  raíz = rotación derecha (raíz);  } más si (root.left.key< key) {  root.left.right  = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root  : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>clave) { raíz.derecha.izquierda = splay(raíz.derecha.izquierda, clave);  if (root.right.left! = nulo) root.right = rightRotate(root.right);  } más si (root.right.key< key) {  root.right.right  = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root  : leftRotate(root);  }  }  static Node insert(Node root, int key)  {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>clave) { nodo.derecha = raíz;  nodo.izquierda = raíz.izquierda;  raíz.izquierda = nulo;  } else { nodo.izquierda = raíz;  nodo.derecha = raíz.derecha;  raíz.derecha = nulo;  } nodo de retorno;  } static void preOrder(Nodo nodo) { if (nodo!= null) { Console.Write(node.key + ' ');  pedido anticipado (nodo.izquierda);  pedido anticipado (nodo.derecha);  } } public static void Main(string[] args) { Raíz del nodo = null;  raíz = insertar(raíz, 100);  raíz = insertar(raíz, 50);  raíz = insertar(raíz, 200);  raíz = insertar(raíz, 40);  raíz = insertar(raíz, 60);  Console.WriteLine( 'Recorrido previo al pedido del árbol Splay modificado:');  pedido anticipado (raíz);  } } // Este código es aportado por el Príncipe Kumar>

// Javascript code addition  class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } class SplayTree {  static newNode(key) {  const node = new Node(key);  return node;  }  static rightRotate(x) {  const y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static leftRotate(x) {  const y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static splay(root, key) {  if (root == null || root.key == key) {  return root;  }  if (root.key>clave) { if (root.left == null) { return root;  } if (root.left.key> clave) { root.left.left = SplayTree.splay(root.left.left, clave);  raíz = SplayTree.rightRotate(raíz);  } más si (root.left.key< key) {  root.left.right = SplayTree.splay(root.left.right, key);  if (root.left.right != null) {  root.left = SplayTree.leftRotate(root.left);  }  }  return root.left == null ? root : SplayTree.rightRotate(root);  } else {  if (root.right == null) {  return root;  }  if (root.right.key>clave) { raíz.derecha.izquierda = SplayTree.splay(raíz.derecha.izquierda, clave);  if (root.right.left! = nulo) { root.right = SplayTree.rightRotate(root.right);  } } más si (root.right.key< key) {  root.right.right = SplayTree.splay(root.right.right, key);  root = SplayTree.leftRotate(root);  }  return root.right == null ? root : SplayTree.leftRotate(root);  }  }  static insert(root, key) {  if (root == null) {  return SplayTree.newNode(key);  }  root = SplayTree.splay(root, key);  if (root.key == key) {  return root;  }  const node = SplayTree.newNode(key);  if (root.key>clave) { nodo.derecha = raíz;  nodo.izquierda = raíz.izquierda;  raíz.izquierda = nulo;  } else { nodo.izquierda = raíz;  nodo.derecha = raíz.derecha;  raíz.derecha = nulo;  } nodo de retorno;  } pedido anticipado estático (nodo) { if (nodo! = nulo) { console.log(nodo.key + ' ');  SplayTree.preOrder(nodo.izquierda);  SplayTree.preOrder(nodo.derecha);  } } } let raíz = nulo; raíz = SplayTree.insert(raíz, 100); raíz = SplayTree.insert(raíz, 50); raíz = SplayTree.insert(raíz, 200); raíz = SplayTree.insert(raíz, 40); raíz = SplayTree.insert(raíz, 60); console.log('Recorrido previo al pedido del árbol Splay modificado:'); SplayTree.preOrder(raíz); // El código fue aportado por Nidhi goel.>

Preorder traversal of the modified Splay tree:>

Desventajas de la estructura de datos del árbol de distribución:

• Árboles desequilibrados: Los árboles extendidos pueden desequilibrarse y volverse ineficientes si el árbol se gira repetidamente en la misma dirección.
• Uso de memoria: Los árboles de distribución pueden utilizar mucha memoria en comparación con otras estructuras de datos porque cada nodo contiene información adicional.
• Complejidad: Los árboles de distribución pueden tener una gran complejidad temporal para operaciones básicas como la inserción y eliminación porque los árboles deben reorganizarse después de cada operación.
• Gastos generales de reorganización: La operación de separación necesaria en cada operación puede llevar mucho tiempo y generar grandes gastos generales.
• Casos de uso limitado : Los árboles de distribución no son adecuados para todas las estructuras de datos y tienen casos de uso limitados porque no manejan claves duplicadas de manera eficiente.

Aplicaciones del árbol splay:

• Almacenamiento en caché : Los árboles de distribución se pueden utilizar para implementar la gestión de la memoria caché, donde los elementos a los que se accede con más frecuencia se mueven a la parte superior del árbol para un acceso más rápido.
• Indexación de bases de datos : Los árboles de distribución se pueden utilizar para indexar bases de datos para una búsqueda y recuperación de datos más rápida.
• Sistemas de archivos : Los árboles de distribución se pueden utilizar para almacenar metadatos del sistema de archivos, como la tabla de asignación, la estructura de directorios y los atributos del archivo.
• Compresión de datos: Los árboles de distribución se pueden utilizar para comprimir datos identificando y codificando patrones repetidos.
• Procesamiento de textos : Los árboles de visualización se pueden utilizar en aplicaciones de procesamiento de texto, como los correctores ortográficos, donde las palabras se almacenan en un árbol de visualización para una búsqueda y recuperación rápidas.
• Algoritmos de gráficos: Los árboles de distribución se pueden utilizar para implementar algoritmos gráficos, como encontrar la ruta más corta en un gráfico ponderado.
• Juego en linea: Los árboles de distribución se pueden utilizar en juegos en línea para almacenar y administrar puntuaciones altas, tablas de clasificación y estadísticas de jugadores.

Claro, aquí hay algunas ventajas y desventajas de los árboles splay, así como algunos libros recomendados para aprender más sobre el tema:

Ventajas de los árboles extendidos:

Los árboles de distribución tienen una complejidad temporal amortizada de O (log n) para muchas operaciones, lo que los hace más rápidos que muchas otras estructuras de datos de árbol equilibrado en algunos casos.
Los árboles de expansión se ajustan automáticamente, lo que significa que se equilibran automáticamente a medida que se insertan y retiran elementos. Esto puede ayudar a evitar la degradación del rendimiento que puede ocurrir cuando un árbol se desequilibra.

búsqueda binaria

Desventajas de los árboles extendidos:

Los árboles de distribución pueden tener una complejidad temporal de O(n) en el peor de los casos para algunas operaciones, lo que los hace menos predecibles que otras estructuras de datos de árboles equilibrados, como los árboles AVL o los árboles rojo-negro.
Es posible que los árboles de distribución no sean adecuados para determinadas aplicaciones en las que se requiere un rendimiento predecible.

Libros recomendados sobre Splay Trees:

Estructuras de datos y análisis de algoritmos en Java por Mark Allen Weiss
Introducción a los algoritmos por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein
Estructuras de datos y algoritmos en C++ por Michael T. Goodrich y Roberto Tamassia

Conclusión:

En conclusión, Splay Trees es una estructura de datos de árbol de búsqueda binaria dinámica y autoequilibrada que proporciona una forma eficiente de buscar, insertar y eliminar elementos. Se diferencian de los árboles de búsqueda binarios equilibrados tradicionales, como AVL y los árboles Rojo-Negro, en que reorganizan el árbol después de cada operación para llevar el nodo al que se accedió recientemente a la raíz. Esto ayuda a reducir la altura del árbol y da como resultado operaciones más rápidas. Los Splay Trees son muy flexibles y se pueden adaptar a diversos casos de uso. Aunque pueden tener una mayor sobrecarga en términos de rotaciones, su simplicidad y versatilidad los convierten en herramientas útiles para resolver una amplia gama de problemas.