finallyooooo.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "estruturas.h"

/* Segura o valor do último voo adicionado, auxiliando na escrita dos dados dos passageiros no arquivo.
 * É setada como " " propositalmente, para que possa ser corretamente utilizada na função save_pas, que
 * salva as informações dos passageiros inseridos em um arquivo txt. */
char atual_Plane_Pas[16] = " ";
long number_of_Pages; /* Variável auxiliar que guarda o número de páginas de voo contidas na árvore B. */
int number_of_Planes; /* Variável auxiliar que guarda o número de voos contidos no arquivo de dados do mesmo */
static int auxFatBal = 0;   /*Auxiliar de fator de balanceamento */

/* Método de busca de um passageiro na sua árvore AVL */
struct Nodo* search_Pas(char key_Pas[], struct Nodo* pNodo) {
    /* Enquanto o endereço for diferente de nulo e não tenha encontrado o passageiro solicitado */
    while((pNodo != NULL) && (strcmp(pNodo->info.pass, key_Pas))) {
        /* se a chave procurada for menor que o nó comparado, vai para seu filho a esquerda (lado onde estará a chave procurada, se ela existir) */
        if(strcmp(pNodo->info.pass, key_Pas) > 0)
            pNodo = pNodo->pLeft;
        else /* se a chave procurada for maior que o nó comparado, vai para seu filho a direita */
            pNodo = pNodo->pRight;
    }

    if (pNodo == NULL) /* caso o passageiro buscado não esteja na árvore AVL */
        printf ("ERRO\n");
    return pNodo; /* Irá retornar NULL (valor inicial do pNodo), caso nenhum passageiro seja encontrado */
}

/* Método responsável por balancear a árvore no sentido horário */
void balance_Horario(struct Nodo** pNodo) {
    struct Nodo* pAux = (*pNodo)->pLeft; /* Nodo auxiliar recebe o filho a esquerda no nodo recebido. */

    if(pAux->factor_Balance == 1) /* Se o fator de balanceamento do nodo auxiliar for igual a um. */
        balance_AntiHorario(&(*pNodo)->pLeft); /* Chama a função balancear anti horário passando o filho a esquerda do nodo atual. */

    pAux = (*pNodo)->pLeft; /* Nodo auxiliar recebe o filho a esquerda no nodo recebido. */

    if(pAux->factor_Balance == -1 || pAux->factor_Balance == 0) { /* Se o fator de balanceamento do auxiliar for igual a menos um ou zero. */
        (*pNodo)->pLeft = pAux->pRight; /* O filho a esquerda do nodo recebe o filho a direita da auxiliar. */
        pAux->pRight = (*pNodo); /* O filho a direita do auxiliar recebe o nodo. */
        (*pNodo)->factor_Balance = 0; /* O fator de balanceamento do nodo recebe zero. */
        (*pNodo) = pAux; /* O nodo recebe o auxiliar. */
    }

    (*pNodo)->factor_Balance = 0; /* O fator de balanceamento do nodo recebe zero. */
}

/* Método responsável por balancear a árvore no sentido anti-horário */
void balance_AntiHorario(struct Nodo** pNodo) {
    struct Nodo* pAux = (*pNodo)->pRight; /* Nodo auxiliar recebe o filho a direita no nodo recebido. */

    if(pAux->factor_Balance == -1) /* Se o fator de balanceamento do nodo auxiliar for igual a um. */
        balance_AntiHorario(&(*pNodo)->pRight); /* Chama a função balancear horário passando o filho a direita do nodo atual. */

    pAux = (*pNodo)->pRight; /* Nodo auxiliar recebe o filho a direita no nodo recebido. */

    if(pAux->factor_Balance == 1 || pAux->factor_Balance == 0) { /* Se o fator de balanceamento do auxiliar for igual a menos um ou zero. */
        (*pNodo)->pRight = pAux->pLeft; /* O filho a direita do nodo recebe o filho a esquerda da auxiliar. */
        pAux->pLeft = (*pNodo); /* O filho a esquerda do auxiliar recebe o nodo. */
        (*pNodo)->factor_Balance = 0; /* O fator de balanceamento do nodo recebe zero. */
        (*pNodo) = pAux; /* O nodo recebe o auxiliar. */
    }

    (*pNodo)->factor_Balance = 0; /* O fator de balanceamento do nodo recebe zero. */
}

/* método responsável por separar as informações da string contendo os dados do passageiro, para que possam ser utilizadas */
struct Passager convert_Data (char data[]) {
    struct Passager data_Struct; /* variável que armazenará todos os dados separados (será retornado posteriormente) */
    /* encontra primeira informação, que é o código voo */
    char auxCodVoo[16] = " "; /* variável auxiliar que recebe o código do voo (que tem o tamanho 15) */
    int i = 0;
    while (data[i] != '@') { /* o código do voo estará localizado antes do primeiro delimitador (@) da string */
        auxCodVoo[i] = data[i]; /* preenche a variável auxiliar com os primeiros 15 caracteres, que é o código do voo */
        i++;
    }
    strcpy (data_Struct.code_Plane, auxCodVoo); /* copia codigo do voo para seu respectivo campo */

