Como construir determinada Arvores AVL sendo balanceada a cada inserção fazendo as rotações necessárias?
Nessa árvores são inseridos os valores: 20, 10, 5, 30, 25, 27 e 28. Como esta árvore vai ser contruido sendo balanceada a cada inserção?
💡 3 Respostas
Joao Andre MArtins Dias
struct AVLNode {
int info;
struct AVLNode *esq, *dir;
};
typedef struct AVLNode No;
/*------------------------------------------------------------------------*/
void init(No **raiz);
void insereAvl(No **raiz, int info, char *flag);
void rotacaoEsq(No **p);
void rotacaoDir(No **p);
No* criaNo(int info);
char eFolha(No *no);
char vazia(No *raiz);
int altura(No *raiz);
/*------------------------------------------------------------------------*/
void init(No **raiz) {
*raiz = NULL;
}
/*------------------------------------------------------------------------*/
No* criaNo(int info) {
No* novo = (No*) malloc(sizeof (No));
novo->info = info;
novo->esq = novo->dir = NULL;
return novo;
}
/*------------------------------------------------------------------------*/
char vazia(No *raiz) {
return raiz == NULL;
}
/*------------------------------------------------------------------------*/
char eFolha(No *no) {
return (no->dir == NULL && no->esq == NULL);
}
/*------------------------------------------------------------------------*/
void rotacaoEsq(No **p) {
No *temp, *q;
q = (*p)->dir;
temp = q->esq;
q->esq = *p;
(*p)->dir = temp;
*p = q;
}
/*------------------------------------------------------------------------*/
void rotacaoDir(No **p) {
No *temp, *q;
q = (*p)->esq;
temp = q->dir;
q->dir = *p;
(*p)->esq = temp;
*p = q;
}
/*------------------------------------------------------------------------*/
int altura(No *raiz) {
int esq, dir;
if (raiz != NULL) {
esq = altura(raiz->esq);
dir = altura(raiz->dir);
return (esq > dir) ? esq + 1 : dir + 1;
}
return 0;
}
/*------------------------------------------------------------------------*/
void insereAvl(No **raiz, int info, char *flag) {
int FB, FBFilho;
if (vazia(*raiz)) {
*raiz = criaNo(info);
*flag = 0;
} else {
if (info > (*raiz)->info)
insereAvl(&(*raiz)->dir, info, flag);
else
insereAvl(&(*raiz)->esq, info, flag);
if (!flag) {
FB = altura((*raiz)->dir) - altura((*raiz)->esq);
if (abs(FB) == 2) {
*flag = 1;
if (FB == 2) {
FBFilho = altura((*raiz)->dir->dir) - altura((*raiz)->dir->esq);
if (FBFilho == 1)
rotacaoEsq(&(*raiz));
else {
rotacaoDir(&(*raiz)->dir);
rotacaoEsq(&(*raiz));
}
} else {
FBFilho = altura((*raiz)->esq->dir) - altura((*raiz)->esq->esq);
if (FBFilho == -1)
rotacaoDir(&(*raiz));
else {
rotacaoEsq(&(*raiz)->esq);
rotacaoDir(&(*raiz));
}
}
}
}
}
}
/*------------------------------------------------------------------------*/
void Exibe(No *raiz, int tam, int l, int c) {
if (raiz != NULL) {
move(l, c);//trocar para gotoxy quem usa windows
attron(COLOR_PAIR((1)));//trocar para color quem usa windows
printw("%2d\n", raiz->info);//trocar para printf quem usa windows
c -= int(pow(2, tam) / 2);
Exibe(raiz->esq, tam - 1, l + 2, c);
c += int(pow(2, tam - 1)*2);
Exibe(raiz->dir, tam - 1, l + 2, c);
}
}
Cara esse é o codigo em C para inserir na arvore AVL(recursivo) A função exibe está com comandos de telas da lib ncurses(se você usa windows deve substituir pelos comnados da conio ex move(i,c) gotoxy(c,i) ...
RD Resoluções
Para a resolução desta tarefa foram utilizados conhecimentos sobre arvores AVL.
Para manter uma árvore balanceada, é necessário fazer uma transformação na árvore tal que o percurso em ordem da árvore transformada seja o mesmo da árvore original (isto é, a árvore transformada continue sendo um árvore de busca binária) e a árvore transformada fique balanceada. Esta transformação se chama rotação que pode ser feita à esquerda ou à direita, Para o rebalanceamento da árvore é necessário calcular o Fator de Balanceamento para verificar qual rotação deve ser efetuada afim de rebalanceá-la, este cálculo é feito através da subtração da altura da subárvore à direita pela altura da subárvore à esquerda, se FB é negativo, as rotações são feitas à direita e se é positivo, as rotações são feitas à esquerda. Existem 4 tipos de rotação sendo elas, rotação esquerda, rotação direita, rotação esquerda direita e rotação direita esquerda.
Nesta sequência de inserção, 20 ia ser inserido na raiz, após isso o 10 à esquerda, quando o 5 fosse inserido iria acontecer a primeira rotação e a nova raiz da árvore seria o 10, com o 20 à direita e o 5 à esquerda, 30 iria ser inserido à direita de 20, na inserção do 25 ocorreria outra rotação para a árvore continuar balanceada, o 25 ficaria no lugar do 20, tendo 30 à sua direita e 20 à sua esquerda, com a inserção do 27 a árvore toda se modificaria, 27 seria inserido à esquerda de 30 e mais de uma rotação seria feita, a nova raiz agora é o 25 e a altura da árvore é 3, por fim com a inserção do 28, ocorreria a última rotação e o resultado final seria o seguinte:
Arvores AVL são sempre balanceadas através de rotações, onde sua inserção é baseada.
Gustavo Pereira
Para construir a árvore AVL com os valores dados, devemos seguir os seguintes passos:
Inserir o valor 20: a árvore fica com apenas um nó, que é a raiz.
20
Inserir o valor 10: o 10 é menor que 20, então é inserido à esquerda da raiz. A árvore fica desbalanceada, então é necessário fazer uma rotação simples à direita.
10 \ 20
Inserir o valor 5: o 5 é menor que 10, então é inserido à esquerda do nó 10. A árvore fica desbalanceada, então é necessário fazer uma rotação simples à direita.
5 / \ 10 20
Inserir o valor 30: o 30 é maior que 20, então é inserido à direita da raiz. A árvore fica desbalanceada, então é necessário fazer uma rotação simples à esquerda.
5 / \ 10 20 \ 30
Inserir o valor 25: o 25 é maior que 10 e menor que 20, então é inserido entre esses nós. A árvore fica desbalanceada, então é necessário fazer duas rotações: primeiro uma simples à esquerda no nó 20 e depois uma simples à direita na raiz.
5 / \ 10 25 / \ 20 30
Inserir o valor 27: o 27 é maior que 25 e menor que 30, então é inserido entre esses nós. A árvore fica desbalanceada, então é necessário fazer duas rotações: primeiro uma simples à direita no nó 25 e depois uma simples à esquerda na raiz.
5 / \ 10 27 / / \ 5 20 30
Assim, a árvore AVL construída com os valores dados é:
5 / \ 10 27 / / \ 5 20 30
Implementação em java.
public class AVLTree {
private Node root;
private class Node {
private int value;
private int height;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
this.height = 1;
}
}
private int height(Node node) {
if (node == null) return 0;
return node.height;
}
private int balance(Node node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}
private Node rotateLeft(Node node) {
Node newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
return newRoot;
}
private Node rotateRight(Node node) {
Node newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1;
return newRoot;
}
public void insert(int value) {
root = insert(root, value);
}
private Node insert(Node node, int value) {
if (node == null) return new Node(value);
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
} else {
return node;
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = balance(node);
if (balance > 1 && value < node.left.value) {
return rotateRight(node);
}
if (balance < -1 && value > node.right.value) {
return rotateLeft(node);
}
if (balance > 1 && value > node.left.value) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (balance < -1 && value < node.right.value) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
// Métodos adicionais para percorrer, buscar, remover nós, etc.
public void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}
public void preOrderTraversal(Node node) {
if (node != null) {
System.out.print(node.value + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
public void postOrderTraversal(Node node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.value + " ");
}
}
public Node search(Node node, int value) {
if (node == null || node.value == value) {
return node;
}
if (value < node.value) {
return search(node.left, value);
} else {
return search(node.right, value);
}
}
}
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Perguntas relacionadas
Compartilhar