daily pastebin goal
24%
SHARE
TWEET

Untitled

a guest Jan 15th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //либо задача не простая, либо я дибил
  2. //скорее второе :)
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. struct elem
  9. {
  10.         long int k;
  11.         char word[10];
  12.         int count;
  13.         struct elem * parent;
  14.     struct elem * left;
  15.     struct elem * right;
  16. };
  17.  
  18. struct  elem * InitBinarySearchTree(void)
  19. {
  20.    
  21.     struct elem * tree = NULL;
  22.     return tree;
  23. }
  24.  
  25. struct elem * Minimum(struct  elem * x)
  26. {
  27.     struct elem * y;
  28.     if(x == NULL)
  29.     {
  30.         y = NULL;
  31.     }
  32.     else
  33.     {
  34.         y = x;
  35.         while(y->left != NULL)
  36.         {
  37.             y->count--;
  38.             y = y->left;
  39.         }
  40.     }
  41.     return y;
  42. }
  43.  
  44. struct  elem * Succ(struct  elem * x)
  45. {
  46.     struct  elem * y;
  47.     if(x->right != NULL)
  48.     {
  49.         y = Minimum(x->right);
  50.     }
  51.     else
  52.     {
  53.         y = x->parent;
  54.         while(y != NULL && x == y->right)
  55.         {
  56.             x = y;
  57.             y = y->parent;
  58.         }
  59.     }
  60.     return y;
  61. }
  62.  
  63. struct  elem * Descend(struct elem * tree, long int k)
  64. {
  65.     struct  elem * x =tree;
  66.     while(x!= NULL && x->k != k)
  67.     {
  68.         if(k < x->k)
  69.         {
  70.             x = x->left;
  71.         }
  72.         else
  73.         {
  74.             x = x->right;
  75.         }
  76.     }
  77.     return x;
  78.    
  79. }
  80.  
  81. struct  elem * DescendforDelete(struct elem * tree, long int k)
  82. {
  83.     struct  elem * x =tree;
  84.     while(x!= NULL && x->k != k)
  85.     {
  86.         x->count--;
  87.         if(k < x->k)
  88.         {
  89.             x = x->left;
  90.         }
  91.         else
  92.         {
  93.             x = x->right;
  94.         }
  95.     }
  96.     return x;
  97.    
  98. }
  99.  
  100. char * Lookup(struct elem * tree, long int k)
  101. {
  102.     struct  elem * x = Descend(tree, k);
  103.     return x->word;
  104. }
  105.  
  106. struct elem * Insert(struct elem * tree, long int k)
  107. {
  108.     struct elem * y = (struct elem *)malloc(sizeof(struct elem));  
  109.     struct elem * x;
  110.     y->k = k;
  111.     scanf("%s", y->word);
  112.     y->parent = NULL;
  113.     y->count = 0;
  114.     y->left = NULL;
  115.     y->right = NULL;
  116.     if(tree == NULL)
  117.     {
  118.         tree = y;
  119.     }
  120.     else
  121.     {
  122.         x = tree;
  123.         while(1)
  124.         {
  125.             x->count++;
  126.             if(k < x->k)
  127.             {
  128.                 if(x->left == NULL)
  129.                 {
  130.                     x->left = y;
  131.                     y->parent = x;
  132.                     break;
  133.                 }
  134.                 x = x->left;
  135.             }
  136.             else
  137.             {
  138.                 if(x->right == NULL)
  139.                 {
  140.                     x->right = y;
  141.                     y->parent = x;
  142.                     break;
  143.                 }
  144.                 x = x->right;
  145.             }
  146.            
  147.         }
  148.     }
  149.     return tree;
  150. }
  151.  
  152. struct elem * ReplaceNode(struct elem* tree, struct elem* x, struct elem* y)
  153. {
  154.     if(tree == x)
  155.     {
  156.         tree = y;
  157.         if(y != NULL)
  158.         {
  159.             y->parent = NULL;
  160.         }
  161.     }
  162.     else
  163.     {
  164.         struct elem * p = x->parent;
  165.         if(y != NULL)
  166.         {
  167.             y->parent = p;
  168.         }
  169.         if(p->left == x)
  170.         {
  171.             p->left = y;
  172.         }
  173.         else
  174.         {
  175.             p->right = y;
  176.         }
  177.     }
  178.     return tree;
  179. }
  180.  
  181. void DeleteAll(struct elem* tree)
  182. {
  183.     struct elem *temp;
  184.     if (tree != NULL)
  185.     {
  186.             DeleteAll(tree->left);
  187.             temp = tree->right;
  188.             free(tree);
  189.             DeleteAll(temp);
  190.         }
  191. }
  192.  
  193.  
  194. struct elem *  Delete(struct elem* tree, long int k)
  195. {
  196.     struct elem * x = DescendforDelete(tree, k);
  197.     struct elem* y;
  198.     if(x->left == NULL && x->right == NULL)
  199.     {
  200.         tree =  ReplaceNode(tree, x, NULL);
  201.     }
  202.     else
  203.     {
  204.         if(x->left == NULL)
  205.         {
  206.             tree = ReplaceNode(tree, x, x->right);
  207.         }
  208.         else
  209.         {
  210.             if(x->right == NULL)
  211.             {
  212.                 tree= ReplaceNode(tree, x, x->left);
  213.             }
  214.             else
  215.             {
  216.                 y = Succ(x);
  217.                 tree = ReplaceNode(tree, y, y->right);
  218.                 x->left->parent = y;
  219.                 y->left = x->left;
  220.                 if(x->right != NULL)
  221.                 {
  222.                     x->right->parent = y;  
  223.                 }
  224.                 y->right = x->right;
  225.                 y->count = x->count-1;
  226.                 tree = ReplaceNode(tree, x, y);
  227.             }
  228.         }
  229.     }
  230.     free(x);
  231.     return tree;
  232. }
  233.  
  234. char * SearchByRank(struct elem * tree, int rank)
  235. {
  236.     struct elem * x = tree;
  237.     while(x != NULL)
  238.     {
  239.         if(x->left != NULL)
  240.         {
  241.             if(x->left->count+1 >  rank)
  242.             {
  243.                
  244.                 x = x->left;
  245.             }
  246.             else
  247.             {
  248.                 if(x->left->count+1 < rank)
  249.                 {
  250.                         rank -= x->left->count + 2;
  251.                         x = x->right;
  252.                 }
  253.                 else
  254.                 {
  255.                     return x->word;
  256.                 }
  257.  
  258.             }
  259.         }
  260.         else
  261.         {
  262.             if(rank != 0)
  263.             {
  264.                 rank--;
  265.                 x = x->right;
  266.             }
  267.             else
  268.             {
  269.                 return x->word;
  270.             }
  271.         }
  272.     }
  273. }
  274.  
  275. int main(void)
  276. {
  277.     int n;
  278.     scanf("%d", &n);
  279.     struct  elem * tree = InitBinarySearchTree();
  280.     struct  elem * forDelete;
  281.     int i = 0;
  282.     char str[6];
  283.     long int k;
  284.     for(i = 0; i < n; i++)
  285.     {
  286.         scanf("%s", str);
  287.         switch(str[0])
  288.         {
  289.             case 'S':
  290.             {
  291.                 scanf( "%ld", &k);
  292.                 printf( "%s \n", SearchByRank(tree, k));
  293.                 break;
  294.             }
  295.             case 'I':
  296.             {
  297.                 scanf("%ld", &k);
  298.                 tree = Insert(tree, k);
  299.                 break;
  300.             }
  301.             case 'L':
  302.             {
  303.                 scanf("%ld", &k);
  304.                 char * v = Lookup(tree, k);
  305.                 printf("%s \n", v);
  306.                 break;
  307.             }
  308.             case 'D':
  309.             {
  310.                 scanf("%ld", &k);
  311.                 tree = Delete(tree, k);
  312.                 break;
  313.             }
  314.         }
  315.     }
  316.     DeleteAll(tree);
  317.     return 0;
  318. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top