    char auxPas[11] = " "; /* variável auxiliar que recebe o passaporte (que tem o tamanho 10) */
    i = i+1; /* posição do primeiro caracter depois do primeiro @ */
    int j = 0; /* controla as posições da variável auxiliar, iniciando com valor 0 (primeira posição) */

    /* encontra segunda informação, que é o passaporte */
    while (data[i] != '@') {
        auxPas[j] = data[i];
        i++;
        j++;
    }
    strcpy (data_Struct.pass, auxPas); /* copia passaporte para seu respectivo campo */

    char auxNome[101] = " "; /* variável auxiliar que recebe o nome (que tem o tamanho máximo de 100 caracteres) */
    i = i+1; /* posição do primeiro caracter depois do segundo @ */
    j = 0; /* controle da variável auxiliar */

    /* encontra terceira informação, que é o nome */
    while (data[i] != '@') {
        auxNome[j] = data[i];
        i++;
        j++;
    }
    strcpy (data_Struct.name, auxNome); /* copia nome para seu respectivo campo */

    char auxPol[4] = " "; /* variável auxiliar que recebe a poltrona (que tem o tamanho 3) */
    i = i+1; /* posição do primeiro caracter depois do terceiro @ */
    j = 0;

    /* encontra quarta informação, que é o poltrona */
    while (j < 4) {
        auxPol[j] = data[i];
        i++;
        j++;
    }
    strcpy (data_Struct.chair, auxPol); /* copia poltrona para seu respectivo campo */

    return data_Struct; /* retorna a estrutura corretamente preenchida */
}

/* Método responsável por armazenar as informações dos passageiros em um arquivo txt */
void save_Pas (char data[]) {
    struct Passager data_Struct = convert_Data (data); /* estrutura que armazena as informações do novo passageiro inserido */

    FILE *passager; /* variável do tipo FILE, para abrir (ou criar) arquivo texto de passageiros */
    passager = fopen ("passager.txt", "r+"); /* tenta ler arquivo texto de passageiro */
    if(passager == NULL) { /*Se o arquivo não existir */
        passager = fopen ("passager.txt", "w+"); /* cria novo arquivo txt para que possa ser armazenado os dados do passageiro */
    }

    fseek(passager, 0, SEEK_END); /* Move o cursor do arquivo para o endereço da página que o novo passageiro será incluido. */
    if (!strcmp (atual_Plane_Pas, " ") || strcmp (atual_Plane_Pas, data_Struct.code_Plane)) { /* Caso seja um voo diferente */
        fprintf(passager, "#%s#", data_Struct.code_Plane); /* preenche parte do arquivo com o codigo do voo, com os caracteres delimitadores # */
        /* define a variavel global atual_Plane_Pas como o código do novo voo inserido, desta forma,
         * caso haja mais passageiros deste mesmo voo, o codigo do voo será inserido no arquivo apenas uma vez. */
        strcpy (atual_Plane_Pas, data_Struct.code_Plane);
    }
    /* Escreve as informações do passageiro, delimitados pelo caracter @, no arquivo */
    fprintf(passager, "%s@%s@%s@", data_Struct.pass, data_Struct.name, data_Struct.chair);
    fclose (passager); /* fecha arquivo txt de passageiros */

}

/* Método responsável pela criação da árvore AVL de passageiros de um determinado voo */
int insert_Pas (char data[], struct Nodo** pNodo) {
    struct Passager data_Struct = convert_Data (data); /* converte string extraida no arquivo, para que seja possível utilizar o código do passageiro */

    /* pNodo se inicia com valor da raiz. Se não tiver raiz, ele será nulo inicialmente,
     * caso contrário, chama recursivamente até achar posição nula. */
    if((*pNodo) == NULL) {
        (*pNodo) = (struct Nodo*)malloc(sizeof(struct Nodo));
        (*pNodo)->info = data_Struct;
        (*pNodo)->pLeft = NULL;
        (*pNodo)->pRight = NULL;
        (*pNodo)->factor_Balance = 0;

        printf ("SUCESSO\n");
        /* verifica balanceamento da árvore */
        if(auxFatBal == 1)
            return 1;
        else
            if(auxFatBal == 2)
                return -1;
    }
    else {
        /* Caso o código do novo passageiro inserido seja maior que o nó pai */
        if(strcmp(data_Struct.pass, (*pNodo)->info.pass) > 0) {
            auxFatBal = 1;
            (*pNodo)->factor_Balance += insert_Pas(data, &(*pNodo)->pRight); /* chama a funação recursivamente, indo para o lado direito (maior) do provisório nó pai */

            if((*pNodo)->pRight->factor_Balance != 0) {
                (*pNodo)->factor_Balance ++; /* como o nó receberá um novo filho, cresce seu fator de balanceamento */

                if( (*pNodo)->factor_Balance > 1) /* verifica se é necessário fazer o balanceamento da árvore */
                    balance_AntiHorario(&(*pNodo));
            }

        }
        else {
            /* Caso o código do novo passageiro inserido seja menor que o nó pai */
            if(strcmp(data_Struct.pass, (*pNodo)->info.pass) < 0) {
                auxFatBal = 2;
                /* chama a funação recursivamente, indo para o lado esquerdo (menor) do provisório nó pai */
                (*pNodo)->factor_Balance += insert_Pas(data, &(*pNodo)->pLeft);

                if((*pNodo)->pLeft->factor_Balance != 0) {
                    /* incrementa fator balanceamento do lado esquerdo da árvore (que é reprensentado por um número negativo,
                     * permitindo o cálculo com o lado direito que é um número positivo) */
                    (*pNodo)->factor_Balance --;

                    if( (*pNodo)->factor_Balance < -1) { /* verifica se é necessário fazer o balanceamento da árvore */
                        balance_Horario(&(*pNodo));

                    }
                }
            }
        }
    }

    return 0;
}

