La complejidad de tiempo del peor de los casos de las operaciones del árbol de búsqueda binaria (BST) como buscar, eliminar, insertar es O(n). El peor caso ocurre cuando el árbol está sesgado. Podemos obtener la complejidad de tiempo del peor de los casos como O (Logn) con AVL y Red-Black Trees.
¿Podemos hacerlo mejor que los árboles AVL o Red-Black en situaciones prácticas?
Al igual que AVL y Red-Black Trees, Splay Tree también es BST autoequilibrante. La idea principal de splay tree es llevar el elemento al que se accedió recientemente a la raíz del árbol, esto hace que el elemento buscado recientemente sea accesible en tiempo O(1) si se vuelve a acceder. La idea es usar la localidad de referencia (En una aplicación típica, el 80% de los accesos son al 20% de los artículos). Imagine una situación en la que tenemos millones o miles de millones de claves y solo se accede con frecuencia a algunas de ellas, lo que es muy probable en muchas aplicaciones prácticas.
Todas las operaciones de árbol splay se ejecutan en tiempo O (log n) en promedio, donde n es el número de entradas en el árbol. Cualquier operación individual puede tomar tiempo Theta(n) en el peor de los casos.
Operación de búsqueda
La operación de búsqueda en el árbol Splay realiza la búsqueda BST estándar, además de buscar, también splays (mover un Node a la raíz). Si la búsqueda tiene éxito, el Node encontrado se abre y se convierte en la nueva raíz. De lo contrario, el último Node al que se accedió antes de llegar a NULL se muestra y se convierte en la nueva raíz.
Existen los siguientes casos para el Node al que se accede.
1) El Node es root Simplemente devolvemos el root, no hagas nada más ya que el Node accedido ya es root.
2) Zig: el Node es hijo de la raíz (el Node no tiene abuelo). El Node es un hijo izquierdo de la raíz (hacemos una rotación a la derecha) o el Node es un hijo derecho de su padre (hacemos una rotación a la izquierda).
T1, T2 y T3 son subárboles del árbol con raíz y (en el lado izquierdo) o x (en el lado derecho)
y x
/ \ Zig (Right Rotation) / \
x T3 – - – - – - – - - -> T1 y
/ \ < - - - - - - - - - / \
T1 T2 Zag (Left Rotation) T2 T3
3) El Node tiene padre y abuelo . Puede haber subcasos siguientes.
…….. 3.a) Zig-Zig y Zag-Zag El Node es el hijo izquierdo del padre y el padre también es el hijo izquierdo del abuelo (Dos rotaciones a la derecha) O el Node es el hijo derecho de su padre y el padre también es el hijo derecho de abuelo (Dos Rotaciones a la Izquierda).
Zig-Zig (Left Left Case):
G P X
/ \ / \ / \
P T4 rightRotate(G) X G rightRotate(P) T1 P
/ \ ============> / \ / \ ============> / \
X T3 T1 T2 T3 T4 T2 G
/ \ / \
T1 T2 T3 T4
Zag-Zag (Right Right Case):
G P X
/ \ / \ / \
T1 P leftRotate(G) G X leftRotate(P) P T4
/ \ ============> / \ / \ ============> / \
T2 X T1 T2 T3 T4 G T3
/ \ / \
T3 T4 T1 T2
…….. 3.b) Zig-Zag y Zag-Zig El Node es el hijo derecho del padre y el padre es el hijo izquierdo del abuelo (rotación a la izquierda seguida de rotación a la derecha) O el Node es el hijo izquierdo de su padre y el padre es el hijo derecho del abuelo (rotación a la derecha seguida de rotación a la izquierda).
Zag-Zig (Left Right Case):
G G X
/ \ / \ / \
P T4 leftRotate(P) X T4 rightRotate(G) P G
/ \ ============> / \ ============> / \ / \
T1 X P T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
Zig-Zag (Right Left Case):
G G X
/ \ / \ / \
T1 P rightRotate(P) T1 X leftRotate(G) G P
/ \ =============> / \ ============> / \ / \
X T4 T2 P T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Ejemplo:
100 100 [20]
/ \ / \ \
50 200 50 200 50
/ search(20) / search(20) / \
40 ======> [20] ========> 30 100
/ 1. Zig-Zig \ 2. Zig-Zig \ \
30 at 40 30 at 100 40 200
/ \
[20] 40
Lo importante a tener en cuenta es que la operación de búsqueda o distribución no solo trae la clave buscada a la raíz, sino que también equilibra el BST. Por ejemplo, en el caso anterior, la altura de BST se reduce en 1.
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
// An AVL tree node
class node
{
public:
int key;
node *left, *right;
};
/* Helper function that allocates
a new node with the given key and
NULL left and right pointers. */
node* newNode(int key)
{
node* Node = new node();
Node->key = key;
Node->left = Node->right = NULL;
return (Node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
node *rightRotate(node *x)
{
node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
node *leftRotate(node *x)
{
node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// This function brings the key at
// root if key is present in tree.
// If key is not present, then it
// brings the last accessed item at
// root. This function modifies the
// tree and returns the new root
node *splay(node *root, int key)
{
// Base cases: root is NULL or
// key is present at root
if (root == NULL || root->key == key)
return root;
// Key lies in left subtree
if (root->key > key)
{
// Key is not in tree, we are done
if (root->left == NULL) return root;
// Zig-Zig (Left Left)
if (root->left->key > key)
{
// First recursively bring the
// key as root of left-left
root->left->left = splay(root->left->left, key);
// Do first rotation for root,
// second rotation is done after else
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (Left Right)
{
// First recursively bring
// the key as root of left-right
root->left->right = splay(root->left->right, key);
// Do first rotation for root->left
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
// Do second rotation for root
return (root->left == NULL)? root: rightRotate(root);
}
else // Key lies in right subtree
{
// Key is not in tree, we are done
if (root->right == NULL) return root;
// Zag-Zig (Right Left)
if (root->right->key > key)
{
// Bring the key as root of right-left
root->right->left = splay(root->right->left, key);
// Do first rotation for root->right
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key)// Zag-Zag (Right Right)
{
// Bring the key as root of
// right-right and do first rotation
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
// Do second rotation for root
return (root->right == NULL)? root: leftRotate(root);
}
}
// The search function for Splay tree.
// Note that this function returns the
// new root of Splay Tree. If key is
// present in tree then, it is moved to root.
node *search(node *root, int key)
{
return splay(root, key);
}
// A utility function to print
// preorder traversal of the tree.
// The function also prints height of every node
void preOrder(node *root)
{
if (root != NULL)
{
cout<<root->key<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
/* Driver code*/
int main()
{
node *root = newNode(100);
root->left = newNode(50);
root->right = newNode(200);
root->left->left = newNode(40);
root->left->left->left = newNode(30);
root->left->left->left->left = newNode(20);
root = search(root, 20);
cout << "Preorder traversal of the modified Splay tree is \n";
preOrder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
// The code is adopted from http://goo.gl/SDH9hH
#include<stdio.h>
#include<stdlib.h>
// An AVL tree node
struct node
{
int key;
struct node *left, *right;
};
/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct node* newNode(int key)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *x)
{
struct node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// This function brings the key at root if key is present in tree.
// If key is not present, then it brings the last accessed item at
// root. This function modifies the tree and returns the new root
struct node *splay(struct node *root, int key)
{
// Base cases: root is NULL or key is present at root
if (root == NULL || root->key == key)
return root;
// Key lies in left subtree
if (root->key > key)
{
// Key is not in tree, we are done
if (root->left == NULL) return root;
// Zig-Zig (Left Left)
if (root->left->key > key)
{
// First recursively bring the key as root of left-left
root->left->left = splay(root->left->left, key);
// Do first rotation for root, second rotation is done after else
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (Left Right)
{
// First recursively bring the key as root of left-right
root->left->right = splay(root->left->right, key);
// Do first rotation for root->left
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
// Do second rotation for root
return (root->left == NULL)? root: rightRotate(root);
}
else // Key lies in right subtree
{
// Key is not in tree, we are done
if (root->right == NULL) return root;
// Zag-Zig (Right Left)
if (root->right->key > key)
{
// Bring the key as root of right-left
root->right->left = splay(root->right->left, key);
// Do first rotation for root->right
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key)// Zag-Zag (Right Right)
{
// Bring the key as root of right-right and do first rotation
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
// Do second rotation for root
return (root->right == NULL)? root: leftRotate(root);
}
}
// The search function for Splay tree. Note that this function
// returns the new root of Splay Tree. If key is present in tree
// then, it is moved to root.
struct node *search(struct node *root, int key)
{
return splay(root, key);
}
// A utility function to print preorder traversal of the tree.
// The function also prints height of every node
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
/* Driver program to test above function*/
int main()
{
struct node *root = newNode(100);
root->left = newNode(50);
root->right = newNode(200);
root->left->left = newNode(40);
root->left->left->left = newNode(30);
root->left->left->left->left = newNode(20);
root = search(root, 20);
printf("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
return 0;
}
Java
// Java implementation for above approach
class GFG
{
// An AVL tree node
static class node
{
int key;
node left, right;
};
/* Helper function that allocates
a new node with the given key and
null left and right pointers. */
static node newNode(int key)
{
node Node = new node();
Node.key = key;
Node.left = Node.right = null;
return (Node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
static node rightRotate(node x)
{
node y = x.left;
x.left = y.right;
y.right = x;
return y;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
static node leftRotate(node x)
{
node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
// This function brings the key at
// root if key is present in tree.
// If key is not present, then it
// brings the last accessed item at
// root. This function modifies the
// tree and returns the new root
static node splay(node root, int key)
{
// Base cases: root is null or
// key is present at root
if (root == null || root.key == key)
return root;
// Key lies in left subtree
if (root.key > key)
{
// Key is not in tree, we are done
if (root.left == null) return root;
// Zig-Zig (Left Left)
if (root.left.key > key)
{
// First recursively bring the
// key as root of left-left
root.left.left = splay(root.left.left, key);
// Do first rotation for root,
// second rotation is done after else
root = rightRotate(root);
}
else if (root.left.key < key) // Zig-Zag (Left Right)
{
// First recursively bring
// the key as root of left-right
root.left.right = splay(root.left.right, key);
// Do first rotation for root.left
if (root.left.right != null)
root.left = leftRotate(root.left);
}
// Do second rotation for root
return (root.left == null) ?
root : rightRotate(root);
}
else // Key lies in right subtree
{
// Key is not in tree, we are done
if (root.right == null) return root;
// Zag-Zig (Right Left)
if (root.right.key > key)
{
// Bring the key as root of right-left
root.right.left = splay(root.right.left, key);
// Do first rotation for root.right
if (root.right.left != null)
root.right = rightRotate(root.right);
}
else if (root.right.key < key)// Zag-Zag (Right Right)
{
// Bring the key as root of
// right-right and do first rotation
root.right.right = splay(root.right.right, key);
root = leftRotate(root);
}
// Do second rotation for root
return (root.right == null) ?
root : leftRotate(root);
}
}
// The search function for Splay tree.
// Note that this function returns the
// new root of Splay Tree. If key is
// present in tree then, it is moved to root.
static node search(node root, int key)
{
return splay(root, key);
}
// A utility function to print
// preorder traversal of the tree.
// The function also prints height of every node
static void preOrder(node root)
{
if (root != null)
{
System.out.print(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// Driver code
public static void main(String[] args)
{
node root = newNode(100);
root.left = newNode(50);
root.right = newNode(200);
root.left.left = newNode(40);
root.left.left.left = newNode(30);
root.left.left.left.left = newNode(20);
root = search(root, 20);
System.out.print("Preorder traversal of the" +
" modified Splay tree is \n");
preOrder(root);
}
}
// This code is contributed by 29AjayKumar
C#
// C# implementation for above approach
using System;
class GFG
{
// An AVL tree node
public class node
{
public int key;
public node left, right;
};
/* Helper function that allocates
a new node with the given key and
null left and right pointers. */
static node newNode(int key)
{
node Node = new node();
Node.key = key;
Node.left = Node.right = null;
return (Node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
static node rightRotate(node x)
{
node y = x.left;
x.left = y.right;
y.right = x;
return y;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
static node leftRotate(node x)
{
node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
// This function brings the key at
// root if key is present in tree.
// If key is not present, then it
// brings the last accessed item at
// root. This function modifies the
// tree and returns the new root
static node splay(node root, int key)
{
// Base cases: root is null or
// key is present at root
if (root == null || root.key == key)
return root;
// Key lies in left subtree
if (root.key > key)
{
// Key is not in tree, we are done
if (root.left == null) return root;
// Zig-Zig (Left Left)
if (root.left.key > key)
{
// First recursively bring the
// key as root of left-left
root.left.left = splay(root.left.left, key);
// Do first rotation for root,
// second rotation is done after else
root = rightRotate(root);
}
else if (root.left.key < key) // Zig-Zag (Left Right)
{
// First recursively bring
// the key as root of left-right
root.left.right = splay(root.left.right, key);
// Do first rotation for root.left
if (root.left.right != null)
root.left = leftRotate(root.left);
}
// Do second rotation for root
return (root.left == null) ?
root : rightRotate(root);
}
else // Key lies in right subtree
{
// Key is not in tree, we are done
if (root.right == null) return root;
// Zag-Zig (Right Left)
if (root.right.key > key)
{
// Bring the key as root of right-left
root.right.left = splay(root.right.left, key);
// Do first rotation for root.right
if (root.right.left != null)
root.right = rightRotate(root.right);
}
else if (root.right.key < key)// Zag-Zag (Right Right)
{
// Bring the key as root of
// right-right and do first rotation
root.right.right = splay(root.right.right, key);
root = leftRotate(root);
}
// Do second rotation for root
return (root.right == null) ?
root : leftRotate(root);
}
}
// The search function for Splay tree.
// Note that this function returns the
// new root of Splay Tree. If key is
// present in tree then, it is moved to root.
static node search(node root, int key)
{
return splay(root, key);
}
// A utility function to print
// preorder traversal of the tree.
// The function also prints height of every node
static void preOrder(node root)
{
if (root != null)
{
Console.Write(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// Driver code
public static void Main(String[] args)
{
node root = newNode(100);
root.left = newNode(50);
root.right = newNode(200);
root.left.left = newNode(40);
root.left.left.left = newNode(30);
root.left.left.left.left = newNode(20);
root = search(root, 20);
Console.Write("Preorder traversal of the" +
" modified Splay tree is \n");
preOrder(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation for above approach
// An AVL tree node
class Node
{
/* Helper function that allocates
a new node with the given key and
null left and right pointers. */
constructor(key)
{
this.key = key;
this.left = this.right = null;
}
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
function rightRotate(x)
{
let y = x.left;
x.left = y.right;
y.right = x;
return y;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
function leftRotate(x)
{
let y = x.right;
x.right = y.left;
y.left = x;
return y;
}
// This function brings the key at
// root if key is present in tree.
// If key is not present, then it
// brings the last accessed item at
// root. This function modifies the
// tree and returns the new root
function splay(root,key)
{
// Base cases: root is null or
// key is present at root
if (root == null || root.key == key)
return root;
// Key lies in left subtree
if (root.key > key)
{
// Key is not in tree, we are done
if (root.left == null) return root;
// Zig-Zig (Left Left)
if (root.left.key > key)
{
// First recursively bring the
// key as root of left-left
root.left.left = splay(root.left.left, key);
// Do first rotation for root,
// second rotation is done after else
root = rightRotate(root);
}
else if (root.left.key < key) // Zig-Zag (Left Right)
{
// First recursively bring
// the key as root of left-right
root.left.right = splay(root.left.right, key);
// Do first rotation for root.left
if (root.left.right != null)
root.left = leftRotate(root.left);
}
// Do second rotation for root
return (root.left == null) ?
root : rightRotate(root);
}
else // Key lies in right subtree
{
// Key is not in tree, we are done
if (root.right == null) return root;
// Zag-Zig (Right Left)
if (root.right.key > key)
{
// Bring the key as root of right-left
root.right.left = splay(root.right.left, key);
// Do first rotation for root.right
if (root.right.left != null)
root.right = rightRotate(root.right);
}
else if (root.right.key < key)// Zag-Zag (Right Right)
{
// Bring the key as root of
// right-right and do first rotation
root.right.right = splay(root.right.right, key);
root = leftRotate(root);
}
// Do second rotation for root
return (root.right == null) ?
root : leftRotate(root);
}
}
// The search function for Splay tree.
// Note that this function returns the
// new root of Splay Tree. If key is
// present in tree then, it is moved to root.
function search(root,key)
{
return splay(root, key);
}
// A utility function to print
// preorder traversal of the tree.
// The function also prints height of every node
function preOrder(root)
{
if (root != null)
{
document.write(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// Driver code
let root = new Node(100);
root.left = new Node(50);
root.right = new Node(200);
root.left.left = new Node(40);
root.left.left.left = new Node(30);
root.left.left.left.left = new Node(20);
root = search(root, 20);
document.write("Preorder traversal of the" +
" modified Splay tree is <br>");
preOrder(root);
// This code is contributed by rag2127
</script>
Producción:
Preorder traversal of the modified Splay tree is 20 50 30 40 100 200
Resumen
1) Los árboles Splay tienen excelentes propiedades de localidad. Los elementos de acceso frecuente son fáciles de encontrar. Los artículos poco frecuentes están fuera de lugar.
2) Todas las operaciones del árbol de distribución toman tiempo O (Iniciar sesión) en promedio. Se puede demostrar rigurosamente que los árboles de distribución se ejecutan en un tiempo promedio de O (log n) por operación, en cualquier secuencia de operaciones (suponiendo que empecemos desde un árbol vacío)
3) Los árboles de distribución son más simples en comparación con AVL y los árboles rojo-negro como ningún extra El campo es obligatorio en cada Node del árbol.
4) A diferencia del árbol AVL , un árbol de distribución puede cambiar incluso con operaciones de solo lectura como la búsqueda.
Aplicaciones de Splay Trees
Los árboles dispersos se han convertido en la estructura de datos básica más utilizada inventada en los últimos 30 años, porque son el tipo de árbol de búsqueda equilibrado más rápido para muchas aplicaciones.
Los árboles de distribución se utilizan en Windows NT (en la memoria virtual, la red y el código del sistema de archivos), el compilador gcc y la biblioteca GNU C++, el editor de strings sed, los enrutadores de red para sistemas, la implementación más popular de Unix malloc, el kernel cargable de Linux módulos, y en mucho otro software (Fuente: http://www.cs.berkeley.edu/~jrs/61b/lec/36 )
Ver Splay Tree | Establecer 2 (Insertar) para la inserción del árbol de distribución.
Ventajas de los árboles Splay:
- Útil para implementar cachés y algoritmos de recolección de basura.
- Requiere menos espacio ya que no se requiere información de saldo.
- Los árboles de distribución proporcionan un buen rendimiento con Nodes que contienen claves idénticas.
Desventajas de los árboles Splay:
- La altura de un árbol de distribución puede ser lineal cuando se accede a los elementos en orden no decreciente.
- El rendimiento de un árbol splay será peor que el de un árbol de búsqueda binaria simple equilibrado en caso de acceso uniforme.
Referencias:
http://www.cs.berkeley.edu/~jrs/61b/lec/36
http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html
http:/ /courses.cs.washington.edu/courses/cse326/01au/lectures/SplayTrees.ppt
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA