#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct deramid_node{
int key;
int priority;
deramid_node *left;
deramid_node *right;
deramid_node *parent;
};
typedef deramid_node deramid;
void inorder_traversal(deramid *root);
deramid * deramid_search(deramid *root, int k);
deramid * deramid_minimum(deramid *root);
deramid * deramid_maximum(deramid *root);
void left_rotate(deramid root, deramid x);
void right_rotate(deramid root, deramid x);
void deramid_insert(deramid *root, deramid *z);
void inorder_traversal(deramid *root){
if(root != NULL){
inorder_traversal(root->left);
printf("%d ", root->key);
inorder_traversal(root->right);
}
}
deramid * deramid_search(deramid *root, int k){
while(root != NULL && root->key != k){
if(k < root->key) root = root->left;
else root = root->right;
}
return root;
}
deramid * deramid_minimum(deramid *root){
while(root->left != NULL)
root = root->left;
return root;
}
deramid * deramid_maximum(deramid *root){
while(root->right != NULL)
root = root->right;
return root;
}
void left_rotate(deramid *root, deramid *x){
deramid *y = x->right;
x->right = y->left;
if(y->left != NULL) y->left->parent = x;
y->parent = x->parent;
if(x->parent == NULL) root = y;
else{
if(x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate(deramid *root, deramid *x){
deramid *y = x->left;
x->left = y->right;
if(y->right != NULL) y->right->parent = x;
y->parent = x->parent;
if(x->parent == NULL) root = y;
else{
if(x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void deramid_insert(deramid *root, deramid *z){
deramid *x = root; //Отмечает проходимый путь
deramid *y = NULL; //Ссылается на родительский по отношению к x узел
deramid *p = NULL;
srand(time(NULL));
z->priority = rand() % 701;
while(x != NULL){
y = x;
if(z->key < x->key) x = x->left;
else x = x->right;
}
y = z->parent; //Позаботиться о том, чтобы все поля z кроме key были NULL
if(y == NULL) root = z;
else{
if(z->key < y->key) y->left = z;
else y->right = z;
}
z->parent = y;
p = z; //Для прохода вверх
while(y != root){
if(y->priority < y->left->priority) right_rotate(root, y);
if(y->priority < y->right->priority) left_rotate(root, y);
y = y->parent;
}
}
int main() {
deramid *d = NULL;
deramid *p = NULL;
for(int i = 0; i < 10; i++){
p = (deramid *)malloc(sizeof(deramid));
p->key = i;
p->priority = 0;
p->parent = NULL;
p->left = NULL;
p->right = NULL;
deramid_insert(d, p);
}
return 0;
}