Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
4.5 kB
3
Indexable
Never
// Muhammad Exell Febrian 2440116920 //

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
	
struct Node{
	char langwords[100];
    char lang[100];
    int height;
	Node* left;
	Node* right;
};

Node* createNode(
	char langwords[100]
){
	Node *newNode = (Node *)malloc(sizeof(Node));
	strcpy(newNode->langwords, langwords);
    // Extract the first token
    char * token = strtok(langwords, " ");
    // printf("%s\n", token );
    strcpy(newNode->lang, token);
	newNode->height = 1;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

int max(int a, int b){
	return a > b ? a : b;
}

int getHeight(Node* root){
	if(!root) return 0;
	return root->height;
}

int getBalanceFactor(Node* root){
	return getHeight(root->left) - getHeight(root->right);
}

void updateHeight(Node* root){
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}

Node* rotateRight(Node* root){
	Node* child = root->left;
	Node* gchild = child->right;
	child->right = root;
	root->left = gchild;
	updateHeight(root);
	updateHeight(child);
	return child;
}

Node* rotateLeft(Node* root){
	Node* child = root->right;
	Node* gchild = child->left;
	child->left = root;
	root->right = gchild;
	updateHeight(root);
	updateHeight(child);
	return child;
}

Node* rebalance(Node* root){
	int bf = getBalanceFactor(root);
	
	if(bf < -1){
		if(getBalanceFactor(root->right) > 0){
			root->right = rotateRight(root->right);
		}
		root =  rotateLeft(root);
	} else if(bf > 1){
		if(getBalanceFactor(root->left) < 0){
			root->left = rotateLeft(root->left);
		}
		root = rotateRight(root);
	}
	return root;
}

Node* push(
	Node* root,
    char langwords[100]
){
	if(!root) {
        return createNode(langwords);
    }
	if(strcmp(langwords, root->langwords) < 0) {
		root->left = push(root->left, langwords);
	} else if (strcmp(langwords, root->langwords) > 0){
		root->right = push(root->right, langwords);
	}
	updateHeight(root);
	return rebalance(root);
	}
	
Node* searchSimiliar(Node* root, char langwords[100]){
	if(!root) return NULL;
	if(strcmp(langwords, root->langwords) < 0)
		return searchSimiliar(root->left, langwords);
	else if(strcmp(langwords, root->langwords) > 0)
		return searchSimiliar(root->right, langwords);
	else return root;
}

// Node* searchLang(Node* root, char lang[100]){
// 	if(!root) return NULL;
// 	if(strcmp(langwords, root->langwords) < 0)
// 		return searchSimiliar(root->left, langwords);
// 	else if(strcmp(langwords, root->langwords) > 0)
// 		return searchSimiliar(root->right, langwords);
// 	else return root;
// }

Node* insert(Node* root, char langwords[100]){
	root = push(root, langwords);
    printf("Succesfully Added!\n");
	return root;
}
void inOrder(Node* root){
    if(!root) return;
    inOrder(root->left);
    printf("%s\n", root->langwords);
    inOrder(root->right);
}

void seeAll(Node* root){
    if(!root) return;
    inOrder(root);
}

int main(){
	int count = 0;
	Node* root = NULL;
	
	printf("Input case count: ");
		scanf("%d", &count);
		getchar();

        for (int i=1; i<count+1; ++i) {
            char inp[100];

            printf("Case %d: ", i);
            scanf("%[^\n]", inp);
            getchar();

            char command1[20];
            char command2[20];
            char command3[20];
            char command4[20];
            char command5[20];

            strncpy(command1, inp, 4);
            command1[4] = '\0';
            if(strcmp(command1, "ADD ")==0) {
                char langwords[100];
                strncpy(langwords, inp + 4, 100);
                root = insert(root, langwords);
                continue;
            }
            
            strcpy(command2, inp);
            if(strcmp(command2, "SHOW-ALL")==0) {
                seeAll(root);
                continue;
            }

            strncpy(command3, inp, 10);
            command3[10] = '\0';
            if(strcmp(command3, "SHOW-LANG ")==0) {
                char lang[100];
                strncpy(lang, inp + 10, 100);
                printf("%s\n", lang);
                // root = insert(root, lang);
                continue;
            }

            strncpy(command4, inp, 9);
            command4[9] = '\0';
            if(strcmp(command4, "DEL-LANG ")==0) {
                //SHOW ALL
                continue;
            }

            strncpy(command5, inp, 10);
            command5[9] = '\0';
            if(strcmp(command5, "DEL-WORD ")==0) {
                //SHOW ALL
                continue;
            }
        }

    return 0;
}