/* Método responsável pela remoção de um passageiro na árvore AVL */
int remove_Pas(char key_Pas[], struct Nodo** pNodo) {

    if(strcmp(key_Pas, (*pNodo)->info.pass) > 0) { /* Se a chave para remover for maior que a chave do nodo atual. */
        auxFatBal = 2; /* Auxiliar de fator de balanceamento recebe 2. */
        (*pNodo)->factor_Balance += remove_Pas(key_Pas, &(*pNodo)->pRight); /* O fator de balanceamento do nodo atual é acrescentado o valor do retorno
                                                                               da chamada da função recursivamente da chave no nodo direito. */
        if((*pNodo)->pLeft != NULL && (*pNodo)->pLeft->factor_Balance == 0) { /* Se o nodo tiver filho a esquerda com fator de balanceamento igual a zero. */
            (*pNodo)->factor_Balance --; /* O fator de balanceamento do nodo é decrementado. */

            if( (*pNodo)->factor_Balance < -1) /* Se o fator de balanceamento do nodo for menor que menos 1. */
                balance_Horario(&(*pNodo)); /* Chama a função balancear no sentido horário no nodo. */

        }
    }
    else {
        if(strcmp(key_Pas, (*pNodo)->info.pass) < 0) { /* Se a chave para remover for menor que a chave do nodo atual. */
            auxFatBal = 1; /* Auxiliar de fator de balanceamento recebe 2. */
            (*pNodo)->factor_Balance += remove_Pas(key_Pas, &(*pNodo)->pLeft); /* O fator de balanceamento do nodo atual é acrescentado o valor do retorno
                                                                               da chamada da função recursivamente da chave no nodo esquerdo. */

            if((*pNodo)->pRight != NULL && (*pNodo)->pRight->factor_Balance == 0) { /* Se o nodo tiver filho a direita com fator de balanceamento igual a zero. */
                (*pNodo)->factor_Balance ++; /* O fator de balanceamento do nodo é acrementado. */

                if( (*pNodo)->factor_Balance > 1) /* Se o fator de balanceamento do nodo for maior que 1. */
                    balance_Horario(&(*pNodo)); /* Chama a função balancear no sentido anti horário no nodo. */

            }
        }
        else { /* A chave foi encontrada para ser removida. */
            if((*pNodo)->pRight == NULL && (*pNodo)->pLeft == NULL) { /* Se o nodo não tiver filhos. */
                free(*pNodo); /* Limpa o nodo da memória. */
                (*pNodo) = NULL; /* Nodo recebe vazio. */

                printf ("SUCESSO\n"); /* Feedback. */

                if(auxFatBal == 1) /* Se a auxiliar é igual a 1. */
                    return 1;

                else
                    if(auxFatBal == 2) /* Se a auxiliar é igual a 2. */
                        return -1;
            }
            else if((*pNodo)->pLeft == NULL) { /* Se o nodo tiver apenas filhos a direita. */
                struct Nodo* pAux = (*pNodo); /* Auxiliar recebe o nodo. */
                (*pNodo) = (*pNodo)->pRight; /* Nodo recebe seu filho a direita. */
                free(pAux); /* Limpa a auxiliar da memoria. */
                pAux = NULL; /* Auxiliar recebe vazio. */

                printf ("SUCESSO\n"); /* Feedback. */

                if(auxFatBal == 1) /* Se a auxiliar é igual a 1. */
                    return 1;

                else
                    if(auxFatBal == 2) /* Se a auxiliar é igual a 2. */
                        return -1;
                }
                else if((*pNodo)->pRight == NULL) { /* Se o nodo tiver apenas filhos a esquerda. */
                    struct Nodo* pAux = (*pNodo); /* Auxiliar recebe o nodo. */
                    (*pNodo) = (*pNodo)->pLeft; /* Nodo recebe seu filho a esquerda. */
                    free(pAux); /* Limpa a auxiliar da memoria. */
                    pAux = NULL; /* Auxiliar recebe vazio. */

                    printf ("SUCESSO\n"); /* Feedback. */

                    if(auxFatBal == 1) /* Se a auxiliar é igual a 1. */
                        return 1;

                    else
                    if(auxFatBal == 2) /* Se a auxiliar é igual a 2. */
                        return -1;
                }
                else { /* Caso o nodo tenha filho direito e esquerdo. */
                    (*pNodo)->info = search_Biggest_Left((*pNodo)->pLeft)->info; /* As informações do nodo recebe as informações do maior nodo a esquerda. */
                    return remove_Pas(key_Pas, &(*pNodo)->pLeft); /* Chama a função remover recursivamente. */
                }
            }
        }
    return 0;
}

