Basic Operations in Binary Search Tree
/*
Time limit: 1000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
struct treeNode {
int value, size;
struct treeNode* left;
struct treeNode* right;
struct treeNode* parent;
};
typedef struct treeNode* TreeNode;
// You need to maintain the size of the BST subtrees
TreeNode CreateTreeNode(int value) {
TreeNode node = (TreeNode) malloc(sizeof(struct treeNode));
node->value = value;
node->size = 1;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
// Insert a value x into the BST
// Remember to maintain the sizes of the BST subtrees
// Ignore the insertion if it contains x that exists in the binary search tree
TreeNode Insert(TreeNode root, int value) {
if (root == NULL) {
return CreateTreeNode(value);
}
// WRITE YOUR CODE HERE
}
// Find the successor of the node
TreeNode Successor(TreeNode root) {
// WRITE YOUR CODE HERE
}
// Delete a value x from the BST
// Remember to maintain the sizes of the BST subtrees
// Remember to free the memory of the deleted node
TreeNode Delete(TreeNode root, int value) {
// WRITE YOUR CODE HERE
}
// Query the x-th smallest value in the BST
// If the query is invalid (the size of the BST is smaller than x), return -1
int Query(TreeNode root, int x) {
// WRITE YOUR CODE HERE
}
int main()
{
int n, operation, value;
scanf("%d", &n);
TreeNode root = NULL;
for (int i = 0; i < n; i++) {
scanf("%d%d", &operation, &value);
switch (operation) {
case 1:
root = Insert(root, value);
break;
case 2:
root = Delete(root, value);
break;
case 3:
printf("%d\n", Query(root, value));
break;
}
}
return 0;
}
---------------------------------------End of Code---------------------------------------
## [Basic Operations in Binary Search Tree]
You are tasked with managing a Binary Search Tree (BST) that initially has an empty root. You will process $n$ operations, each of which belongs to one of the following types:
1. Insert a integer value $x$ into the BST. Ignore the insertion if it value $x$ already exists.
2. Delete a value $x$ in the BST (if it exists).
3. Query the $x$-th smallest value in the current BST.
For each Query operation, output the result or $-1$ if the query is invalid.
Remarks: To efficiently answer queries, you must maintain the size of all subtrees.
### Input
The first line contain an integer number $n(1\leq n \leq 3000)$, representing the number of operations.
The next n lines each describe an operation with two integers:
- **op**: The operation type (1 = Insert, 2 = Delete, 3 = Query).
- **x**: An integer value associated with the operation ($1\leq x \leq 10^6$).
### Output
For each Query (Operation 3), output the $x$-th smallest value in the BST on a new line.
If the BST contains fewer than x elements, output -1.
### Example
**Input**
```
6
1 1
1 2
1 5
3 2
2 2
3 2
```
**Output**
```
2
5
```
**Explanation**
Submit