Se recomienda consultar la siguiente publicación como requisito previo para esta publicación.
Árbol de juego | Conjunto 1 (Buscar)
Como se discutió en la publicación anterior , el árbol Splay es una estructura de datos autoequilibrada donde la última clave a la que se accedió siempre está en la raíz. La operación de inserción es similar a la inserción del árbol de búsqueda binaria con pasos adicionales para asegurarse de que la clave recién insertada se convierta en la nueva raíz.
Los siguientes son diferentes casos para insertar una clave k en el árbol de distribución.
1) Root is NULL: simplemente asignamos un nuevo Node y lo devolvemos como root.
2) Pulse la tecla dada k. Si k ya está presente, entonces se convierte en la nueva raíz. Si no está presente, el último Node hoja al que se accedió se convierte en la nueva raíz.
3)Si la clave de la nueva raíz es la misma que k, no haga nada ya que k ya está presente.
4) De lo contrario, asigne memoria para el nuevo Node y compare la clave de raíz con k.
……. 4.a) Si k es menor que la clave de la raíz, haga que la raíz sea el hijo derecho del nuevo Node, copie el hijo izquierdo de la raíz como hijo izquierdo del nuevo Node y haga que el hijo izquierdo de la raíz sea NULL.
……. 4.b) Si k es mayor que la clave de la raíz, haga que la raíz sea el hijo izquierdo del nuevo Node, copie el hijo derecho de la raíz como hijo derecho del nuevo Node y haga que el hijo derecho de la raíz sea NULL.
5) Devuelve el nuevo Node como nueva raíz del árbol.
Ejemplo:
100 [20] 25
/ \ \ / \
50 200 50 20 50
/ insert(25) / \ insert(25) / \
40 ======> 30 100 ========> 30 100
/ 1. Splay(25) \ \ 2. insert 25 \ \
30 40 200 40 200
/
[20]
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;
// Zig-Zag (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);
}
}
// Function to insert a new key k
// in splay tree with given root
node *insert(node *root, int k)
{
// Simple Case: If tree is empty
if (root == NULL) return newNode(k);
// Bring the closest leaf node to root
root = splay(root, k);
// If key is already present, then return
if (root->key == k) return root;
// Otherwise allocate memory for new node
node *newnode = newNode(k);
// If root's key is greater, make
// root as right child of newnode
// and copy the left child of root to newnode
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
// If root's key is smaller, make
// root as left child of newnode
// and copy the right child of root to newnode
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; // newnode becomes new root
}
// 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 = insert(root, 25);
cout<<"Preorder traversal of the modified Splay tree is \n";
preOrder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
// This code is adopted from http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html
#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;
// Zig-Zag (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);
}
}
// Function to insert a new key k in splay tree with given root
struct node *insert(struct node *root, int k)
{
// Simple Case: If tree is empty
if (root == NULL) return newNode(k);
// Bring the closest leaf node to root
root = splay(root, k);
// If key is already present, then return
if (root->key == k) return root;
// Otherwise allocate memory for new node
struct node *newnode = newNode(k);
// If root's key is greater, make root as right child
// of newnode and copy the left child of root to newnode
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
// If root's key is smaller, make root as left child
// of newnode and copy the right child of root to newnode
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; // newnode becomes new root
}
// 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 = insert(root, 25);
printf("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
return 0;
}
Java
import java.util.*;
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;
// Zig-Zag (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);
}
}
// Function to insert a new key k
// in splay tree with given root
static node insert(node root, int k)
{
// Simple Case: If tree is empty
if (root == null) return newNode(k);
// Bring the closest leaf node to root
root = splay(root, k);
// If key is already present, then return
if (root.key == k) return root;
// Otherwise allocate memory for new node
node newnode = newNode(k);
// If root's key is greater, make
// root as right child of newnode
// and copy the left child of root to newnode
if (root.key > k)
{
newnode.right = root;
newnode.left = root.left;
root.left = null;
}
// If root's key is smaller, make
// root as left child of newnode
// and copy the right child of root to newnode
else
{
newnode.left = root;
newnode.right = root.right;
root.right = null;
}
return newnode; // newnode becomes new root
}
// 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 = insert(root, 25);
System.out.print("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
}
}
// This code is contributed by Rajput-Ji
C#
using System;
public class node
{
public int key;
public node left, right;
}
public class GFG{
/* 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;
// Zig-Zag (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);
}
}
// Function to insert a new key k
// in splay tree with given root
static node insert(node root, int k)
{
// Simple Case: If tree is empty
if (root == null) return newNode(k);
// Bring the closest leaf node to root
root = splay(root, k);
// If key is already present, then return
if (root.key == k) return root;
// Otherwise allocate memory for new node
node newnode = newNode(k);
// If root's key is greater, make
// root as right child of newnode
// and copy the left child of root to newnode
if (root.key > k)
{
newnode.right = root;
newnode.left = root.left;
root.left = null;
}
// If root's key is smaller, make
// root as left child of newnode
// and copy the right child of root to newnode
else
{
newnode.left = root;
newnode.right = root.right;
root.right = null;
}
return newnode; // newnode becomes new root
}
// 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*/
static public void 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 = insert(root, 25);
Console.Write("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
}
}
// This code is contributed by patel2127.
Javascript
<script>
// An AVL tree node
class Node {
constructor(val) {
this.key = val;
this.left = null;
this.right = null;
}
}
/*
Helper function that allocates a new
node with the given key and null left
and right pointers.
*/
function newNode(key) {
var 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.
function rightRotate( x) {
var 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) {
var 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;
// Zig-Zag (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);
}
}
// Function to insert a new key k
// in splay tree with given root
function insert( root , k) {
// Simple Case: If tree is empty
if (root == null)
return newNode(k);
// Bring the closest leaf node to root
root = splay(root, k);
// If key is already present, then return
if (root.key == k)
return root;
// Otherwise allocate memory for new node
var newnode = newNode(k);
// If root's key is greater, make
// root as right child of newnode
// and copy the left child of root to newnode
if (root.key > k) {
newnode.right = root;
newnode.left = root.left;
root.left = null;
}
// If root's key is smaller, make
// root as left child of newnode
// and copy the right child of root to newnode
else {
newnode.left = root;
newnode.right = root.right;
root.right = null;
}
return newnode; // newnode becomes new root
}
// 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 */
var 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 = insert(root, 25);
document.write(
"Preorder traversal of the modified Splay tree is <br/>"
);
preOrder(root);
// This code contributed by umadevi9616
</script>
Producción:
Preorder traversal of the modified Splay tree is 25 20 50 30 40 100 200
Este artículo ha sido compilado por Abhay Rathi . 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