Árvore AVL

I - Apresentação

Como descrito anteriormente, busca binária em arvores trabalham bem somente quando a árvore está balanceada. Infelizmente, manter uma árvore de busca binária balanceada é um problema mais complicado do que parece inicialmente. Não obstante, existem algumas abordagens inteligentes que podem ser usadas para se criar ou manter uma arvore balanceada.

Por exemplo, sabendo de antemão os itens que serão utilizados na arvore, colocamos os itens mais frequentemente acessados na parte alta da arvore, criando assim uma arvore balanceada por peso.

Ao generalizar a utilidade assumi-se que todos os itens utilizados na árvore tem a mesma frequência. Como consequência desta ação a árvore terá balanceamento de altura, ou seja, nenhuma subárvore terá permissão de ser maior que seu irmão.

Uma formulação especifica desta ideia foi introduzida por dois matemáticos soviéticos, Georgii Maximovich Adelson-Velsky e  Evgenii Mikhailovich Landis. As árvores que seguem o modelo de programação são conhecidas como arvores AVL. Uma árvore AVL é uma árvore de busca binária que obedece a seguinte regra: A altura das árvores filhas de um nó tem apenas a diferença de um.

Árvore AVL

Esta regra requer que a árvore seja vista como uma floresta de subárvores e imponha a regra através da árvore, como mostrado na figura acima. Note que a regra aplica-se tanto para pequenas subárvore (círculos vermelho e amarelo) como também para as duas subárvores da raiz (círculos verde e azul). Enquanto a regra parece pesada em sua execução, é possível perceber que uma árvore pode ser mantida balanceada realizando apenas manipulações locais na mesma.

  

II - Fator de balanço

Para isso a árvore AVL armazena um pedaço extra de informação em cada nó: fator de balanço. O fator de balanço de um nó é a altura da subárvore enraizada em seu filho esquerdo menos a altura da subárvore enraizada em seu filho direito.

            A altura de cada subárvore será definida pelo filho de maior altura somado de um, ao pegar o exemplo da figura 1 e incluir os valores de altura temos que cada folha terá o valor zero.

            A partir das folhas, a altura da subárvore pai irá escolher sempre a subrvore filha de maior altura e somar 1.

Como se observa, a altura da arvore utilizara como referencia sempre a altura do maior filho.

Possuindo a altura de cada nó que se encontra na árvore, basta fazer altura do filho esquerdo menos a altura do filho direito para obter o fator de balanço.

Após adicionar ou apagar nós, se deve rebalancear a árvore caso um desbalanceamento tenha sido introduzido, ajustando para que todos os fatores de balanço fiquem +1, -1 ou 0.   

Uma subárvore com o fator de balanço +1 é dita como esquerda pesada. Uma subárvore com fator de balanço -1 é dita como direito-pesada. Uma subárvore cujo nó tem o fator de balanço 0 é considerada balanceada. Por manter suas subárvores balanceadas, uma árvore AVL se mantém de forma geral aproximadamente balanceada.

III - Rotação

A rotação faz o rebalanceamento de uma parte da árvore AVL ao rearranjar nós enquanto preserva a relação aonde o esquerdo é menor que o pai e o pai é menor que o da direita, que deve ser mantida para que árvore permaneça uma árvore de busca binária. Após a rotação, o fator de balanço entre todos os nós na subárvore que girou em volta são +1, -1 ou 0.

Na figura abaixo vemos as duas operações básicas de rotação para rebalancear a arvore sem violar a propriedade de busca binária com filho esquerdo menor que pai menor que filho direito, aonde T1, T2 e T3 são subárvores com raiz em y (lado esquerdo) ou em x (lado direito).

   

Operações básicas de rotação

  

Existem somente quatro casos em que as rotações podem ser aplicadas. Estes são as sequencias EE (Esquerda Esquerda), ED (Esquerda Direita), DD (Direita Direita) e DE (Direita Esquerda).

1.            Caso EE (Esquerda Esquerda):

2.            Caso ED (Esquerda Direita):

3.            Caso DD (Direita Direita):

4.            Caso DE (Direita Esquerda):

