fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7.  
  8. struct deramid_node{
  9. 	int key;
  10. 	int priority;
  11. 	deramid_node *left;
  12. 	deramid_node *right;
  13. 	deramid_node *parent;
  14. };
  15.  
  16. typedef deramid_node deramid;
  17.  
  18. void inorder_traversal(deramid *root);
  19. deramid * deramid_search(deramid *root, int k);
  20. deramid * deramid_minimum(deramid *root);
  21. deramid * deramid_maximum(deramid *root);
  22. void left_rotate(deramid root, deramid x);
  23. void right_rotate(deramid root, deramid x);
  24. void deramid_insert(deramid *root, deramid *z);
  25.  
  26.  
  27. void inorder_traversal(deramid *root){
  28. 	if(root != NULL){
  29. 		inorder_traversal(root->left);
  30. 		printf("%d ", root->key);
  31. 		inorder_traversal(root->right);
  32. 	}
  33. }
  34.  
  35. deramid * deramid_search(deramid *root, int k){
  36. 	while(root != NULL && root->key != k){
  37. 		if(k < root->key)	root = root->left;
  38. 		else				root = root->right;
  39. 	}
  40. 	return root;
  41. }
  42.  
  43. deramid * deramid_minimum(deramid *root){
  44. 	while(root->left != NULL)
  45. 		root = root->left;
  46. 	return root;
  47. }
  48.  
  49. deramid * deramid_maximum(deramid *root){
  50. 	while(root->right != NULL)
  51. 		root = root->right;
  52. 	return root;
  53. }
  54.  
  55. void left_rotate(deramid *root, deramid *x){
  56. 	deramid *y = x->right;
  57. 	x->right = y->left;
  58. 	if(y->left != NULL) y->left->parent = x;
  59. 	y->parent = x->parent;
  60. 	if(x->parent == NULL) root = y;
  61. 	else{
  62. 		if(x == x->parent->left)	x->parent->left = y;
  63. 		else						x->parent->right = y;
  64. 	}
  65. 	y->left = x;
  66. 	x->parent = y;
  67. }
  68.  
  69. void right_rotate(deramid *root, deramid *x){
  70. 	deramid *y = x->left;
  71. 	x->left = y->right;
  72. 	if(y->right != NULL) y->right->parent = x;
  73. 	y->parent = x->parent;
  74. 	if(x->parent == NULL) root = y;
  75. 	else{
  76. 		if(x == x->parent->right)	x->parent->right = y;
  77. 		else						x->parent->left = y;
  78. 	}
  79. 	y->right = x;
  80. 	x->parent = y;
  81. }
  82.  
  83. void deramid_insert(deramid *root, deramid *z){
  84. 	deramid *x = root;	//Отмечает проходимый путь
  85. 	deramid *y = NULL;	//Ссылается на родительский по отношению к x узел
  86. 	deramid *p = NULL;
  87.  
  88. 	srand(time(NULL));
  89. 	z->priority = rand() % 701;
  90. 	while(x != NULL){
  91. 		y = x;
  92. 		if(z->key < x->key) x = x->left;
  93. 		else				x = x->right;
  94. 	}
  95. 	y = z->parent;	//Позаботиться о том, чтобы все поля z кроме key были NULL
  96. 	if(y == NULL) root = z;
  97. 	else{
  98. 		if(z->key < y->key) y->left = z;
  99. 		else				y->right = z;	
  100. 	}
  101. 	z->parent = y;
  102. 	p = z;	//Для прохода вверх
  103. 	while(y != root){
  104. 		if(y->priority < y->left->priority) right_rotate(root, y);
  105. 		if(y->priority < y->right->priority) left_rotate(root, y);
  106. 		y = y->parent;
  107. 	}
  108. }
  109.  
  110. int main() {
  111. 	deramid *d = NULL;
  112. 	deramid *p = NULL;
  113. 	for(int i = 0; i < 10; i++){
  114. 		p = (deramid *)malloc(sizeof(deramid));
  115. 		p->key = i;
  116. 		p->priority = 0;
  117. 		p->parent = NULL;
  118. 		p->left = NULL;
  119. 		p->right = NULL;
  120. 		deramid_insert(d, p);
  121. 	}
  122. 	return 0;
  123. }
Runtime error #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1ZDuxS
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!