Lista2

Prévia do material em texto

Algoritmos e Estrutura de Dados III
Lista de exercício 2
Nome: Guilherme Vemado	Nº: 201010347
Árvore Binária completamente balanceada
Árvore Binária balanceada
Árvore Binária cheia
a) 
b) Os passos realizados na primeira fase
a) Inserção da chave 10,11 (Rotação Dupla):
b) Inserção da chave 6 (Rotação Simples): 
c) Inserção da chave 1 (Árvore permanece balanceada):
d) Inserção da chave 2, 3, 7, 9, 12:
Função implementada em C:
void rotacaoEsquerda(Apontador *p) 
{
 if((*p)==NULL || (*p)->Dir==NULL) /*Verifica se o no passado, ou seu filho a direita e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pfilhoDir = (*p)->Dir;
 (*p)->Dir = pfilhoDir->Esq;
 pfilhoDir->Esq = (*p);
 (*p) = pfilhoDir;
 }
 
}
Função Implementada em C:
void rotacaoDireita(Apontador *p)
{
 
 if((*p)==NULL || (*p)->Esq==NULL) /*Verifica se o no passado, ou seu filho a esquerda e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pfilhoEsq = (*p)->Esq;
 (*p)->Esq = pfilhoEsq->Dir;
 pfilhoEsq->Dir = (*p);
 (*p) = pfilhoEsq;
 }
}
Função Implementada em C:
void rotacaoEsqDir(Apontador *pAvo)
{
 if((*pAvo)->Esq==NULL || (*pAvo)->Esq->Dir==NULL || (*pAvo)==NULL) /*Verifica se o no avo, ou seu filho a esquerda, ou seu filho a direita do filho a esquerda e nulo*/
 {
 printf("Rotacao Impossivel de ser realizada!\n");
 }
 else
 {
 rotacaoEsquerda(&(*pAvo)->Esq); /*E executada uma rotacao a esquerda com o no pai a esquerda*/
 rotacaoDireita(&(*pAvo));/*E executada uma rotacao a direita com o no avo atual*/
 } 
}
Implementação para Teste:
#include <stdlib.h>
typedef int TipoChave;
typedef struct Registro {
 TipoChave Chave;
} Registro;
typedef struct No * Apontador;
typedef struct No {
 Registro Reg;
 Apontador Esq, Dir;
} No;
typedef Apontador TipoDicionario;
void rotacaoEsquerda(Apontador *p) 
{
 if((*p)==NULL || (*p)->Dir==NULL) /*Verifica se o no passado, ou seu filho a direita e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pfilhoDir = (*p)->Dir;
 (*p)->Dir = pfilhoDir->Esq;
 pfilhoDir->Esq = (*p);
 (*p) = pfilhoDir;
 }
 
}
void rotacaoDireita(Apontador *p)
{
 
 if((*p)==NULL || (*p)->Esq==NULL) /*Verifica se o no passado, ou seu filho a esquerda e nulo*/
 {
 printf("Rotacao impossivel de ser realizada!\n");
 }
 else
 {
 Apontador pfilhoEsq = (*p)->Esq;
 (*p)->Esq = pfilhoEsq->Dir;
 pfilhoEsq->Dir = (*p);
 (*p) = pfilhoEsq;
 }
}
void rotacaoEsqDir(Apontador *pAvo)
{
 if((*pAvo)->Esq==NULL || (*pAvo)->Esq->Dir==NULL || (*pAvo)==NULL) /*Verifica se o no avo, ou seu filho a esquerda, ou seu filho a direita do filho a esquerda e nulo*/
 {
 printf("Rotacao Impossivel de ser realizada!\n");
 }
 else
 {
 rotacaoEsquerda(&(*pAvo)->Esq); /*E executada uma rotacao a esquerda com o no pai a esquerda*/
 rotacaoDireita(&(*pAvo));/*E executada uma rotacao a direita com o no avo atual*/
 } 
}
void ListarTabulado(No *p,int nivel)
{
 int i;
 nivel++;
 if (p != NULL)
 {
 for(i=1;i<nivel;i++)
 {
 printf(" ");
 }
 
 printf("%d\n",p->Reg.Chave);
 ListarTabulado(p->Esq,nivel);
 ListarTabulado(p->Dir,nivel);
 }else printf("---\n");
}
int Insere(Registro x, Apontador *p)
{ 
 
 if (*p == NULL) 
 { *p = (Apontador)malloc(sizeof(No));
 (*p)->Reg = x; (*p)->Esq = NULL; (*p)->Dir = NULL;
 return 0;
 }else
 if (x.Chave < (*p)->Reg.Chave) 
 {
 if( Insere(x, &(*p)->Esq)==-1 ) return -1;
 else return 0;
 }else
 if (x.Chave > (*p)->Reg.Chave)
 {
 if( Insere(x, &(*p)->Dir)==-1 ) return -1;
 else return 0;
 }
 else
 {
 printf("Erro : Registro ja existe na arvore\n");
 return -1;
 }
 
}
int main()
{
 No *Dicionario=NULL; //Declara Dicionario
 Registro X; //Declara tipo registro
 X.Chave=500; //Passa chave igual a 500 para o registro X
 Insere(X,&Dicionario); // Insere Registro X na arvore binaria
 X.Chave=400; //Passa chave igual a 400 para o registro X
 Insere(X,&Dicionario); // Insere Registro X na arvore binaria
 X.Chave=450; //Passa chave igual a 450 para o registro X
 Insere(X,&Dicionario); // Insere Registro X na arvore binaria
 
 printf("Arvore antes da rotacao Esquerda-Direita:\n");
 ListarTabulado(Dicionario,0); //Exibe arvore atraves do metodo por tabulacao
 rotacaoEsqDir(&Dicionario); //Faz rotacao Esquerda Direita atraves das funções de rotacao ja criada
 
 printf("Arvore depois da rotacao Esquerda-Direita:\n");
 ListarTabulado(Dicionario,0); //Exibe arvore atraves do metodo por tabulacao, mostrando o sucesso da rotacao
 
 system("pause");
 return 0; 
 }
