Hello, Khabrovites. In anticipation of the start of the course "Algorithms and Data Structures", we invite future students and everyone to an open lesson on the topic "Reserves of Binary Search Trees".
We also share a traditional useful translation.
: 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
« ».
« ».