struct Nodo* search_Biggest_Left(struct Nodo* pNodo) {

    while(pNodo->pRight != NULL)
        pNodo = pNodo->pRight;

    return pNodo;
}

void cut_Tree (struct Nodo* pNodo) {

    if (pNodo->pLeft == NULL && pNodo->pRight == NULL)
        free (pNodo);

    if (pNodo->pLeft != NULL)
        cut_Tree (pNodo->pLeft);

    if (pNodo->pRight != NULL)
        cut_Tree (pNodo->pRight);

}

void save_Page(FILE *p, long RRN_Page, struct Page *page) {
    if(p != NULL) { /*Se a tentativa de abrir o arquivo foi um sucesso. */
        fseek(p, RRN_Page, SEEK_SET); /* Move o cursor do arquivo para o endereço da página. */
        fwrite(page, sizeof(struct Page), 1, p); /* Escreve a página passada no arquivo. */
    }
    else {
        printf("ERRO\n");
    }
}

void load_Page(FILE *p, long RRN_Page, struct Page *page) {
    if (p != NULL) { /* Se a tentativa de abrir o arquivo foi um sucesso. */
        fseek(p, RRN_Page, SEEK_SET); /* Move o cursor do arquivo para o endereço da página. */
        fread(page, sizeof(struct Page), 1, p); /* Carrega a página do arquivo para a estrutura page. */
    }
    else {
        printf("ERRO\n");
    }
}

void createNewPage(struct Page *page) {
    page->num_Plane = 0;
    int i;
    for(i = 0; i < MAX_INDEX + 1; i++) {
        if( i < MAX_INDEX) {
            strcpy(page->planes[i].key_Plane, "####");
            page->planes[i].RRN_Plane = -1;
        }
        page->RRN_Son[i] = -1;
    }
}
void update_Root(long new_Root) {
    FILE *p;
    p = fopen("index.dat", "wb");
    if(p != NULL) {
        fseek(p, 0, 0);
        fwrite(&new_Root, sizeof(long), 1, p);
    }
    else {
        printf("ERRO\n");
    }
    fclose(p);
}

long load_RNN_Root(FILE *p) {
    long root;
    fseek(p, 0, 0); /* Mover o cursor para o início do arquivo. Que é onde o RRN da raiz se localiza. */
    fread(&root, sizeof(long), 1, p); /* Carrega o RRN da raiz na variável root. */
    return root; /* Retorna a raiz encontrada. */
}

void split(struct Page *atual_Page, struct Page *new_Page, struct Index promoter, long right_Son_Page) {
    struct Index planesSplit[MAX_INDEX + 1]; /* Vetor auxiliar. */
    long RRNSplit[MAX_INDEX + 1]; /* Vetor auxiliar. */

    int i = 0; /* Indice para começar a percorrer/preencher os vetores auxiliares. */
    while(strcmp(promoter.key_Plane, atual_Page->planes[i].key_Plane) > 0)
    { /* Enquanto o indice a ser inserido for maior do que o na posição i da página atual. */
        RRNSplit[i] = atual_Page->RRN_Son[i]; /* Insere um filho da página atual no vetor auxiliar. */
        planesSplit[i] = atual_Page->planes[i]; /* Insere um indice da página atual no vetor auxiliar. */
        i++; /* Acrescimo do indice. */
    }
    RRNSplit[i] = atual_Page->RRN_Son[i]; /* Insere um filho da página atual no vetor auxiliar. */
    planesSplit[i] = promoter; /* Insere o novo indice no vetor auxiliar. */
    i++; /* Acrescimo do indice. */
    RRNSplit[i] = right_Son_Page; /* Insere um filho a direita no vetor auxiliar. */
    while(i < MAX_INDEX + 1) { /* Enquanto o indice for menor que o número máximo de index mais um.  */
        RRNSplit[i + 1] = atual_Page->RRN_Son[i-1]; /* Insere um filho da página atual no vetor auxiliar. */
        planesSplit[i] = atual_Page->planes[i-1]; /* Insere um indice da página atual no vetor auxiliar. */
        i++; /* Acrescimo do indice. */
    }


    /* Agora que já está tudo no vetor auxiliar, vamos passar para as duas páginas. */

    atual_Page->num_Plane = 0; /* "Esvaziando a página para começar a colocar os indices. */
    new_Page->num_Plane = 0; /* "Esvaziando a página para começar a colocar os indices. */
    createNewPage(atual_Page); /* Inicializando a página atual. */
    createNewPage(new_Page); /* Inicializando a nova página. */

    int pos_Promoter = floor((MAX_INDEX + 1) / 2); /* Calculando em qual posição do vetor está o indice que deve ser promovido. */
    promoter = planesSplit[pos_Promoter]; /* O promovido é buscado do vetor auxiliar. */


    for(i = 0; i < pos_Promoter; i++) { /* Enquanto o indice for menor que a posição da chave que foi promovida. */
        atual_Page->num_Plane ++; /* Acrescenta um na quantidade de voos da página. */
        atual_Page->planes[i] = planesSplit[i]; /* Chave i da página recebe a chave i do vetor auxiliar. */
        atual_Page->RRN_Son[i] = RRNSplit[i]; /* Filho i da página recebe o filho i do vetor auxiliar. */
    }
    atual_Page->RRN_Son[i] = RRNSplit[i]; /* Filho i da página recebe o filho i do vetor auxiliar. */
    i++; /* Acrescimo do indice. */
    for(; i < MAX_INDEX + 1; i++) { /* ENquanto o indice for menor que a quantidade máxima de chaves em uma página mais um. */
        new_Page->num_Plane ++; /* Acrescenta um na quantidade de voos da página. */
        new_Page->planes[i - pos_Promoter - 1] = planesSplit[i];
        new_Page->RRN_Son[i - pos_Promoter - 1] = RRNSplit[i-1];
    }

    new_Page->RRN_Son[i - pos_Promoter - 1] = RRNSplit[i - 1];

}

