fork download

copy

int insert(int n, struct node *start)
{
//if node doesnt exist then add it to the tree otherwise increase amount of keys
 
//if tree is empty add root
    if (root == NULL)
    {
        root = (struct node*)malloc(sizeof *root);
        root->value = n;
        root->keys_amount=0;
        root->left = NULL;
        root->right = NULL;
        root->up = NULL;
 
    }
    else if(search(root,n)!=NULL)
    {
        struct node *tmp = search(root, n);
        tmp->keys_amount += 1;
        return 0;
    }
//if value is lower than root val then go to left son
    else if(n < start->value)
    {
//if left son exist then apply function insert for it
    if(start->left != NULL)
    {
        insert(n,start->left);
    }
//if it doesnt exist then create 
    else
    {
    struct node *new = (struct node*)malloc(sizeof *root);
    new->value = n;
    new->keys_amount=0;
    new->left = NULL;
    new->right = NULL;
    new->up = start;
    start->left=new;
    correct_tree(new);
    }
    }
//if new value is higher than root
    else
    {
//if right son exist then apply function for it
    if(start->right!=NULL)
    {
    insert(n,start->right);
    }
//if it doesnt exist create new one
    else
    {
    struct node *new = (struct node*)malloc(sizeof *root);
    new->value = n;
    new->keys_amount=0;
    new->left = NULL;
    new->right = NULL;
    new->up = start;
    start->right=new;
    correct_tree(new);
    }
    }
    return 0;
}
 
//////////////////////////////////////////////////////////////////
 
void correct_tree(struct node *start)
{
    struct node *tmp = (struct node*)malloc(sizeof *root);
    start->color = 'R';
    while((start != root) && (start->up->color == 'R'))
    {
        if(start->up == start->up->up->left)
        {
            tmp = start->up->up->right; //uncle of start for tmp
            if(tmp->color == 'R') //case 1
            {
                start->up->color = 'B';
                tmp->color = 'B';
                start->up->up->color='R';
                start = start->up->up;
                continue;
            }
            if(start == start->up->right) //case 2
            {
                start = start->up;
                rot_L(start);
            }
            start->up->color = 'B'; //case3
            start->up->up->color = 'R';
            rot_R(start->up->up);
            break;
        }
        else //mirror cases
        {
            tmp = start->up->up->left;
            if(tmp->color == 'R') //case 1
            {
                start->up->color = 'B';
                tmp->color = 'B';
                start->up->up->color='R';
                start = start->up->up;
                continue;
            }
            if(start == start->up->left) //case 2
            {
                start = start->up;
                rot_R(start);
            }
            start->up->color = 'B'; //case3
            start->up->up->color = 'R';
            rot_L(start->up->up);
            break;
        }
    }
    root->color = 'B';
}
 
//////////////////////////////////////////////////////////////
 
void rot_L(struct node *start)
{
    struct node *tmp = (struct node*)malloc(sizeof *root);
    struct node *tmp2 = (struct node*)malloc(sizeof *root);
    tmp = start->right;
    if(tmp != NULL)
    {
        tmp2 = start->up;
        start->right = tmp->left;
        if(start->right != NULL)
            start->right->up = start;
        tmp->left = start;
        tmp->up = tmp2;
        start->up = tmp;
        if(tmp2 != NULL)
        {
            if(tmp2->left == start)
                tmp2->left = tmp;
            else
                tmp2->right = tmp;
        }
        else root = tmp;
    }
 
}

prog.c:1:26: warning: ‘struct node’ declared inside parameter list will not be visible outside of this definition or declaration
 int insert(int n, struct node *start)
                          ^~~~
prog.c: In function ‘insert’:
prog.c:6:9: error: ‘root’ undeclared (first use in this function)
     if (root == NULL)
         ^~~~
prog.c:6:9: note: each undeclared identifier is reported only once for each function it appears in
prog.c:6:17: error: ‘NULL’ undeclared (first use in this function)
     if (root == NULL)
                 ^~~~
prog.c:8:30: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
         root = (struct node*)malloc(sizeof *root);
                              ^~~~~~
prog.c:8:30: warning: incompatible implicit declaration of built-in function ‘malloc’
prog.c:8:30: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
prog.c:16:13: warning: implicit declaration of function ‘search’ [-Wimplicit-function-declaration]
     else if(search(root,n)!=NULL)
             ^~~~~~
prog.c:19:12: error: dereferencing pointer to incomplete type ‘struct node’
         tmp->keys_amount += 1;
            ^~
prog.c:33:38: warning: incompatible implicit declaration of built-in function ‘malloc’
     struct node *new = (struct node*)malloc(sizeof *root);
                                      ^~~~~~
prog.c:33:38: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
prog.c:40:5: warning: implicit declaration of function ‘correct_tree’ [-Wimplicit-function-declaration]
     correct_tree(new);
     ^~~~~~~~~~~~
prog.c:54:38: warning: incompatible implicit declaration of built-in function ‘malloc’
     struct node *new = (struct node*)malloc(sizeof *root);
                                      ^~~~~~
prog.c:54:38: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
prog.c: At top level:
prog.c:69:26: warning: ‘struct node’ declared inside parameter list will not be visible outside of this definition or declaration
 void correct_tree(struct node *start)
                          ^~~~
prog.c:69:6: warning: conflicting types for ‘correct_tree’
 void correct_tree(struct node *start)
      ^~~~~~~~~~~~
prog.c:40:5: note: previous implicit declaration of ‘correct_tree’ was here
     correct_tree(new);
     ^~~~~~~~~~~~
prog.c: In function ‘correct_tree’:
prog.c:71:38: warning: incompatible implicit declaration of built-in function ‘malloc’
     struct node *tmp = (struct node*)malloc(sizeof *root);
                                      ^~~~~~
prog.c:71:38: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
prog.c:71:53: error: ‘root’ undeclared (first use in this function)
     struct node *tmp = (struct node*)malloc(sizeof *root);
                                                     ^~~~
prog.c:72:10: error: dereferencing pointer to incomplete type ‘struct node’
     start->color = 'R';
          ^~
prog.c:89:17: warning: implicit declaration of function ‘rot_L’ [-Wimplicit-function-declaration]
                 rot_L(start);
                 ^~~~~
prog.c:93:13: warning: implicit declaration of function ‘rot_R’ [-Wimplicit-function-declaration]
             rot_R(start->up->up);
             ^~~~~
prog.c: At top level:
prog.c:123:19: warning: ‘struct node’ declared inside parameter list will not be visible outside of this definition or declaration
 void rot_L(struct node *start)
                   ^~~~
prog.c:123:6: warning: conflicting types for ‘rot_L’
 void rot_L(struct node *start)
      ^~~~~
prog.c:89:17: note: previous implicit declaration of ‘rot_L’ was here
                 rot_L(start);
                 ^~~~~
prog.c: In function ‘rot_L’:
prog.c:125:38: warning: incompatible implicit declaration of built-in function ‘malloc’
     struct node *tmp = (struct node*)malloc(sizeof *root);
                                      ^~~~~~
prog.c:125:38: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
prog.c:125:53: error: ‘root’ undeclared (first use in this function)
     struct node *tmp = (struct node*)malloc(sizeof *root);
                                                     ^~~~
prog.c:127:16: error: dereferencing pointer to incomplete type ‘struct node’
     tmp = start->right;
                ^~
prog.c:128:15: error: ‘NULL’ undeclared (first use in this function)
     if(tmp != NULL)
               ^~~~

Standard output is empty