Hallo Khabrovites. Im Vorgriff auf den Beginn des Kurses "Algorithmen und Datenstrukturen" laden wir zukünftige Studenten und alle zu einer offenen Lektion zum Thema "Reserven binärer Suchbäume" ein.
Wir teilen auch eine traditionelle nützliche Übersetzung.
: 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
« ».
« ».