void save_Plane (char data[]) {

    struct Plane plane;
    int i = 0;

    /* Separando a string com as informacoes do voo
     * (todos são de tamanho fixo, o que justifica o
     * valor utilizado em cada for) */
    char cod1[15];
    while (i < 15) {
        cod1[i] = data[i];
        i++;
    }
    strcpy(plane.code_Plane, cod1);  /* codigo voo */

    char cod2[4];
    for(i = 0; i < 3; i++) {
        cod2[i] = data[i + 16];
    }
    strcpy(plane.arrival_Airport, cod2); /* aeroporto partida */

    char cod3[4];
    for(i = 0; i < 3; i++) {
        cod3[i] = data[i + 20];
    }
    strcpy(plane.dest_Airport, cod3);  /* aeroporto chegada */

    char cod4[5];
    for(i = 0; i < 5; i++) {
        cod4[i] = data[i + 24];
    }
    strcpy(plane.plane_Time, cod4); /* horario */

    char cod5[3];
    for(i = 0; i < 2; i++) {
        cod5[i] = data[i + 30];
    }
    strcpy(plane.enterprise, cod5); /* companhia aerea */

    FILE *p;
    p = fopen ("data.dat", "wb");
    if(p != NULL) { /*Se a tentativa de abrir o arquivo foi um sucesso. */
        fseek(p, 1, SEEK_END); /* Move o cursor do arquivo para o endereço da página. */
        fwrite(&plane, sizeof(struct Plane), 1, p); /* Escreve a página passada no arquivo. */
    }
    else {
        printf("ERRO\n");
    }
    fclose (p);
}

