Maintaining a Set with Binary Search Tree
/*
Time limit: 5000ms
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>
/* === BST Node ===================================================== */
typedef struct BSTNode {
int val;
int size; /* number of nodes in this subtree */
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
/* Function prototypes */
BSTNode *new_node(int val);
int get_size(BSTNode *n);
BSTNode *bst_insert(BSTNode *root, int val);
BSTNode *bst_delete(BSTNode *root, int val);
int bst_search(BSTNode *root, int val);
int bst_lower_bound(BSTNode *root, int x);
int bst_kth(BSTNode *root, int k);
void free_tree(BSTNode *root);
/**
* @brief Allocate a new BST node (size = 1).
*/
BSTNode *new_node(int val) {
BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode));
node->val = val;
node->size = 1;
node->left = NULL;
node->right = NULL;
return node;
}
/**
* @brief Return the subtree size of n (0 if n is NULL).
*/
int get_size(BSTNode *n) { return n ? n->size : 0; }
/**
* @brief Free all nodes in the tree.
*/
void free_tree(BSTNode *root) {
if (!root) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}
/**
* @brief Insert key val into the BST rooted at root.
* @return the (possibly updated) root of the tree.
*/
BSTNode *bst_insert(BSTNode *root, int val) {
// WRITE YOUR CODE HERE
}
/**
* @brief Delete key val from the BST rooted at root.
* @return the (possibly updated) root of the tree.
*/
BSTNode *bst_delete(BSTNode *root, int val) {
// WRITE YOUR CODE HERE
}
/**
* @brief Search for key val in the BST.
*
* @return 1 if val is present, 0 otherwise.
*/
int bst_search(BSTNode *root, int val) {
// WRITE YOUR CODE HERE
}
/**
* @brief Find the smallest key in the BST that is >= x (lower bound of x).
* @return the lower bound key, or -1 if no key >= x exists.
*/
int bst_lower_bound(BSTNode *root, int x) {
// WRITE YOUR CODE HERE
}
/**
* @brief Return the k-th smallest key in the BST (1-indexed).
* @param k rank to query (return -1 if k is out of range)
* @return the k-th smallest key
*/
int bst_kth(BSTNode *root, int k) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int n;
scanf("%d", &n);
BSTNode *root = NULL;
for (int i = 0; i < n; ++i) {
int op, x;
scanf("%d %d", &op, &x);
if (op == 1) {
root = bst_insert(root, x);
} else if (op == 2) {
root = bst_delete(root, x);
} else if (op == 3) {
printf("%d\n", bst_search(root, x));
} else if (op == 4) {
printf("%d\n", bst_lower_bound(root, x));
} else {
printf("%d\n", bst_kth(root, x));
}
}
free_tree(root);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Maintaining a Set with Binary Search Tree
Implement a dynamic set using a **Binary Search Tree (BST)** that supports five operations:
1. **Insert** a key $x$. If $x$ already exists, ignore the operation.
2. **Delete** a key $x$. If $x$ does not exist, ignore the operation.
3. **Search** for a key $x$. Output $1$ if $x$ is in the set, or $0$ otherwise.
4. **Lower bound** of $x$. Output the smallest key in the set that is $\geq x$, or $-1$ if no such key exists.
5. **$k$-th smallest key**: output the $k$-th smallest key in the set (1-indexed). It is guaranteed that $k$ does not exceed the current set size.
**Hint**
To answer **$k$-th smallest key** efficiently, augment each BST node with a `size` field that records the number of nodes in its subtree. Update `size` during every insertion and deletion.
### Input
- The first line contains $n$ ($1 \leq n \leq 10^5$), the number of operations.
- The next $n$ lines each describe one operation:
- `1 x` -- Insert key $x$
- `2 x` -- Delete key $x$
- `3 x` -- Search for key $x$ (output $1$ or $0$)
- `4 x` -- Lower bound of $x$ (output smallest key $\geq x$, or $-1$)
- `5 k` -- $k$-th smallest key (output the $k$-th smallest key, if no such key exists, output $-1$)
- All keys satisfy $1 \leq x \leq 10^6$.
### Output
For each operation of type 3, 4, or 5, output one integer per line.
### Example
**Input**
```
12
1 5
1 3
1 7
1 1
1 9
3 3
4 4
5 2
2 3
3 3
4 6
5 3
```
**Output**
```
1
5
3
0
7
7
```
Submit