fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long n;
  5. long long count = 1;
  6. bool found = false;
  7. bool incr = false;
  8.  
  9. class BST
  10. {
  11.     long long data, index;
  12.     BST *left, *right;
  13.  
  14. public:
  15.     // Default constructor.
  16.     BST();
  17.  
  18.     // Parameterized constructor.
  19.     BST(long long, long long);
  20.  
  21.     // Insert function.
  22.     BST* Insert(BST*, BST*, long long);
  23.  
  24. 	void Increment(BST*, long long);
  25.  
  26.     // Inorder traversal.
  27.     void Inorder(BST*);
  28.  
  29.     void IndexSearch(BST*, long long int);
  30. };
  31.  
  32.  
  33. BST ::BST()
  34.     : data(0)
  35.     , left(NULL)
  36.     , right(NULL)
  37.     , index(1)
  38. {
  39. }
  40.  
  41. BST ::BST(long long value, long long i)
  42. {
  43.     data = value;
  44.     left = right = NULL;
  45.     index = i;
  46. }
  47.  
  48.  
  49. BST* BST ::Insert(BST* root, BST* parent, long long value)
  50. {
  51.     if (!root)
  52.     {
  53.     	if (parent && parent->data < value) {
  54.     		return new BST(value, parent->index);
  55.     	}
  56.     	else if (parent && parent->data > value) {
  57.     		return new BST(value, parent->index + 1);
  58.     	}
  59.     	else {
  60.         	return new BST(value, 1);
  61.     	}
  62.     }
  63.  
  64.     if (value > root->data)
  65.     {
  66.     	incr = true;
  67.         root->right = Insert(root->right, root, value);
  68.     }
  69.     else
  70.     {
  71.         root->left = Insert(root->left, root, value);
  72.     }
  73.  
  74.     return root;
  75. }
  76.  
  77. void BST ::Increment(BST* root, long long value) {
  78.     if (!root) {
  79.         return;
  80.     }
  81.     Increment(root->left, value);//, data);
  82.     if (root->data < value) root->index += 1;
  83.     if (root->right && root->right->data < value) {
  84.     	Increment(root->right, value);//, data);
  85.     }
  86. } 
  87.  
  88. // Inorder traversal function.
  89. // This gives data in sorted order.
  90. void BST ::Inorder(BST* root)
  91. {
  92.     if (!root) {
  93.         return;
  94.     }
  95.     Inorder(root->right);
  96.     cout << "index: " << root->index;
  97.     cout << " data: " << root->data << endl;
  98.     Inorder(root->left);
  99. }
  100.  
  101. void BST ::IndexSearch(BST* root, long long value) {
  102. 	if (!root) return;
  103. 	else if (root->data == value) {
  104. 		found = true;
  105. 		cout << root->index << endl;
  106. 	}
  107. 	else if (root->data < value) IndexSearch(root->right, value);
  108. 	else IndexSearch(root->left, value);
  109. } 
  110.  
  111. // Driver code
  112. int main()
  113. {
  114. 	long long type, data;
  115.     BST b, *root = NULL;
  116.  
  117.     cin >> n;
  118.  
  119.     while (n--) {
  120.     	cin >> type;
  121.     	cin >> data;
  122.     	if (!root) {
  123.     		if (type == 1)		root = b.Insert(root, NULL, data);
  124.     		else if (type == 2)	cout << "Data tidak ada\n";
  125.     	}
  126.     	else {
  127.     		if (type == 1) {
  128.     			b.Insert(root, NULL, data);
  129.     			if (incr) b.Increment(root, data);
  130.     		}
  131.     		else {	
  132.     			b.IndexSearch(root, data);
  133. 				if (!found) cout << "Data tidak ada\n";
  134.     		}
  135.     	}
  136.     	incr = false;
  137.     	found = false;
  138.     	count = 1;
  139.     }
  140. 	return 0;
  141. }
  142.  
Success #stdin #stdout 0s 5604KB
comments (?)
stdin
copy 
10
1 5
1 6
1 7
1 8
1 1 
1 2
1 3
1 4
2 1
2 8
stdout
copy 
8
1
https://ideone.com/m3rICg
language:
C++ (gcc 8.3)
created:
2 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!