int insert_Plane(FILE *p, long RRN_Atual_Page, struct Index key_to_Insert, char data[], struct Index **promoter, long **right_Son_Page) {
    strcpy (atual_Plane_Pas, " "); /* Novo voo (no arquivo do passageiro) */
    struct Page atual_Page; /* Página atual. */
    struct Page new_Page; /* Nova página caso precise quando for chamado o split. */
    int value_Return;

    if(RRN_Atual_Page > -1) { /* Se a página existe. */
        load_Page(p, RRN_Atual_Page, &atual_Page); /* Carregar a página do disco para a estrutura atual_Page. */
        int pos = atual_Page.num_Plane; /* Variavel po é inicializada com o número de voos na página. */
        int i = 0; /* Indice. */
        while( i < atual_Page.num_Plane) { /* Enquanto o indice for menor que o número de voos na página. */
            if(strcmp(key_to_Insert.key_Plane, atual_Page.planes[i].key_Plane) == 0) { /* Se a chave a ser inserida é igual
                                                                                          a chave na posição i da página.   */
                printf("ERRO\n"); /* Feedback. */
                return -1; /* Não foi possível a inserção. */
            }

            if(strcmp(key_to_Insert.key_Plane, atual_Page.planes[i].key_Plane) < 0) { /* Se a chave a ser inserida é menor
                                                                                         do que a chave na posição i da página.
                                                                                         Ou seja, a chave deveria estar lá.    */
                pos = i; /* Posição recebe o indice. */
                i = MAX_INDEX; /* Terminando o while para pegar a posição exata. */
            }
            i++; /* Acrescimo do indice. */
        }
        value_Return = insert_Plane(p, atual_Page.RRN_Son[pos], key_to_Insert, data, promoter, right_Son_Page); /* Chama a função inserir na página do filho na posição que deveria estar. */
        if(value_Return < 2) { /* Se o retorno for não promoção ou erro */
            return value_Return; /* Repassa o valor do retorno. */
        }
        else {  /* Se o retorno for promoção. */
            if(atual_Page.num_Plane < MAX_INDEX) { /* Se tem espaço para adicionar outro índice na página. */
                atual_Page.num_Plane ++; /* Aumenta o número de voos na página. */
                if(pos == atual_Page.num_Plane - 1) { /* Se o elemento deve ser inserido na última posição livre. */
                    atual_Page.planes[atual_Page.num_Plane - 1] = **promoter; /* O voo da página recebe o promovido. */
                    atual_Page.RRN_Son[atual_Page.num_Plane] = **right_Son_Page; /* O filho a direita do voo adicionado recebe o filho a direita do promovido. */
                    save_Page(p, RRN_Atual_Page, &atual_Page); /* Salva a página atual. */
                }
                else {  /* Se o elemento não será inserido na última posição livre. */
                    int j = atual_Page.num_Plane - 1; /* O indice j recebe a quantidade de voos na página atual menos 1. */
                    while(j > pos) /* Enquanto o indice for maior que a posição que o elemento deve ser inserido. */
                    {  /* Ordena a página. */
                        atual_Page.planes[j] = atual_Page.planes[j-1];  /* Arrasta um voo para frente. */
                        atual_Page.RRN_Son[j] = atual_Page.RRN_Son[j-1]; /* Arrasta um filho para frente. */
                        j--; /* Decrescimo do indice. */
                    }
                    atual_Page.planes[j] = **promoter; /* A posição que ele devia ocupar recebe o promovido. */
                    atual_Page.RRN_Son[j+1] = **right_Son_Page; /* O filho a direita do voo inserido recebe o filho a direita do promovido. */
                    save_Page(p, RRN_Atual_Page, &atual_Page); /* Salva a página atual. */
                }
                return 1; /* Retorna não promoção. */
            }
            else { /* Se não tem espaço para adicionar um novo elemento na página. */
                split(&atual_Page, &new_Page, **promoter, **right_Son_Page); /* Chama a função split passando todos os parâmetros necessários.*/
                long free_Pos = sizeof(long) + (number_of_Pages * sizeof(struct Page)); /* Posição vaga para inserir nova página */
                *right_Son_Page = &free_Pos; /* O filho a direita recebe a posição livre. */
                number_of_Pages ++; /* Aumenta o número de páginas. */
                pino(p); /* Chamando função auxiliar. */
                save_Page(p, free_Pos, &new_Page); /* Salva a nova página na posição livre. */
                pino(p); /* Chamando função auxiliar. */
                save_Page(p, RRN_Atual_Page, &atual_Page); /* Salva a página atual atualizada. */
                pino(p); /* Chamando função auxiliar. */
                return 2; /* Retorna promoção. */
            }
        }
    }
    else { /* Se chegar a uma página que não existe. */
        *promoter = &key_to_Insert; /* Promovido recebe a chave que está sendo inserida. */
        return 2; /* Retorna promoção. */
    }
    return 1; /* Retorna não promoção. */
}

