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. /* Struktur Node */
  22.  
  23. typedef struct queueNode_t {
  24.     int data;
  25.     struct queueNode_t *next;
  26. } QueueNode;
  27.  
  28. typedef struct queue_t {
  29.     QueueNode   *_front, 
  30.                 *_rear;
  31.     unsigned _size;
  32. } Queue;
  33.  
  34.  
  35.  
  36. AVLNode* _avl_createNode(int value) {
  37.     AVLNode *newNode = (AVLNode*) malloc(sizeof(AVLNode));
  38.     newNode->data = value;
  39.     newNode->height=1;
  40.     newNode->left = newNode->right = NULL;
  41.     return newNode;
  42. }
  43.  
  44. AVLNode* _search(AVLNode *root, int value) {
  45.     while (root != NULL) {
  46.         if (value < root->data)
  47.             root = root->left;
  48.         else if (value > root->data)
  49.             root = root->right;
  50.         else
  51.             return root;
  52.     }
  53.     return root;
  54. }
  55.  
  56. int _getHeight(AVLNode* node){
  57.     if(node==NULL)
  58.         return 0; 
  59.     return node->height;
  60. }
  61.  
  62. int _max(int a,int b){
  63.     return (a > b)? a : b;
  64. }
  65.  
  66. AVLNode* _rightRotate(AVLNode* pivotNode) {
  67.  
  68.     AVLNode* newParrent=pivotNode->left;
  69.     pivotNode->left=newParrent->right;
  70.     newParrent->right=pivotNode;
  71.  
  72.     pivotNode->height=_max(_getHeight(pivotNode->left),
  73.                       _getHeight(pivotNode->right))+1;
  74.     newParrent->height=_max(_getHeight(newParrent->left),
  75.                        _getHeight(newParrent->right))+1;
  76.  
  77.     return newParrent;
  78. }
  79.  
  80. AVLNode* _leftRotate(AVLNode* pivotNode) {
  81.  
  82.     AVLNode* newParrent=pivotNode->right;
  83.     pivotNode->right=newParrent->left;
  84.     newParrent->left=pivotNode;
  85.  
  86.     pivotNode->height=_max(_getHeight(pivotNode->left),
  87.                       _getHeight(pivotNode->right))+1;
  88.     newParrent->height=_max(_getHeight(newParrent->left),
  89.                        _getHeight(newParrent->right))+1;
  90.  
  91.     return newParrent;
  92. }
  93.  
  94. AVLNode* _leftCaseRotate(AVLNode* node){
  95.     return _rightRotate(node);
  96. }
  97.  
  98. AVLNode* _rightCaseRotate(AVLNode* node){
  99.     return _leftRotate(node);
  100. }
  101.  
  102. AVLNode* _leftRightCaseRotate(AVLNode* node){
  103.     node->left=_leftRotate(node->left);
  104.     return _rightRotate(node);
  105. }
  106.  
  107. AVLNode* _rightLeftCaseRotate(AVLNode* node){
  108.     node->right=_rightRotate(node->right);
  109.     return _leftRotate(node);
  110. }
  111.  
  112. int _getBalanceFactor(AVLNode* node){
  113.     if(node==NULL)
  114.         return 0;
  115.     return _getHeight(node->left)-_getHeight(node->right);
  116. }
  117.  
  118. AVLNode* _insert_AVL(AVL *avl,AVLNode* node,int value) {
  119.  
  120.     if(node==NULL) // udah mencapai leaf
  121.         return _avl_createNode(value);
  122.     // Bebas mau dijadikan anak kanan atau anak kiri
  123.     if(value <= node->data)
  124.         node->left = _insert_AVL(avl,node->left,value);
  125.     else if(value > node->data)
  126.         node->right = _insert_AVL(avl,node->right,value);
  127.  
  128.     node->height= 1 + _max(_getHeight(node->left),_getHeight(node->right)); 
  129.  
  130.     int balanceFactor=_getBalanceFactor(node);
  131.  
  132.     if(balanceFactor > 1 && value < node->left->data) // skewed kiri (left-left case)
  133.         return _leftCaseRotate(node);
  134.     if(balanceFactor > 1 && value > node->left->data) // 
  135.         return _leftRightCaseRotate(node);
  136.     if(balanceFactor < -1 && value > node->right->data)
  137.         return _rightCaseRotate(node);
  138.     if(balanceFactor < -1 && value < node->right->data)
  139.         return _rightLeftCaseRotate(node);
  140.  
  141.     return node;
  142. }
  143.  
  144. AVLNode* _findMinNode(AVLNode *node) {
  145.     AVLNode *currNode = node;
  146.     while (currNode && currNode->left != NULL)
  147.         currNode = currNode->left;
  148.     return currNode;
  149. }
  150.  
  151. AVLNode* _remove_AVL(AVLNode* node,int value){
  152.     if(node==NULL)
  153.         return node;
  154.     if(value > node->data)
  155.         node->right=_remove_AVL(node->right,value);
  156.     else if(value < node->data)
  157.         node->left=_remove_AVL(node->left,value);
  158.     else{
  159.         AVLNode *temp;
  160.         if((node->left==NULL)||(node->right==NULL)){
  161.             temp=NULL;
  162.             if(node->left==NULL) temp=node->right;  
  163.             else if(node->right==NULL) temp=node->left;
  164.  
  165.             if(temp==NULL){
  166.                 temp=node;
  167.                 node=NULL;
  168.             }
  169.             else
  170.                 *node=*temp;   
  171.  
  172.             free(temp);
  173.         }
  174.         else{
  175.             temp = _findMinNode(node->right);
  176.             node->data=temp->data;
  177.             node->right=_remove_AVL(node->right,temp->data);
  178.         }    
  179.     }
  180.  
  181.     if(node==NULL) return node;
  182.  
  183.     node->height=_max(_getHeight(node->left),_getHeight(node->right))+1;
  184.  
  185.     int balanceFactor= _getBalanceFactor(node);
  186.  
  187.     if(balanceFactor>1 && _getBalanceFactor(node->left)>=0) 
  188.         return _leftCaseRotate(node);
  189.  
  190.     if(balanceFactor>1 && _getBalanceFactor(node->left)<0) 
  191.         return _leftRightCaseRotate(node);
  192.  
  193.     if(balanceFactor < -1 && _getBalanceFactor(node->right)<=0) 
  194.         return _rightCaseRotate(node);
  195.  
  196.     if(balanceFactor < -1 && _getBalanceFactor(node->right)>0) 
  197.         return _rightLeftCaseRotate(node);
  198.  
  199.     return node;
  200. }
  201.  
  202. void avl_init(AVL *avl) {
  203.     avl->_root = NULL;
  204.     avl->_size = 0u;
  205. }
  206.  
  207. bool avl_isEmpty(AVL *avl) {
  208.     return avl->_root == NULL;
  209. }
  210.  
  211. bool avl_find(AVL *avl, int value) {
  212.     AVLNode *temp = _search(avl->_root, value);
  213.     if (temp == NULL)
  214.         return false;
  215.  
  216.     if (temp->data == value)
  217.  
  218.         return true;
  219.     else
  220.         return false;
  221. }
  222.  
  223. void avl_insert(AVL *avl,int value){
  224. //    if(!avl_find(avl,value)){
  225.         avl->_root=_insert_AVL(avl,avl->_root,value);
  226.         avl->_size++;
  227. //    }
  228.  
  229. }
  230.  
  231. void avl_remove(AVL *avl,int value){
  232.     if(avl_find(avl,value)){
  233.         avl->_root=_remove_AVL(avl->_root,value);
  234.         avl->_size--;
  235.     }
  236.  
  237. }
  238.  
  239. // QUEUE untuk nyari Index
  240. void queue_init(Queue *queue)
  241. {
  242.     queue->_size = 0;
  243.     queue->_front = NULL;
  244.     queue->_rear = NULL;
  245. }
  246.  
  247. bool queue_isEmpty(Queue *queue) {
  248.     return (queue->_front == NULL && queue->_rear == NULL);
  249. }
  250.  
  251. void queue_push(Queue *queue, int value)
  252. {
  253.     QueueNode *newNode = (QueueNode*) malloc(sizeof(QueueNode));
  254.     if (newNode) {
  255.         queue->_size++;
  256.         newNode->data = value;
  257.         newNode->next = NULL;
  258.  
  259.         if (queue_isEmpty(queue))                 
  260.             queue->_front = queue->_rear = newNode;
  261.         else {
  262.             queue->_rear->next = newNode;
  263.             queue->_rear = newNode;
  264.         }
  265.     }
  266. }
  267.  
  268. void queue_pop(Queue *queue)
  269. {
  270.     if (!queue_isEmpty(queue)) {
  271.         QueueNode *temp = queue->_front;
  272.         queue->_front = queue->_front->next;
  273.         free(temp);
  274.  
  275.         if (queue->_front == NULL)
  276.             queue->_rear = NULL;
  277.         queue->_size--;
  278.     }
  279. }
  280.  
  281. int queue_front(Queue *queue)
  282. {
  283.     if (!queue_isEmpty(queue)) {
  284.         return (queue->_front->data);
  285.     }
  286.     return (int)0;
  287. }
  288.  
  289. void preorder(AVLNode *root) {
  290.     if (root) {
  291.         printf("%d ", root->data);
  292.         preorder(root->left);
  293.         preorder(root->right);
  294.     }
  295. }
  296.  
  297. void inorder(AVLNode *root, Queue *queue) {
  298.     if (root) {
  299.         inorder(root->left, queue);
  300.         queue_push(queue, root->data);
  301.         inorder(root->right, queue);
  302.     }
  303. }
  304.  
  305. void postorder(AVLNode *root) {
  306.     if (root) {
  307.         postorder(root->left);
  308.         postorder(root->right);
  309.         printf("%d ", root->data);
  310.     }
  311. }
  312.  
  313.  
  314. int main(){
  315.     AVL avlku;
  316.     avl_init(&avlku);
  317.  
  318.     int Q;    //Query
  319.     int T;    //Input 
  320.  
  321.     while(scanf("%d", &Q) != EOF){
  322.         if(Q == 1){
  323.             scanf("%d", &T);
  324.             avl_insert(&avlku, T);            
  325.         }
  326.         else{
  327.             scanf("%d", &T);
  328.             if(!avl_find(&avlku, T)){
  329.                 printf("M44f h3l c4r1 4ngk4 l4in y4\n");
  330.             }
  331.             else{
  332.                 Queue queueku;
  333.                 queue_init(&queueku);
  334.  
  335.                 inorder(avlku._root, &queueku);
  336.  
  337.                 int index = 1; 
  338.                 int same = 0;
  339.                 // array buat nyimpen nilai yang akan dicek 
  340.                 // indeks nya menunjukkan nilai yang sama (same)
  341.                 int cek[1000];
  342.  
  343.                 // dihapus satu-satu sambil dicek ada yang sama atau ndak
  344.                 while(!queue_isEmpty(&queueku)){
  345.                     if(queue_front(&queueku) != T){
  346.                         queue_pop(&queueku);
  347.                         index++;
  348.                     }
  349.                     else{
  350.                         cek[same]=index;
  351.                         queue_pop(&queueku);
  352.                         same++;
  353.                         index++;
  354.                     }
  355.                 }
  356.                 if(same == 1) printf("%d\n", cek[0]);
  357.                 else{
  358.                     if(same % 2 == 0) 
  359.                         printf("%d\n", cek[same / 2 - 1]);
  360.                     else printf("%d\n", cek[same / 2]);
  361.                 }
  362.             }
  363.         }
  364.     }
  365.  
  366.  
  367. }
  368.  
  369.  
Success #stdin #stdout 0s 5396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Sf9AEi
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!