fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <stdlib.h>
  5. #include <stdbool.h>
  6.  
  7.  
  8. typedef struct AVLNode_t
  9. {
  10.     int data;
  11.     struct AVLNode_t *left,*right;
  12.     int height;
  13. }AVLNode;
  14.  
  15. typedef struct AVL_t
  16. {
  17.     AVLNode *_root;
  18.     unsigned int _size;
  19. }AVL;
  20.  
  21. AVLNode* _avl_createNode(int value) {
  22.     AVLNode *newNode = (AVLNode*) malloc(sizeof(AVLNode));
  23.     newNode->data = value;
  24.     newNode->height=1;
  25.     newNode->left = newNode->right = NULL;
  26.     return newNode;
  27. }
  28.  
  29. AVLNode* _search(AVLNode *root, int value) {
  30.     while (root != NULL) {
  31.         if (value < root->data)
  32.             root = root->left;
  33.         else if (value > root->data)
  34.             root = root->right;
  35.         else
  36.             return root;
  37.     }
  38.     return root;
  39. }
  40.  
  41. int _getHeight(AVLNode* node){
  42.     if(node==NULL)
  43.         return 0; 
  44.     return node->height;
  45. }
  46.  
  47. int _max(int a,int b){
  48.     return (a > b)? a : b;
  49. }
  50.  
  51. AVLNode* _rightRotate(AVLNode* pivotNode) {
  52.  
  53.     AVLNode* newParrent=pivotNode->left;
  54.     pivotNode->left=newParrent->right;
  55.     newParrent->right=pivotNode;
  56.  
  57.     pivotNode->height=_max(_getHeight(pivotNode->left),
  58.                       _getHeight(pivotNode->right))+1;
  59.     newParrent->height=_max(_getHeight(newParrent->left),
  60.                        _getHeight(newParrent->right))+1;
  61.  
  62.     return newParrent;
  63. }
  64.  
  65. AVLNode* _leftRotate(AVLNode* pivotNode) {
  66.  
  67.     AVLNode* newParrent=pivotNode->right;
  68.     pivotNode->right=newParrent->left;
  69.     newParrent->left=pivotNode;
  70.  
  71.     pivotNode->height=_max(_getHeight(pivotNode->left),
  72.                       _getHeight(pivotNode->right))+1;
  73.     newParrent->height=_max(_getHeight(newParrent->left),
  74.                        _getHeight(newParrent->right))+1;
  75.  
  76.     return newParrent;
  77. }
  78.  
  79. AVLNode* _leftCaseRotate(AVLNode* node){
  80.     return _rightRotate(node);
  81. }
  82.  
  83. AVLNode* _rightCaseRotate(AVLNode* node){
  84.     return _leftRotate(node);
  85. }
  86.  
  87. AVLNode* _leftRightCaseRotate(AVLNode* node){
  88.     node->left=_leftRotate(node->left);
  89.     return _rightRotate(node);
  90. }
  91.  
  92. AVLNode* _rightLeftCaseRotate(AVLNode* node){
  93.     node->right=_rightRotate(node->right);
  94.     return _leftRotate(node);
  95. }
  96.  
  97. int _getBalanceFactor(AVLNode* node){
  98.     if(node==NULL)
  99.         return 0;
  100.     return _getHeight(node->left)-_getHeight(node->right);
  101. }
  102.  
  103. AVLNode* _insert_AVL(AVL *avl,AVLNode* node,int value) {
  104.  
  105.     if(node==NULL) // udah mencapai leaf
  106.         return _avl_createNode(value);
  107.     if(value < node->data)
  108.         node->left = _insert_AVL(avl,node->left,value);
  109.     else if(value > node->data)
  110.         node->right = _insert_AVL(avl,node->right,value);
  111.  
  112.     node->height= 1 + _max(_getHeight(node->left),_getHeight(node->right)); 
  113.  
  114.     int balanceFactor=_getBalanceFactor(node);
  115.  
  116.     if(balanceFactor > 1 && value < node->left->data) // skewed kiri (left-left case)
  117.         return _leftCaseRotate(node);
  118.     if(balanceFactor > 1 && value > node->left->data) // 
  119.         return _leftRightCaseRotate(node);
  120.     if(balanceFactor < -1 && value > node->right->data)
  121.         return _rightCaseRotate(node);
  122.     if(balanceFactor < -1 && value < node->right->data)
  123.         return _rightLeftCaseRotate(node);
  124.  
  125.     return node;
  126. }
  127.  
  128. AVLNode* _findMinNode(AVLNode *node) {
  129.     AVLNode *currNode = node;
  130.     while (currNode && currNode->left != NULL)
  131.         currNode = currNode->left;
  132.     return currNode;
  133. }
  134.  
  135. AVLNode* _remove_AVL(AVLNode* node,int value){
  136.     if(node==NULL)
  137.         return node;
  138.     if(value > node->data)
  139.         node->right=_remove_AVL(node->right,value);
  140.     else if(value < node->data)
  141.         node->left=_remove_AVL(node->left,value);
  142.     else{
  143.         AVLNode *temp;
  144.         if((node->left==NULL)||(node->right==NULL)){
  145.             temp=NULL;
  146.             if(node->left==NULL) temp=node->right;  
  147.             else if(node->right==NULL) temp=node->left;
  148.  
  149.             if(temp==NULL){
  150.                 temp=node;
  151.                 node=NULL;
  152.             }
  153.             else
  154.                 *node=*temp;   
  155.  
  156.             free(temp);
  157.         }
  158.         else{
  159.             temp = _findMinNode(node->right);
  160.             node->data=temp->data;
  161.             node->right=_remove_AVL(node->right,temp->data);
  162.         }    
  163.     }
  164.  
  165.     if(node==NULL) return node;
  166.  
  167.     node->height=_max(_getHeight(node->left),_getHeight(node->right))+1;
  168.  
  169.     int balanceFactor= _getBalanceFactor(node);
  170.  
  171.     if(balanceFactor>1 && _getBalanceFactor(node->left)>=0) 
  172.         return _leftCaseRotate(node);
  173.  
  174.     if(balanceFactor>1 && _getBalanceFactor(node->left)<0) 
  175.         return _leftRightCaseRotate(node);
  176.  
  177.     if(balanceFactor < -1 && _getBalanceFactor(node->right)<=0) 
  178.         return _rightCaseRotate(node);
  179.  
  180.     if(balanceFactor < -1 && _getBalanceFactor(node->right)>0) 
  181.         return _rightLeftCaseRotate(node);
  182.  
  183.     return node;
  184. }
  185.  
  186. void avl_init(AVL *avl) {
  187.     avl->_root = NULL;
  188.     avl->_size = 0u;
  189. }
  190.  
  191. bool avl_isEmpty(AVL *avl) {
  192.     return avl->_root == NULL;
  193. }
  194.  
  195. bool avl_find(AVL *avl, int value) {
  196.     AVLNode *temp = _search(avl->_root, value);
  197.     if (temp == NULL)
  198.         return false;
  199.  
  200.     if (temp->data == value)
  201.         return true;
  202.     else
  203.         return false;
  204. }
  205.  
  206. void avl_insert(AVL *avl,int value){
  207.     if(!avl_find(avl,value)){
  208.         avl->_root=_insert_AVL(avl,avl->_root,value);
  209.         avl->_size++;
  210.     }
  211.  
  212. }
  213.  
  214. void avl_remove(AVL *avl,int value){
  215.     if(avl_find(avl,value)){
  216.         avl->_root=_remove_AVL(avl->_root,value);
  217.         avl->_size--;
  218.     }
  219.  
  220. }
  221.  
  222. void preorder(AVLNode *root) {
  223.     if (root) {
  224.         printf("%d ", root->data);
  225.         preorder(root->left);
  226.         preorder(root->right);
  227.     }
  228. }
  229.  
  230. void inorder(AVLNode *root) {
  231.     if (root) {
  232.         inorder(root->left);
  233.         printf("%d ", root->data);
  234.         inorder(root->right);
  235.     }
  236. }
  237. void postorder(AVLNode *root) {
  238.     if (root) {
  239.         postorder(root->left);
  240.         postorder(root->right);
  241.         printf("%d ", root->data);
  242.     }
  243. }
  244.  
  245.  
  246. // Mencari  selisih sibling parent Node
  247. void find_sibpar(AVLNode *root, int value, int *diff, int flag) {
  248.     if(root) {
  249.         if(((root->left && root->left->data == value) || (root->right && root->right->data == value)) && flag == 1) {
  250.             *diff -= root->data;
  251.             *diff = abs(*diff);
  252.         }
  253.         else if(flag == 2 && root->left && root->right) {
  254.             if(root->left->data == value) {
  255.                 *diff -= root->right->data;
  256.                 *diff = abs(*diff);
  257.             }
  258.             else if(root->right->data == value){
  259.                 *diff -= root->left->data;
  260.                 *diff = abs(*diff);
  261.             }
  262.         }
  263.         find_sibpar(root->left, value, diff, flag);
  264.         find_sibpar(root->right, value, diff, flag);
  265.     }
  266. }
  267.  
  268. void dif_sibpar(AVL *avl, int value) {
  269.     int selisih = 0;
  270.     find_sibpar(avl->_root, value, &selisih, 1);
  271.     find_sibpar(avl->_root, selisih, &selisih, 2);
  272.     if(selisih == 0) printf("Aku adalah Kepala Keluarga Pawel\n");
  273.     else printf("%d\n", selisih);
  274. }
  275.  
  276. int main(){
  277.     AVL avlku;
  278.     avl_init(&avlku);
  279.  
  280.     int N, T;
  281.     scanf("%d %d", &N, &T);
  282.  
  283.     int U;    // umur masing-masing anggota keluarga 
  284.     int i;
  285.     for(i = 0; i < N; i++){
  286.         scanf("%d", &U);
  287.         avl_insert(&avlku, U);
  288.     }
  289.  
  290.  
  291.     int R;    // umur yang akan dicari 
  292.     for(i = 0; i < T; i++){
  293.         scanf("%d", &R);
  294.  
  295.         if(avl_find(&avlku, R))
  296.             dif_sibpar(&avlku, R);
  297.         else printf("Aku Bukan Anggota Keluarga Pawel\n");
  298.     }
  299.  
  300. }
Success #stdin #stdout 0.01s 5616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jDg6eo
language:
C (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!