void insert_Plane_Driver(char data[]) {
    FILE *p;
    p = fopen("index.dat", "rb+"); /* Abre o arquivo para leitura e escrita. */
    if(p == NULL) { /* Se o arquivo não existe. */
        p = fopen("index.dat", "wb+"); /* Tenta criar um arquivo para escrita e leitura. */
        if(p != NULL) { /* Se foi possível criar o arquivo. */
            long root = sizeof(long); /* Define o lugar onde a raiz vai ficar. */
            fwrite(&root, sizeof(long), 1, p); /* Inicia a raiz na primeira posição. */
            struct Page page; /* Cria a estrutura da página que será inserida. */
            createNewPage(&page); /* Inicializa a página. */
            fwrite(&page, sizeof(struct Page), 1, p); /* Inseri uma página vazia no arquivo que será a raiz. */
            number_of_Pages = 1; /* Número de páginas na árvore = 1. */
            number_of_Planes = 0; /* Como a árvore acabou de ser criada não existe voos. */
        }
        else {
            printf("ERRO\n"); /* Feedback. */
        }
    }
    long root;
    root = load_RNN_Root(p); /* Carrega o valor da raiz para a variável root. */
    struct Index key_to_Insert; /* Criando o índice que vai ser inserido. */
    key_to_Insert.RRN_Plane = number_of_Planes + 1; /* O endereço no arquivo de dados será o número de voos existentes mais . */

    /* Capturando o código da string recebida. */
    char codigo[15];
    int i = 0;
    while (i < 15) {
        codigo[i] = data[i];
        i++;
    }
    strcpy(key_to_Insert.key_Plane, codigo);

    struct Index *promoter; /* Criando o indice promoter que será mandado por referência. */
    long *right_Son_Page; /* Criando o filho a direita que será mandado por referência. */

    promoter = NULL; /* Inicializando o promoter. */
    long aux = -1; /* Criando auxiliar para inicializar o filho a direita. */
    right_Son_Page = &aux; /* Inicializando o filho. */
    int value_return = insert_Plane(p, root, key_to_Insert, data, &promoter, &right_Son_Page); /* Chama o metodo inserir na raiz. */
    if(value_return == 2) { /* Caso houve promoção. */
        struct Page newbie_Page; /* Criando uma nova página pro promovido. */
        struct Page gatona_Lindsay; /* Página auxiliar. */
        struct Page crazy_Sierra; /* Página auxiliar. */
        createNewPage(&newbie_Page); /* Inicializando a nova página. */
        createNewPage(&gatona_Lindsay); /* Inicializando página auxiliar. */
        createNewPage(&crazy_Sierra); /* Inicializando página auxiliar. */
        newbie_Page.num_Plane = 1; /* Número de voos na nova página recebe um. */
        newbie_Page.planes[0] = *promoter; /* O voo da nova página recebe o promoter. */
        newbie_Page.RRN_Son[0] = root; /* O filho a esquerda do promovido recebe a antiga raiz. */
        long tyler = *right_Son_Page; /* Criando auxiliar para salvar o filho a direita. */
        newbie_Page.RRN_Son[1] = tyler; /* Filho a direita do promovido recebe o filho a direta do promovido. */

        long free_Pos = sizeof(long) + (number_of_Pages * sizeof(struct Page)); /* Posição vaga para inserir nova página */
        number_of_Pages ++; /* Acrescimo do número de páginas. */
        update_Root(free_Pos); /* Atualizando a raiz. */
        load_Page(p, tyler, &gatona_Lindsay); /* Carrega a página auxiliar. */
        load_Page(p, root, &crazy_Sierra); /* Carrega a página auxiliar. */
        save_Page(p, free_Pos, &newbie_Page); /* Salva a nova página. */
        save_Page(p, tyler, &gatona_Lindsay); /* Salva a página auxiliar. */
        save_Page(p, root, &crazy_Sierra); /* Salva a página auxiliar. */
        printf ("SUCESSO\n"); /* Feedback. */
        number_of_Planes ++; /* Número de voos aumenta. */
        save_Plane(data); /* Chama a função que salva os dados do voo. */
    }
    else if (value_return == 1) { /* Caso não houver promoção. */
        printf ("SUCESSO\n");  /* Feedback. */
        save_Plane(data); /* Chama a função que salva os dados do voo. */
        number_of_Planes ++; /* Número de voos aumenta. */
    }
    fclose(p); /* Fecha o arquivo que foi aberto para escrita e leitura do indice. */
}

void pino(FILE *p) {
    struct Page page;
    load_Page(p, 0, &page);
}

void print_Index_Tree(FILE *p, long RRN) {

    if(RRN > 0) { /* Se a página existir. */
        struct Page page; /* Declaração de uma página. */
        load_Page(p, RRN, &page); /* Carregando a página do disco para a memória. */
        printf("%ld|%d", RRN, page.num_Plane); /* Imprime o RRN da página e a quantidade de voos na mesma. */
        int i; /* Declaração de um indice. */
        for(i = 0; i < MAX_INDEX; i++) {
            printf("|%ld|%s,%ld", page.RRN_Son[i], page.planes[i].key_Plane, page.planes[i].RRN_Plane); /* Imprime os RRN das páginas filhas, as chaves e o RRN das chaves no arquivo de dados. */
        }
        printf("|%ld|\n", page.RRN_Son[i]); /* Imprime o RRN de umas das páginas filhas. */
        for(i = 0; i < MAX_INDEX + 1; i++) {
            print_Index_Tree(p, page.RRN_Son[i]); /* Chama a função recursivamente em todos os filhos. */
        }
    }

}

void print_Plane(long RRN) {
    struct Plane plane; /* Declaração de um voo. */
    FILE *l; /* Declaração do ponteiro de arquivo. */
    l = fopen("data.dat", "rb"); /* Abre o arquivo de dados. */
    if(l != NULL) { /* Se a tentativa de abrir o arquivo for sucedida. */
        fseek(l, RRN * sizeof(struct Plane), SEEK_SET); /* Move o cursor para o início dos dados da página. */
        fread(&plane, sizeof(struct Plane), 1, l); /* Carrega a página do disco para a estrutura da memoria. */
        printf("%s %s %s %s %s\n", plane.code_Plane, plane.arrival_Airport, plane.dest_Airport, plane.plane_Time, plane.enterprise); /* Imprime os dados do voo. */
        fclose(l); /* Fecha o arquivo. */
    }
    else {
        printf("ERRO\n"); /* Feedback. */
    }
}


