Hola, Khabrovites. Anticipándonos al inicio del curso "Algoritmos y estructuras de datos", invitamos a los futuros estudiantes ya todos a una lección abierta sobre el tema "Reservas de árboles de búsqueda binaria".
También compartimos una traducción útil tradicional.
: Splay-.
k Splay-.
1) NULL: .
2) Splay k. k , . , -, .
3) , k, , k .
4) k.
4.a) k , , NULL.
4.b) k , , NULL.
5) .
:
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]
++
#include <bits/stdc++.h>
using namespace std;
// -
class node
{
public:
int key;
node *left, *right;
};
/* ,
key left right, NULL. */
node* newNode(int key)
{
node* Node = new node();
Node->key = key;
Node->left = Node->right = NULL;
return (Node);
}
// y .
// , .
node *rightRotate(node *x)
{
node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
// x
// , .
node *leftRotate(node *x)
{
node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
//
// , .
// ,
// ,
// .
//
// (root).
node *splay(node *root, int key)
{
// : root NULL
//
if (root == NULL || root->key == key)
return root;
//
if (root->key > key)
{
// ,
if (root->left == NULL) return root;
// Zig-Zig (-)
if (root->left->key > key)
{
//
// left-left
root->left->left = splay(root->left->left, key);
// root,
// else
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (Left Right)
{
//
// left-right
root->left->right = splay(root->left->right, key);
// root->left
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
//
return (root->left == NULL)? root: rightRotate(root);
}
else //
{
// ,
if (root->right == NULL) return root;
// Zag-Zig (-)
if (root->right->key > key)
{
// right-left
root->right->left = splay(root->right->left, key);
// root->right
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key)// Zag-Zag (-)
{
//
// right-right
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
// root
return (root->right == NULL)? root: leftRotate(root);
}
}
// k splay-
node *insert(node *root, int k)
{
// :
if (root == NULL) return newNode(k);
// -
root = splay(root, k);
// ,
if (root->key == k) return root;
//
node *newnode = newNode(k);
// , ,
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
// , ,
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; //
}
//
// .
//
void preOrder(node *root)
{
if (root != NULL)
{
cout<<root->key<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
/* */
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;
}
// rathbhupendra
C
// c http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html
#include<stdio.h>
#include<stdlib.h>
// -
struct node
{
int key;
struct node *left, *right;
};
/* ,
key left right, NULL. */
struct node* newNode(int key)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
// y .
// , .
struct node *rightRotate(struct node *x)
{
struct node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
// x
// , .
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
//
// , .
// ,
// ,
// .
//
// .
struct node *splay(struct node *root, int key)
{
// : NULL
//
if (root == NULL || root->key == key)
return root;
//
if (root->key > key)
{
// ,
if (root->left == NULL) return root;
// Zig-Zig (-)
if (root->left->key > key)
{
//
// left-left
root->left->left = splay(root->left->left, key);
// ,
// else
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (-)
{
//
// left-right
root->left->right = splay(root->left->right, key);
// root->left
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
//
return (root->left == NULL)? root: rightRotate(root);
}
else //
{
// ,
if (root->right == NULL) return root;
// Zag-Zig (-)
if (root->right->key > key)
{
// right-left
root->right->left = splay(root->right->left, key);
// root->right
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key)// Zag-Zag (-)
{
//
// right-right
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
//
return (root->right == NULL)? root: leftRotate(root);
}
}
// k splay-
struct node *insert(struct node *root, int k)
{
// :
if (root == NULL) return newNode(k);
// -
root = splay(root, k);
// ,
if (root->key == k) return root;
//
struct node *newnode = newNode(k);
// , ,
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
// , ,
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; //
}
//
// .
//
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
/* */
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;
}
:
Preorder traversal of the modified Splay tree is
25 20 50 30 40 100 200
« ».
« ».