Time limit: 19ms
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>
#include <stdbool.h>
#include <string.h>
#define INF -999999
typedef enum {PUT = 1, GET, ERASE, SIZE, PRINT, ERROR_OP} OP;
// AVL tree node
struct AVLTreeNode{
int key;
int value;
int height;
struct AVLTreeNode* left;
struct AVLTreeNode* right;
};
typedef struct AVLTreeNode* TreeNode;
// Map Data Structure
struct Map {
int size;
TreeNode root;
};
typedef struct Map* MapADT;
OP get_op() {
char str[20];
scanf("%s", str);
if (strcmp(str, "put") == 0) {
return PUT;
} else if (strcmp(str, "get") == 0) {
return GET;
} else if (strcmp(str, "erase") == 0) {
return ERASE;
} else if (strcmp(str, "size") == 0) {
return SIZE;
} else if (strcmp(str, "print") == 0) {
return PRINT;
} else {
return ERROR_OP;
}
}
// AVL tree
TreeNode createNode(int key, int value) {
TreeNode node = (TreeNode)malloc(sizeof(struct AVLTreeNode));
node->key = key;
node->height = 1;
node->left = NULL;
node->right = NULL;
node->value = value;
return node;
}
TreeNode Lchild(TreeNode root) {
return root->left;
}
TreeNode Rchild(TreeNode root) {
return root->right;
}
int Data(TreeNode root) {
return root->key;
}
bool isEmpty(TreeNode root) {
return root == NULL;
}
void Preorder(TreeNode root) {
if (!isEmpty(root)) {
printf("<%d,%d> ", root->key, root->value);
Preorder(Lchild(root));
Preorder(Rchild(root));
}
}
void Inorder(TreeNode root) {
if (!isEmpty(root)) {
Inorder(Lchild(root));
printf("<%d,%d> ", root->key, root->value);
Inorder(Rchild(root));
}
}
void Postorder(TreeNode root) {
if (!isEmpty(root)) {
Postorder(Lchild(root));
Postorder(Rchild(root));
printf("<%d,%d> ", root->key, root->value);
}
}
int max(int a, int b) {
if (a > b) {
return a;
}
else {
return b;
}
}
int Height(TreeNode root) {
if (isEmpty(root)) {
return 0;
}
return root->height;
}
int calHeight(TreeNode root)
{
if (isEmpty(root)) {
return 0;
}
return 1+max(Height(root->left), Height(root->right));
}
int Search(TreeNode root, int key) {
// write your code here
}
TreeNode llRotation(TreeNode y) {
// write your code here
}
// right-right imbalance
TreeNode rrRotation(TreeNode x) {
// write your code here
}
// left-right imbalance
TreeNode lrRotation(TreeNode y) {
// write your code here
}
// right-left imbalance
TreeNode rlRotation(TreeNode x) {
// write your code here
}
int balanceFactor(TreeNode root)
{
if (root == NULL) {
return 0;
}
return Height(root->left) - Height(root->right);
}
TreeNode insertNode(TreeNode root, int key, int value) {
// write your code here
}
// if the target node has two children, replace this node with its successor, which is the smallest item in the tree rooted at its right child.
TreeNode deleteNode(TreeNode root, int key) {
// write your code here
}
// map ADT
void PrintMap(MapADT myMap) {
printf("Preorder: ");
Preorder(myMap->root);
printf("\nInorder: ");
Inorder(myMap->root);
printf("\nPostorder: ");
Postorder(myMap->root);
printf("\n");
}
MapADT CreateMap() {
MapADT myMap = (MapADT) malloc(sizeof(struct Map));
myMap->size = 0;
myMap->root = NULL;
return myMap;
}
// If there is no this key, return INF
int Get(MapADT myMap, int key) {
// write your code here
}
// If there exists this key, update the value
void Put(MapADT myMap, int key, int value) {
// write your code here
}
void Erase(MapADT myMap, int key) {
// write your code here
}
int Size(MapADT myMap) {
return myMap->size;
}
int main() {
int n, m, key, value;
TreeNode root = NULL;
MapADT myMap = CreateMap();
scanf("%d", &n);
for(int i=0; i<n; i++)
{
switch (get_op()) {
case PUT:
scanf(" %d%d", &key, &value);
Put(myMap, key, value);
break;
case GET:
scanf(" %d", &key);
printf("%d\n", Get(myMap, key));
break;
case ERASE:
scanf(" %d", &key);
Erase(myMap, key);
break;
case SIZE:
printf("%d\n", Size(myMap));
break;
case PRINT:
PrintMap(myMap);
break;
default:
printf("Error Input\n");
}
}
return 0;
}
-----------------------------------------End of Code-----------------------------------------
Description:
Implement the map ADT with the AVL tree.
The map ADT has four operations:
1. Put(key, value): insert a key-value pair into the map. If it already has the key, then update the value.
2. Get(key): given a key, report its value. If it does not have this key, report INF.
3. Erase(key): delete this key from the map.
4. Size(): report the number of elments inside the map.
Additionally, keys are sorted from smallest to largest, allowing for efficient traversal of all key-value pairs in ascending order based on the key. The traversal must be achieved in O(N) total time.
Input:
The first line contains one integer: N;
The next N lines, each of which contains one of these operations: 1. put key value (two Integers) or 2. get key 3. erase key 4. size 5. print
Output:
Each line is the result of get or size or print.
Sample Input 1:
20
put 7 7
put 9 9
put 11 11
put 5 5
put 4 4
put 6 6
put 8 8
put 12 12
put 15 15
put 10 10
get 4
put 4 1
get 4
erase 4
get 4
erase 6
erase 15
erase 12
size
print
Sample Output 1:
4
1
-999999
6
Preorder: <9,9> <7,7> <5,5> <8,8> <11,11> <10,10>
Inorder: <5,5> <7,7> <8,8> <9,9> <10,10> <11,11>
Postorder: <5,5> <8,8> <7,7> <10,10> <11,11> <9,9>