int search_Plane(FILE *p, long RRN_Atual_Page, char key_Plane[]) {
    if(RRN_Atual_Page > 0) { /* Se a página existe. */
        struct Page page; /* Declaração de uma nova página. */
        load_Page(p, RRN_Atual_Page, &page); /* Carregando a página do disco para a memória. */
        int i = 0; /* Declaração do indice. */
        int pos = page.num_Plane; /* Inicializando a variavel pos com a quantidade de voos que tem na página. */
        while(i < page.num_Plane) { /* Enquanto o indice for menor que a quantidade de voos na página. */
            if(strcmp(key_Plane, page.planes[i].key_Plane) == 0) { /* Se a chave a ser inserida é igual
                                                                                          a chave na posição i da página.   */
                print_Plane(page.planes[i].RRN_Plane); /* Chama a função imprimir que irá imprimir os dados do voo. */
                return 1; /* Retorna sucesso. */
            }
            if(strcmp(key_Plane, page.planes[i].key_Plane) < 0) { /* Se a chave a ser inserida é menor
                                                                                         do que a chave na posição i da página.
                                                                                         Ou seja, a chave deveria estar lá.    */
                pos = i; /* A posição que deveria estar recebe o indice atual. */
                i += MAX_INDEX + 2; /* Terminando o while para pegar a posição exata. */
            }
            i++; /* Acresimo do indice. */
        }
        search_Plane(p, page.RRN_Son[pos], key_Plane); /* Chama a função buscar recursivamente na página do filho de onde a chave deveria estar. */
    }
    return 0; /* Retorna erro. */
}

int remove_Plane(FILE *p, long RRN_Atual_Page, char key_Plane[], int changing, struct Index *changer_Plane, int *underflow) {
    struct Page atual_Page;
    if(RRN_Atual_Page > -1) { /* Se o RRN da página existe. */
        load_Page(p, RRN_Atual_Page, &atual_Page); /* Carregar a página do disco para a estrutura atual_Page. */
        int pos = atual_Page.num_Plane; /* Inicializa pos com a quantidade de voos na página. */
        int i = 0; /* Variável índice. */

        while( i < atual_Page.num_Plane) { /* Enquanto o indice for menor que a quantidade de voos. */
            if(strcmp(key_Plane, atual_Page.planes[i].key_Plane) == 0) { /* Se a chave a ser inserida é igual
                                                                            a chave na posição i da página.   */
                if(atual_Page.num_Plane > ORDER) { /* Se a página tem mais voos do que a ordem. Não causando underflow.*/
                    if(atual_Page.RRN_Son[i+1] < 0) { /* Se o voo que será removido não tem filhos a direita. */
                        atual_Page.num_Plane --; /* Menos um voo na página, pois esse poderá ser removido. */
                        if(i == atual_Page.num_Plane) {
                            /* Depois trocar para apenas um if. */
                        }
                        else {
                            while(i < atual_Page.num_Plane) { /* Enquanto o indice for menor que o número de voos. */
                                atual_Page.planes[i] = atual_Page.planes[i+1]; /* Arrasta o voo uma posição para trás. */
                                atual_Page.RRN_Son[i] = atual_Page.RRN_Son[i+1]; /* Arrasta o RRN do filho uma posição para trás. */
                                i++; /* Incremento do indice. */
                            }
                        }
                        if(changing == 1) { /* Se estiver no modo troca. */
                            changer_Plane = &atual_Page.planes[i]; /* O voo auxiliar para troca recebe o que será removido. */
                        }
                        strcpy(atual_Page.planes[i].key_Plane, "###"); /* Preenche a chave do voo removido com ###. */
                        /*pino(p);*/
                        save_Page(p, RRN_Atual_Page, &atual_Page); /* Salva a página atualizada. */
                        /*pino(p);*/
                        return 1;
                    }
                    else { /* Se o voo tem filhos a direita. */

                    }
                }
            }

            if(strcmp(key_Plane, atual_Page.planes[i].key_Plane) < 0) { /* Se a chave a ser inserida é menor
                                                                           do que a chave na posição i da página.
                                                                           Ou seja, a chave deveria estar lá.    */
                pos = i; /* Pos receberá a posição que a chave deveria estar. */
                i = MAX_INDEX; /* Terminando o while para pegar a posição exata. */
            }
            i++; /* Acrescimo do indice. */
        }
        remove_Plane(p, atual_Page.RRN_Son[pos], key_Plane, 0, changer_Plane, underflow); /* Chama a função remover recursivamente na página do filho de onde a chave deveria estar. */
    }
    else {
        return 0;
    }
    return 1;
}


void remove_Plane_Driver(char key_Plane[]) {
    FILE *p; /* Criação de ponteiro tipo arquivo. */
    p = fopen("index.dat", "rb+"); /* Abrindo o arquivo de indices para leitura e escrita. */

    if(p != NULL) { /* Se o arquivo existe. */
        long root;
        int value_Return;

        root = load_RNN_Root(p); /* Carrega a raiz na variável root. */
        struct Index *changer_Plane = NULL; /* Estruturas auxiliar que irá guardar a chave que será substuida caso necessário. */
        value_Return = remove_Plane(p, root, key_Plane, 0, changer_Plane, 0); /* Chama a função remover na raiz para remover a chave. */
        if(value_Return > 0) {
            printf("SUCESSO\n"); /* Feedback. */
        }
        else {
            printf("ERRO\n"); /* Feedback. */
        }
    }
    else {
        printf("ERRO\n"); /* Feedback. */
    }
    fclose(p);
}