Halo, Khabrovites. Untuk mengantisipasi dimulainya kursus "Algoritma dan Struktur Data", kami mengundang siswa yang akan datang dan semua orang untuk mengikuti pelajaran terbuka dengan topik "Cadangan Pohon Pencarian Biner".
Kami juga membagikan terjemahan tradisional yang berguna.
: 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
« ».
« ».