Todos os ajustes de rotação para DD e DE são simétricos de EE e ED.

O efeito da regra AVL é assegurar que árvore nunca fique substancialmente desbalanceada, e pode ser mostrado que a altura de uma árvore AVL com N nós será proporcional à lg N. De qualquer maneira, realmente programar uma árvore AVL é problemático devido ao numero de casos especiais que devem ser considerados, como também a possibilidade de que a árvore exija múltiplas rotações para consertar os novos desbalanceamentos gerados pelas rotações anteriores.

Isto implica em atravessar de volta o caminho de acesso tomado durante a inserção ou exclusão, recorrendo à recursividade, entretanto existem soluções mais simples, que embora não obtenham um balanceamento tão eficiente como o AVL, mas que permitem rotações ocorrerem enquanto a busca segue direção abaixo como a árvore Rubro negra.

Árvore de Busca Binária

                Uma árvore de busca binária nada mais é do que uma arvore binária organizada especificamente para procuras, a busca de um nó dentro arvore se inicia pela raiz da arvore e desce de nível a nível até encontrar o nó desejado, utilizando a seguinte escolha, encontrou um nó maior que o desejado segue o ponteiro esquerdo, encontrou nó menor que o desejado segue o ponteiro direito, caso a procura alcance uma folha antes de encontrar um equivalente, o mesmo não existe na árvore.

                A eficiência de uma busca binária em árvores é excelente, uma vez que o pior caso, basta procurar a informação em apenas uma ramificação, ao invés de percorrer cada um de todos os dados, se uma arvore tem N nós distribuídos aleatoriamente, deverá ter uma altura media de lg N de nós. Por exemplo, se inserir em uma arvore os números 7, 3, 9, 2, 6,  11, 1, 5, 4 e 10, teremos como resultado a árvore da figura 1 com três níveis e razoavelmente bem balanceada. Se iniciar uma busca pelo numero 6, começa seguindo pelo ponteiro esquerdo na raiz 7, seguido do ponteiro direito na subárvore de árvore de valor 3 e já terá encontrado o equivalente.

Figura 1

               

                Pode ser melhorado? Certamente, a árvore da figura 1 precisa apenas de dois níveis de altura,lembre que uma árvore balanceada consiste em manter a mesma com a menor altura possível para um dado numero de nós, com o balanceamento correto na árvore, acaba eliminando o surgimento de uma ramificação demasiadamente longa que precise ser percorrida.

Entretanto  o formato desta árvore binária depende de em qual ordem o conjunto de itens foi carregado, os exemplos de árvores vistos anteriormente não possuem nenhum mecanismo interno que impeça o desbalanceamento entre subárvores.

Para melhor compreender a importância do balanceamento de uma arvore de busca binária, considere o pior caso ocorre quando toda a informação de entrada se encontra ordenada, na figura 2 temos o exemplo do que acontece na arvore quando recebe os números em ordem crescente, com cada elemento sendo sempre inserido a direita, que resulta em uma arvore desbalanceada a tal ponto que se assemelha a uma lista encadeada.

Figura 2

Em situações como esta, altura da arvore não é lg N e sim N, devido a péssima eficiência do pior caso que acaba tornando inaceitável o uso da árvore, de imediato duas soluções para o problema ocorrem, primeira alternativa aonde garante-se uma ordem aleatória de dados como no exemplo da figura 1 resultando num balanceamento ou a segunda opção em que todos os dados são analisados antes de adiciona-los.

Caso se conheça de antemão os itens que serão carregados, é possível construída uma arvore binária completa ou quase completa, mas como é de praxe na programação pratica, a ordem pela qual os nós são adicionados e excluídos não pode ser antecipada, o que irá requerer uma abordagem mais proativa utilizando algoritmos que forçam a arvore a se balancear sempre que executa uma ação de adição ou exclusão.

Nas próximas postagens veremos mais sobre o assunto através das analises das árvores AVL, Splay e Rubro-negra.

Árvore Binária Genérica 2ª Parte

No primeiro passo para montar a aplicação através das primitivas apresentadas para árvore binária, cria a estrutura SBINTREE como mostrado a seguir, que será referenciado no código pelo ponteiro BT.

