Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- typedef struct Node Node;
- struct Node
- {
- int key, count;
- char *value;
- Node *parent, *left, *right;
- };
- Node *tree_find_node(Node *root, int key)
- {
- Node *node = root;
- while(node && node->key != key)
- {
- if(key < node->key) node = node->left;
- else node = node->right;
- }
- return node;
- }
- void tree_insert( Node **root, int key, char *value)
- {
- Node *new_node = (Node *)malloc(sizeof(Node));
- new_node->key = key;
- new_node->value = value;
- new_node->count = 0;
- new_node->parent = NULL; new_node->left = NULL; new_node->right = NULL;
- if(!*root)
- {
- *root = new_node;
- return;
- }
- Node *node = *root;
- for(unsigned char k = 0; k < 300; k++)
- {
- node->count++;
- if(key < node->key)
- {
- if(!node->left)
- {
- node->left = new_node;
- new_node->parent = node;
- break;
- }
- node = node->left;
- }
- else
- {
- if(!node->right)
- {
- node->right = new_node;
- new_node->parent = node;
- break;
- }
- node = node->right;
- }
- }
- }
- void replace_node(Node **root, Node *x, Node *y)
- {
- if(*root == x)
- {
- *root = y;
- if(y) y->parent = NULL;
- }
- else
- {
- Node *parent = x->parent;
- if(y) y->parent = parent;
- if(parent->left == x) parent->left = y;
- else parent->right = y;
- }
- }
- Node *minimum(Node *node)
- {
- if(!node) return NULL;
- else
- {
- while(node->left)
- {
- node->count--;
- node = node->left;
- }
- return node;
- }
- }
- Node *succ(Node *node)
- {
- if(node->right)
- {
- return minimum(node->right);
- }
- else
- {
- Node *node_ = node->parent;
- while(node_ && node == node_->right)
- {
- node = node_;
- node_ = node_->parent;
- }
- return node_;
- }
- }
- void clear_tree(Node *node)
- {
- if(node)
- {
- if(node->right)
- clear_tree(node->right);
- if(node->left)
- clear_tree(node->left);
- free(node->value);
- free(node);
- }
- }
- void delete(Node **root, int key)
- {
- Node *node = tree_find_node(*root, key);
- Node *tr = *root;
- while(tr && tr->key != key)
- {
- tr->count--;
- if(key < tr->key) tr = tr->left;
- else tr = tr->right;
- }
- if(!node->left && !node->right) replace_node(root, node, NULL);
- else if(!node->left) replace_node(root, node, node->right);
- else if(!node->right) replace_node(root, node, node->left);
- else
- {
- Node *y = succ(node);
- replace_node(root, y, y->right);
- node->left->parent = y;
- y->left = node->left;
- if(node->right) node->right->parent = y;
- y->right = node->right;
- y->count = node->count - 1;
- replace_node(root, node, y);
- }
- free(node->value);
- free(node);
- }
- Node *search(Node *root, int rank)
- {
- Node *node = root;
- while(node)
- {
- if(node->left)
- {
- if(node->left->count == rank - 1) return node;
- else if(node->left->count > rank - 1) node = node->left;
- else
- {
- rank -= node->left->count + 2;
- node = node->right;
- }
- }
- else
- {
- if(rank)
- {
- rank--;
- node = node->right;
- }
- else return node;
- }
- }
- }
- int main()
- {
- int n;
- scanf("%d", &n);
- Node *root = NULL;
- char action[7], *word;
- for(int i = 0; i < n; i++)
- {
- scanf("%s", action);
- int x;
- scanf("%d", &x);
- if(strcmp("INSERT", action) == 0)
- {
- word = (char *)malloc(sizeof(char) * 10);
- scanf("%s", word);
- tree_insert(&root, x, word);
- }
- if(strcmp("SEARCH", action) == 0)
- printf("%s\n", search(root, x)->value);
- if(strcmp("LOOKUP", action) == 0)
- printf("%s\n", tree_find_node(root, x)->value);
- if(strcmp("DELETE", action) == 0)
- delete(&root, x);
- }
- clear_tree(root);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement