sweet04527520

fp-sd-22-kenalan-kuy

May 28th, 2022 (edited)
517
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. typedef struct AVLNode
  5. {
  6.     int data;
  7.     struct AVLNode *left,*right,*parent;
  8.     int height;
  9.     int status; //distance or visited
  10. }AVLNode;
  11.  
  12. AVLNode* avl_createNode(AVLNode *parent, int value) {
  13.     AVLNode *newNode = (AVLNode*) malloc(sizeof(AVLNode));
  14.     newNode->data = value;
  15.     newNode->height = 1;
  16.     newNode->left = newNode->right = NULL;
  17.     newNode->parent = parent;
  18.     newNode->status = 1;
  19.     return newNode;
  20. }
  21.  
  22. int _getHeight(AVLNode* node){
  23.     if(node==NULL)
  24.         return 0;
  25.     return node->height;
  26. }
  27.  
  28. int _max(int a,int b){
  29.     return (a > b)? a : b;
  30. }
  31.  
  32. int _getBalanceFactor(AVLNode* node){
  33.     if(node==NULL)
  34.         return 0;
  35.     return _getHeight(node->left)-_getHeight(node->right);
  36. }
  37.  
  38. //Rotationsss
  39.  
  40. AVLNode* _rightRotate(AVLNode* pivotNode) {
  41.    
  42.     AVLNode* newParrent = pivotNode->left;
  43.     newParrent->parent = pivotNode->parent;
  44.     pivotNode->left = newParrent->right;
  45.     if(newParrent->right) newParrent->right->parent = pivotNode;
  46.     newParrent->right = pivotNode;
  47.     pivotNode->parent = newParrent;
  48.    
  49.    
  50.     pivotNode->height=_max(_getHeight(pivotNode->left),
  51.                       _getHeight(pivotNode->right))+1;
  52.     newParrent->height=_max(_getHeight(newParrent->left),
  53.                        _getHeight(newParrent->right))+1;
  54.    
  55.     return newParrent;
  56. }
  57.  
  58. AVLNode* _leftRotate(AVLNode* pivotNode) {
  59.  
  60.     AVLNode* newParrent = pivotNode->right;
  61.     newParrent->parent = pivotNode->parent;
  62.     pivotNode->right = newParrent->left;
  63.     if(newParrent->left) newParrent->left->parent = pivotNode;
  64.     newParrent->left = pivotNode;
  65.     pivotNode->parent = newParrent;
  66.  
  67.     pivotNode->height=_max(_getHeight(pivotNode->left),
  68.                       _getHeight(pivotNode->right))+1;
  69.     newParrent->height=_max(_getHeight(newParrent->left),
  70.                        _getHeight(newParrent->right))+1;
  71.    
  72.     return newParrent;
  73. }
  74.  
  75. AVLNode* _leftCaseRotate(AVLNode* node){
  76.     return _rightRotate(node);
  77. }
  78.  
  79. AVLNode* _rightCaseRotate(AVLNode* node){
  80.     return _leftRotate(node);
  81. }
  82.  
  83. AVLNode* _leftRightCaseRotate(AVLNode* node){
  84.     AVLNode *temp = _leftRotate(node->left);
  85.     node->left = temp;
  86.     temp->parent = node;
  87.     return _rightRotate(node);
  88. }
  89.  
  90. AVLNode* _rightLeftCaseRotate(AVLNode* node){
  91.     AVLNode *temp = _rightRotate(node->right);
  92.     node->right = temp;
  93.     temp->parent = node;
  94.     return _leftRotate(node);
  95. }
  96. //--
  97.  
  98. AVLNode* _insert_AVL(AVLNode *root, AVLNode *parent, int value) {
  99.     if(root == NULL) // udah mencapai leaf
  100.         return avl_createNode(parent, value);
  101.     if(value < root->data)
  102.         root->left = _insert_AVL(root->left,root,value);
  103.     else if(value > root->data)
  104.             root->right = _insert_AVL(root->right,root,value);
  105.     root->height = 1 + _max(_getHeight(root->left),_getHeight(root->right));
  106.     int balanceFactor = _getBalanceFactor(root);
  107.    
  108.     if(balanceFactor > 1 && value < root->left->data) // skewed kiri (left-left case)
  109.         return _leftCaseRotate(root);
  110.     if(balanceFactor > 1 && value > root->left->data) //
  111.         return _leftRightCaseRotate(root);
  112.     if(balanceFactor < -1 && value > root->right->data)
  113.         return _rightCaseRotate(root);
  114.     if(balanceFactor < -1 && value < root->right->data)
  115.         return _rightLeftCaseRotate(root);
  116.    
  117.     return root;
  118. }
  119.  
  120. AVLNode *avl_find(AVLNode *root, int value){   
  121.     if(root){
  122.         if(value < root->data) return avl_find(root->left, value);
  123.         if(value > root->data) return avl_find(root->right,value);
  124.     }
  125.     return root;
  126. }
  127.  
  128. int count = 0, max_count, max_distance;
  129.  
  130. AVLNode *find_predecessor(AVLNode *root, int *distance){
  131.     if(root->parent && *distance < max_distance){
  132.         root->status = -1;
  133.         *distance += 1;
  134.         return find_predecessor(root->parent, distance);
  135.     }
  136.     return root;
  137. }
  138.  
  139.  
  140. void traverse(AVLNode *root, int distance){
  141.     if(root && distance <= max_distance){
  142.         if(count < max_count && root->right)
  143.             traverse(root->right, distance + root->right->status);
  144.         if(count < max_count){
  145.             printf("%d ", root->data);
  146.             count++;
  147.         }
  148.         if(count < max_count && root->left)
  149.             traverse(root->left, distance + root->left->status);
  150.     }
  151. }
  152.  
  153. void set_status(AVLNode *root){
  154.     if(root){
  155.         root->status = 1;
  156.         if(root->left)
  157.             if(root->left->status == -1) set_status(root->left);
  158.         else if(root->right)
  159.             if(root->right->status == -1) set_status(root->right);
  160.     }
  161. }
  162.  
  163.  
  164. void solve(AVLNode *root, int value){
  165.     count = 0;
  166.     AVLNode *starting = avl_find(root, value);
  167.     if(starting == NULL){
  168.         printf("Eyyy lom dateng :)\n");
  169.         return;
  170.     }
  171.     int distance = 0;
  172.     AVLNode *predecessor = find_predecessor(starting, &distance);
  173.     traverse(predecessor, distance);
  174.     printf("\n");
  175.     set_status(predecessor);
  176. }
  177.  
  178. int main(){
  179.     AVLNode *root = NULL;
  180.     int cmd, data, size = 0;
  181.     while(1){
  182.         scanf("%d",&cmd);
  183.         if(cmd == -1) break;
  184.         if(cmd == 0){
  185.             scanf("%d%d%d",&data,&max_distance, &max_count);
  186.             if(max_count == -1) max_count = size;
  187.             solve(root, data);
  188.         }
  189.         else{
  190.             while(cmd--){
  191.                 size++;
  192.                 scanf("%d", &data);
  193.                 root = _insert_AVL(root, NULL, data);    
  194.             }    
  195.         }
  196.     }
  197.     printf("End\n");
  198. }
  199.  
  200.  
RAW Paste Data Copied