fork(2) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stdlib.h>
  5. #include <time.h>
  6.  
  7.  
  8. typedef struct node{
  9. public:
  10. 	int key;
  11. 	int priority;
  12. 	int size;
  13. 	node *left;
  14. 	node *right;
  15. 	node *parent;
  16.  
  17. 	node(int k);
  18. } node;
  19.  
  20. node::node(int k){
  21. 	key = k;
  22. 	priority = rand() % 701;
  23. 	size = 1;
  24. 	left = right = parent = NULL;
  25. }
  26.  
  27. /*Возвращает указатель на узел, содержащий i-й в порядке
  28.  *возрастания ключ в поддереве с корнем root*/
  29. struct node * os_select(struct node *root, int i){
  30. 	int r;
  31. 	if (root != NULL && root->left)
  32. 	    r = root->left->size + 1;
  33. 	else
  34. 		r = 1;
  35. 	if(i == r) return root;
  36. 	else{
  37. 		if(i < r) return os_select(root->left, i);
  38. 		else	  return os_select(root->right, i - r);
  39. 	}
  40. }
  41.  
  42. /*По заданному указателю на узел x дерева с корнем root
  43.  *возвращает позицию данного узла при центрированном обходе*/
  44. int os_rank(struct node *root, struct node *x){
  45. 	int r = x->left->size + 1;
  46. 	struct node *y = x;
  47.  
  48. 	while(y != root){
  49. 		if(y == y->parent->right)
  50. 			r = r + y->parent->left->size + 1;
  51. 		y = y->parent;
  52. 	}
  53. 	return r;
  54. }
  55.  
  56. void traversal(node *root, int level) {
  57. 	if (root != NULL) {
  58. 		traversal(root->left, level+1);
  59. 		for (int i =0; i< level; ++i)
  60. 			printf("--");
  61. 		printf("%d %d %d\n", root->key, root->priority, root->size);
  62. 		traversal(root->right, level+1);
  63. 	}
  64. }
  65.  
  66. void left_rotate(node **root, node *x) { // NOTE: node **root
  67. 	node *y = x->right;
  68. 	x->right = y->left;
  69. 	if (y->left != NULL) y->left->parent = x;
  70. 	y->parent = x->parent;
  71. 	if (x->parent == NULL) *root = y; // NOTE: корень может помен¤тьс¤!
  72. 	else {
  73. 		if (x == x->parent->left)	x->parent->left = y;
  74. 		else						x->parent->right = y;
  75. 	}
  76. 	y->left = x;
  77. 	x->parent = y;
  78. 	// Пересчет полей size после поворота
  79. 	y->size = x->size;
  80. 	x->size = 1;
  81. 	if (x->left)
  82. 		x->size += x->left->size;
  83. 	if (x->right)
  84. 		x->size += x->right->size;
  85. }
  86.  
  87. void right_rotate(node **root, node *x) { // NOTE: node **root
  88. 	node *y = x->left;
  89. 	x->left = y->right;
  90. 	if (y->right != NULL) y->right->parent = x;
  91. 	y->parent = x->parent;
  92. 	if (x->parent == NULL) *root = y; // NOTE: корень может поменяться!
  93. 	else {
  94. 		if (x == x->parent->right)	x->parent->right = y;
  95. 		else						x->parent->left = y;
  96. 	}
  97. 	y->right = x;
  98. 	x->parent = y;
  99. 	// Пересчет полей size после поворота
  100. 	y->size = x->size;
  101. 	x->size = 1;
  102. 	if (x->left)
  103. 		x->size += x->left->size;
  104. 	if (x->right)
  105. 		x->size += x->right->size;
  106. }
  107.  
  108. void insert(node **root, node *z) { // NOTE: node **root
  109. 	node *x = *root;	//отмечает проходимый путь
  110. 	node *y = NULL;	//ссылается на родительский по отношению к x узел
  111. 	node *p = NULL;
  112.  
  113. 	while (x != NULL) {
  114. 		y = x;
  115. 		if (z->key < x->key) x = x->left;
  116. 		else				 x = x->right;
  117. 	}
  118. 	z->parent = y;
  119. 	if (y == NULL) *root = z; // NOTE: корень может поменяться!
  120. 	else {
  121. 		if (z->key < y->key) y->left = z;
  122. 		else				 y->right = z;
  123. 	}
  124.     z->size = 1;
  125. 	x = z;	//Для прохода вверх
  126. 	while (x != *root && x->priority > x->parent->priority) {
  127. 		if (x == x->parent->left)
  128. 			right_rotate(root, x->parent);
  129. 		else /* x == x->parent->right */
  130. 			left_rotate(root, x->parent);
  131. 	}
  132. }
  133.  
  134. int main(){
  135. 	std::vector<int> v;
  136. 	srand(time(NULL));
  137.  
  138. 	/*for(int i = 0; i < 50000; i++)
  139. 		v.push_back(i);
  140. 	std::random_shuffle(v.begin(), v.end());
  141. 	std::nth_element(v.begin(), v.begin() + 5, v.end());
  142. 	std::cout << "the n-th: " << v[5] << std::endl;*/
  143.  
  144. 	node *tree = NULL, *p, *nth;
  145. 	for(int i = 0; i < 10; i++){
  146. 		p = new node(i*11 % 17);
  147. 		insert(&tree, p);
  148. 	}
  149. 	traversal(tree,0);
  150. 	nth = os_select(tree, 10);
  151. 	std::cout << "nth element:" << std::endl;
  152. 	std::cout << nth->key << std::endl;
  153.  
  154.  
  155. 	int pause = 0;
  156. 	std::cin >> pause;
  157. }
Runtime error #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FRaWjF
language:
C++14 (gcc 8.3)
created:
8 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!