int main(int argc, char *argv[]) {       SBINTREE *BT;       // configura a estrutura de dados da arvore binaria       BT = CreateBinTree(     CreateData,                              DeleteData,                              DuplicatedNode,                              NodeDataCmp,                              PrintData); . . .

                Na lista abaixo de primitivas genéricas, exceto pela rotina CreateBinTree (responsável por iniciar a árvore), todas as rotinas recebem como primeiro parâmetro o endereço (ponteiro BT) da estrutura que abriga os itens pertinentes à árvore.

Primitivas Genéricas:	SBINTREE *CreateBinTree(     void *( * fCreateData )    ( void * ),   BOOL ( * fDeleteData )     ( void * ),           int  ( * fDuplicatedNode ) ( SLINK, SLINK ),   int  ( * fNodeDataCmp )    ( void *, void *),    int  ( * fTraversal )    ( void *, void *, int));
	BOOL AddNode( SBINTREE *, void *);
	BOOL DeleteNode( SBINTREE *, void * );
	SLINK FindNode( SBINTREE *, void * );
	BOOL DestroyBinTree( SBINTREE * );
	BOOL TraversalTree(void *, SBINTREE *, ETRAVERSAL );
	BOOL PrintForest(FILE *, SBINTREE *);

Com a lógica da árvore concluída, basta incluir o tratamento dos especifico dos dados a serem utilizados, as primitivas FindNode, DeleteNode e AddNode precisam saber como comparar dados, pois dependem de tal mecanismo para percorrer a arvore, DeleteNode precisa tratar a liberação de memória do nó e AddNode, precisa saber o quanto reservar de memória como também o que fazer com informação duplicada.

Com isso fica claro entender o porquê das primitivas sempre receber como parâmetro a estrutura SBINTREE, através dela será possível acessar rotinas especificas para o tratamento dos dados.

Por exemplo, a função AddNode(), precisa ser capaz de comparar os dados do nó a ser incluído com o nó que já se encontra na árvore,  para isto, chama a rotina de comparação indicada por fNodeDataCmp em BT, BT é um ponteiro para a estrutura SBINTREE que estamos acessando, portanto, BT->fNodeDataCmp é o atual ponteiro de função. Para chamar a função se utiliza o símbolo * de referencia.

BT = CreateBinTree( CreateData,                            DeleteData,                            DuplicatedNode,                            NodeDataCmp,                            PrintData); . . .        *(BT->fNodeDataCmp)(slkNew, slkCurr);

A sintaxe para chamar a rotina através do ponteiro foi simplificada pelo uso de macro de (*(L->fNodeDataCmp)) para NodeDataCmp. Portanto, ao usar a macro NodeDataCmp(a, b), tem o efeito de chamar a função e passar os argumentos a e b. Todas as rotinas especificas da aplicação seguem esse modelo.

#define CreateData                (*(BT->fCreateData)) #define DeleteData                (*(BT->fDeleteData)) #define DuplicatedNode            (*(BT->fDuplicatedNode)) #define NodeDataCmp               (*(BT->fNodeDataCmp))

Todas as funções que seguem com o destaque em branco, se referem às mascaras criadas pela macro para indicar o momento em que o trabalho dependente do tipo de informação é incluso no código de tratamento da árvore.

PRIVATE SLINK CreateNode(SBINTREE *BT, void *pData) { . . .        // agora chama a aplicacaoh especifica para alocacah de dados        slkNewNode->pData = CreateData(pData); . . . BOOL AddNode(SBINTREE *BT, void *pData) { . . .        slkNew = CreateNode(BT, pData);   // cria o noh . . .              // Decide qual direcaoh seguir              iCompare = NodeDataCmp(slkNew->pData, slkCurr->pData);                   if (iCompare == 0)         // noh duplicado              {                     // o que fazer com noh duplicado                     iAction = DuplicatedNode(slkNew, slkCurr); . . . BOOL DeleteNode( SBINTREE *BT, void *pData ) { . . .        while (slkCurr != NULL &&              (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData)))        { . . .        DeleteData(slkDel->pData);        // apaga o dado do noh        free(slkDel);                     // libera a memoria do noh . . . SLINK FindNode( SBINTREE *BT, void *pData ) { . . .        while (slkCurr != NULL &&              (iCompare = NodeDataCmp(slkTmp->pData, slkCurr->pData))) . . .

Toda a parte dependente dos dados fica nos arquivos btapp.h e btapp.c, onde fica declarada que tipo de dados será tratado e como suas rotinas funcionam, para o aplicativo exemplo será utilizado uma estrutura para armazenar uma palavra e um contador de duplicados, serve ao propósito de mostrar o armazenamento e tratamento de copias, além de ser simples de adaptar para outras soluções, portanto no arquivo cabeçalho temos:

// noh consiste em: typedef struct tagSNODEDATA {     char *pWord;           // ponteiros para palavras     unsigned int uCont;    // e a contagem de ocorrencias }SNODEDATA; typedef SNODEDATA *      pND; void *CreateData( void * ); BOOL  DeleteData( void * ); int   DuplicatedNode( SLINK, SLINK ); int   NodeDataCmp( void *, void * ); int   PrintData(FILE *, SLINK, int);

                Todo o trabalho que for necessário para gerenciar e tratar a informação dentro do nó fica no arquivo btapp.c, neste arquivo se encontram todas as rotinas utilizadas pelas primitivas.

                NodeDataCmp deve retornar o resultado da comparação entre dois strings, basta retornar o resultado da comparação dos dados através do da função strcmp.

int NodeDataCmp(void *first, void *second) {     return (strcmp( ((pND) first)->pWord, ((pND) second)->pWord)); }

                DuplicateNode define o tratamento da árvore para dados duplicados, a função deve retornar um dos seguintes valores, zero apagar o nó duplicado ou um inserir o nó duplicado. Neste caso estamos contando as palavras, se uma palavra duplicada é encontrada, incrementa-se o contador e não inclui o dado duplicado.

int DuplicatedNode(SLINK slkNewNode, SLINK slkListNode) {     pND pnd;     // transforma o ponteiro de dados do noh, no da aplicacaoh     pnd = slkListNode->pData;     // adiciona-se uma ocorrencia para a palavra existente     pnd->uCont += 1;     return 0; }

                Todo o processo de adicionar um nó passa por três alocações de memória, na primeira AddNode reserva o nó genérico de uma árvore, que consiste nos ponteiros esquerdo e direito da subarvore, mais um ponteiro genérico para os dados, CreateData irá montar a informação desejada e retornar o endereço para o nó genérico.

SNODE
LEFT	RIGHT
POINTER		à	SNODEDATA
			INT
			POINTER		à	STRING

CreateData aloca memória para a estrutura SNODEDATA que consiste em um ponteiro e um inteiro, e para a string que foi copiada através da rotina _strdup que aloca e copia a informação de apontada por data retornando o endereço para pWord.

void *CreateData(void *data) {     SNODEDATA *pNewData;     // aloca sua estrutura de dados     pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));     if (pNewData == NULL)         return (NULL);     // move os valores para a estrutura de dados     pNewData->uCont = 1;     pNewData->pWord = _strdup((char *) data);     if (pNewData->pWord == NULL)   // erro copiando a string     {         free(pNewData);         return (NULL);     }     else     {         return (pNewData); // retorna o endereco da estrutura     } }

DeleteData tem de lidar com as duas reservas de memória que foram criadas por CreateData, uma para a estrutura SNODEDATA e a outra para a string, neste caso SNODEDATA consiste em: um ponteiro e um inteiro como o ponteiro que indica a string estão armazenados na estrutura apontada por pND, é obrigatório liberar a string antes da estrutura de tipo SNODEDATA.

BOOL  DeleteData(void *data) {        // duas reservas de memoria foram criadas        // uma para a estrutura SNODEDATA,        // outra para a string        // SNODEDATA consiste em: 1 ponteiro e 1 inteiro.        // O inteiro junto do ponteiro retorna para a memoria        // quando a estrutura for liberada        // nescessario liberar a string antes do ponteiro        free( ((pND) data)->pWord );        free(data);        return TRUE; }

                PrintData será utilizada como a função recursiva utilizada pelas rotinas que percorrem e imprimem a árvore, nela quando solicitado, imprime as informações dos dados na saída desejada.

int PrintData(FILE *fOut, SLINK slkNode, int iLevel) {       return fprintf(   fOut,                         "(%i) %s %u",                         iLevel,                         ((pND) slkNode->pData)->pWord,                         ((pND) slkNode->pData)->uCont); }

                Fica assim completa as rotinas de especificas para árvore binária genérica, faltando agora o aplicativo em si, para facilitar o exemplo, nos arquivos btdriver.h e btdriver.c foram incluídas toda a interface com o usuário, assim quando for o núcleo do programa rodar teremos o seguinte código:

int main(int argc, char *argv[]) {        SBINTREE *BT;        // configura a estrutura de dados da arvore binaria        BT = CreateBinTree( CreateData,                                         DeleteData,                                         DuplicatedNode,                                         NodeDataCmp,                                         PrintData);        if (BT == NULL)        {              fprintf(stderr, "Erro criando arvore binaria\n");              exit(EXIT_FAILURE);        }        // controla as opcoes para teste        // na arvore criada        // possui um loop interno que serah finalizado        // quando o usuario escolher a opcaoh        Menu(BT);        // libera toda a memoria utilizada pela arvore binaria        DestroyBinTree(BT);        return (EXIT_SUCCESS); }

                É criada a arvore BT, e passada para a rotina Menu() que irá permitir ao usuário escolher que operações deseja realizar na árvore indicada por BT.

void Menu( SBINTREE *BT )       {       char cTmp[10];       int iChoice;       BOOL bLoop = TRUE;       while (bLoop)       {             printf("\n\n( 1 ) Inserir\n");             printf(    "( 2 ) Apagar\n");             printf(    "( 3 ) Busca\n");             printf(    "( 4 ) Imprime\n");             printf(    "( 5 ) Carrega arquivo\n");             printf(    "( 6 ) Salva\n");             printf(    "( 0 ) Sair\n\n");             Input("Escolha umas das alternativas: " , cTmp, 10);             if ( cTmp[0] != '\0' && (isdigit(*cTmp)) )             {                   iChoice = atoi(cTmp) ;                   switch ( iChoice ) {                         case 1:     Insert(BT);       break;                         case 2:     Delete(BT);       break;                         case 3:     Search(BT);       break;                         case 4:     Display(BT);      break;                         case 5:     LoadFile(BT);     break;                         case 6:     SaveLog(BT);      break;                         case 0:     bLoop = FALSE;    break;                   }             }       } }

                Dentre as rotinas Insert (inserir), Delete (Apagar) e Search (Procurar) serve como chamada para as primitivas da arvore binária.

PRIVATE void Insert( SBINTREE *BT ) {        char strWord[STR_SIZE];        for ( ; ; ) {              Input("Incluir palavra : " , strWord, STR_SIZE );              if ( strWord[0] == '\0' ) break;              // insere na arvore              if (AddNode( BT, strWord ) == FALSE)                     fprintf(stderr, "ERRO! naoh adicionou noh.\n");        } } PRIVATE void Delete( SBINTREE *BT ) {        char strWord[STR_SIZE] ;        Input("Excluir palavra : " , strWord, STR_SIZE );        // apaga        if (DeleteNode( BT, strWord ))              printf("\nNoh removido.");        else              printf("\nNaoh encontrou noh para remover."); } PRIVATE void Search( SBINTREE *BT ) {        char strWord[STR_SIZE] ;        Input("Procurar palavra : " , strWord, STR_SIZE );        // apaga        if (FindNode( BT, strWord ))              printf("\nEncontrou noh.");        else              printf("\nNaoh encontrou noh."); }

                Para as rotinas de Display (Imprime) e SaveLog (Arquivo) usam a rotina que desenha a árvore resultante PrintForest, a diferença fica por conta dos parâmetros de entrada aonde Display utiliza a tela através de stdout e SaveLog passa o arquivo o ponteiro para o arquivo log.txt, como é esperado, stdout direciona a saída para a tela enquanto fLog salva em arquivo.

PRIVATE void Display( SBINTREE *BT ) {        PrintForest(stdout, BT); } PRIVATE void SaveLog( SBINTREE *BT ) {        FILE *fLog;        fLog = fopen("log.txt", "at");        if (fLog)        {              PrintForest(fLog, BT);              fclose(fLog);        }        else              fprintf(stderr, "ERRO AO CRIAR LOG\n"); }

                Por fim, ainda está anexa a possibilidade de utilizar um arquivo texto para adicionar palavras na árvore, semelhante ao utilizado para testar a tabela de dispersão encadeada, a rotina LoadFile (Carrega arquivo) cuida de percorrer a entrada escolhida pelo usuário.

PRIVATE void LoadFile( SBINTREE *BT ) {        FILE *fin;                 // arquivo de entrada        char strWord[STR_SIZE] ;        char *ptrStr;        int iChar;        int i = 0;        Input("Nome do arquivo : " , strWord, STR_SIZE );        fin = fopen(strWord, "rt");        if (fin)        {              // comecah a processar o arquivo              while (!feof(fin))              {                     // percorre pulando espacosh e pontuncaoesh                     do {                            iChar = getc(fin);                     } while ( iChar != EOF &&                           (isspace(iChar) || ispunct(iChar)));                                                      // tendo um caracter valido                     // comecah a montar a palavra                     ptrStr = strWord;                     do {                            *ptrStr++ = iChar;                            iChar = getc(fin);                     } while (    iChar != EOF &&                                   !isspace(iChar) &&                                  !ispunct(iChar) );                     // fim do arquivo, sai do loop                     if (iChar == EOF)                            break;                     // fecha a palavra com o terminador nulo                     *ptrStr = '\0';                     // todos os caracteres em maiuscula                     ptrStr = strupr(strWord);                     // insere na tabela                     AddNode( BT, ptrStr);                     i++;                     if ((i %1000) == 0)                            fprintf(stdout, "Tratou palavras %u\n", i);              }      // while (!feof(fin))              fclose(fin);        } }

                A interface, mesmo sendo em modo texto é bem simples e permite salvar a árvore no arquivo log.txt, o tratamento da rotina faz com que as impressões sejam sempre anexadas no arquivo, assim cada vez que incluir ou excluir dados, peça para salvar a árvore e será possível visualizar a movimentação dos nós dentro da árvore.

( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 1 Incluir palavra : 5 Incluir palavra : 3 Incluir palavra : 1 Incluir palavra : 4 Incluir palavra : 2 Incluir palavra : 0 Incluir palavra : 7 Incluir palavra : 9 Incluir palavra : 6 Incluir palavra : 8 Incluir palavra : ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 4     +-(2) 9 1     | +-(3) 8 1   +-(1) 7 1   | +-(2) 6 1 +-(0) 5 1   | +-(2) 4 1   +-(1) 3 1     | +-(3) 2 1     +-(2) 1 1       +-(3) 0 1 Total de nohs: 10 Profundidade: 3 ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 2 Excluir palavra : 5 Noh removido. ( 1 ) Inserir ( 2 ) Apagar ( 3 ) Busca ( 4 ) Imprime ( 5 ) Carrega arquivo ( 6 ) Salva ( 0 ) Sair Escolha umas das alternativas anteriores : 4     +-(2) 9 1     | +-(3) 8 1   +-(1) 7 1 +-(0) 6 1   | +-(2) 4 1   +-(1) 3 1     | +-(3) 2 1     +-(2) 1 1       +-(3) 0 1 Total de nohs: 9 Profundidade: 3

Novamente deixo como sugestão para o teste que acesse o Projeto Gutenberg, um esforço voluntário para arquivar e distribuir obras culturais através da digitalização de livros. Nele é possível encontrar obras que estão em domínio publico em vários formatos, para teste utilize a obra de Luis Vaz de Camões, Os Lusíadas cujo arquivo texto pode ser encontrado neste LINK.

Os arquivos do projeto se encontram neste LINK compactados com 7z.