Algoritmo DSW
Função DSWBalancingAlgorithm: 
O primeiro passo é transformar toda a árvore em uma espinha dorsal através das rotações para a direita, com os nós filhos a esquerda. No final da operação, a árvore fica com a sua altura igual ao número de nós. Após tal transformação, passaremos para o segundo passo, onde algoritmo executa i rotações a esquerda, sendo i igual a parte inteira da divisão do número de nós por dois. O algoritmo pega de dois em dois nós a direita, para poder fazer as rotações. Após o término da primeira sequência de rotações, o algoritmo divide i por dois, e pega somente a sua parte inteira, para assim fazer uma nova i rotações à esquerda. Essa operação é executada até que a parte inteira de i for menor um. No final teremos uma árvore balanceada.
Função LeftRotate:
O algoritmo modifica somente os ponteiros para a esquerda e direita dos nó pai e do nó filho, e faz com que o nó a esquerda do nó pai seja apontado para o nó a sua direita. Depois é efetuada a troca dos valores contidos, para que a árvore fique regularizada. A árvore a esquerda do nó pai permanece a sua esquerda, o nó a direita do nó pai passa a ser o nó a esquerda do nó filho e o nó a direita do nó filho permanece sendo o nó a direita.
Função RightRotate:
Assim como no LeftRotate, o algoritmo modifica somente os ponteiros para a esquerda e direita dos nó pai e do nó filho, e faz com que o nó a direita do nó pai seja apontado para o nó a sua esquerda. Depois é efetuada a troca dos valores contidos, para que a árvore fique regularizada. A arvore a esquerda do nó filho continua sendo o seu nó a esquerda, o nó a direita do nó filho passa a ser o nó a esquerda do nó filho, o nó a direita do nó pai continua sendo o seu nó filho. Os valores contidos nos nós são trocados para que a árvore permaneça regularizada.