Laboratório No. 04



Objetivo:

O objetivo deste laboratório é a implementação das rotinas de manipulação de dados em disco para árvores B, considerando tanto a inserção quanto a remoção de dados. Você poderá se basear nas funções abaixo apresentadas ou fazer outra implementação.



Implementação:

Descrição de um nó

A declaração abaixo permite que a ordem da árvore seja escolhida em tempo de execução. Cada nó, poderá ter no mínimo ord e no máximo 2 * ord chaves. Os vetores de chaves e apontadores serão alocados dinamicamente de acordo com a ordem da árvore. Uma posição a mais pode ser alocada para facilitar a implementação da operação de inserção. Além disso cada um dos nós possuirá um identificador único que permitirá a definição da quantidade de bytes que será percorrida desde o início do arquivo para achar os dados de um nó filho.

typedef struct no* ap_no;

typedef struct arv_B Arv_B;
struct arv_B {
  ap_no m_pRoot;   /* Apontador para a árvore propriamente dita */
  int m_nOrd;      /* Ordem da árvore                           */
  int m_nNumPages; /* Número de páginas na árvore               */
};

struct no {
  int m_nIndex;         /* Índice do nó */
  int m_nSize;          /* Número de chaves válidas no nó           */
  int* m_pKeys;         /* Endereço inicial do vetor de chaves      */
  ap_no* m_pChildren;   /* Endereço inicial do vetor de apontadores para os nós filhos */
};

Exemplos (ordem 2)



Funções a serem implementadas

  1. void inicia_arvore(Arv_B *t, int ord);

    Inicia uma árvore B de ordem ord. O primeiro nó a ser armazenado no arquivo será utilizado para armazenar informações gerais da árvore.

  2. void escreve(Arv_B t);

    Escreve os elementos de t em ordem crescente. Deixa uma linha em branco caso t esteja vazia.

  3. int insere(Arv_B *t, int v);

    Insere a chave v na árvore t; retorna 1 caso a inserção tenha sido bem sucedida ou 0 caso a chave já esteja presente na árvore.

  4. void insere_disco(Arv_B *t, int pos, ap_no no, char * fileName);

    Insere o nó no na árvore t na posição pos do arquivo fileName .

  5. int busca(Arv_B t, int ch, int &pos);

    Verifica a existência da chave ch na árvore t (retornando falso ou verdadeiro). A variável pos retorna a posição do nó no qual a chave se encontra.

  6. void le_disco(Arv_B *t, int pos, ap_no no, char * fileName);

    Dada uma posição pos no arquivo fileName , carregue esses dados na variável no.

  7. int deleta(Arv_B *t, int v);

    Deleta a chave v na árvore t; retorna 1 caso a deleção tenha sido bem sucedida ou 0 caso a chave já esteja presente na árvore.

  8. void deleta_disco(Arv_B *t, int pos, ap_no no, char * fileName);

    Deleta o nó no da árvore t que se encontra na posição pos no arquivo fileName .

  9. int libera (Arv_B *t);

    Desaloca a memória de todos os nós de t.



Programa para testes

A interface que trabalha sobre uma árvore t deve conter as seguintes operações:

  • i v

    Insere a chave v na árvore t

  • d v

    Deleta a chave v na árvore t

  • b v

    Verifica se a chave v está presente na árvore t

  • e

    Escreve os elementos da árvore t em ordem crescente.

  • l

    Libera os nós da árvore t a reinicializa com NULL.

Exemplo 

    i 3
i 2
i 1
i 6
e
1 2 3 6 
i 4
e
3 
1 2 
4 6 
d 1
1: chave deletada.
e
3 
2 
4 6 
b 4
4: chave encontrada.
l
b 4
4: chave não encontrada. 
e



Bom trabalho!