Algoritmo da Arvore AVL, alguem tem?

Answer 1

ALGORITMOS PARA INSERÇÃO, REMOÇÃO E CORRELATOS EM ÁRVORES AVL



// Aloca um novo nó
Algoritmo inicio-no(pt, x)
aux := novo nó
aux.chave := x
aux.esq := NULO
aux.dir := NULO
aux.bal := 0
Fim algoritmo



// Realiza a rotação direita (RD) ou rotação dupla direita (RDD)
Algoritmo caso1(pt, h)
ptu := pt.esq
se put.bal = -1 então
pt.esq := ptu.dir
ptu.dir := pt
pt.bal := 0
pt := ptu
senão
ptv := ptu.dir
ptu.dir := ptv.esq
ptv.esq := ptu
pt.esq := ptv.dir
ptv.dir := pt
se ptv.bal = -1 então
pt.bal := 1
senão
pt.bal := 0
fim se
se ptv.bal = 1 então
ptu.bal := -1
senão
ptu.bal := 0
fim se
pt := ptv
fim se
pt.bal := 0
h := F
Fim algoritmo



// Realiza a rotação esquerda (RD) ou rotação dupla esquerda (RDE)
Algoritmo caso2(pt, h)
ptu := pt.dir
se put.bal = 1 então
pt.dir := ptu.esq
ptu.esq := pt
pt.bal := 0
pt := ptu
senão
ptv := ptu.esq
ptu.esq := ptv.dir
ptv.dir := ptu
pt.dir := ptv.esq
ptv.esq := pt
se ptv.bal = 1 então
pt.bal := -1
senão
pt.bal := 0
fim se
se ptv.bal = -1 então
ptu.bal := 1
senão
ptu.bal := 0
fim se
pt := ptv
fim se
pt.bal := 0
h := F
Fim algoritmo


// Verifica se é necessário realizar balanceamento para direito do nó
Algoritmo baldir(pt, h)
se h = V então
caso pt.bal seja
1: pt.bal := 0; h := F;
0: pt.bal := -1
-1: caso1(pt, h)
fim caso
fim se
Fim algoritmo

// Verifica se é necessário realizar balanceamento para esquerda do nó
Algoritmo balesq(pt, h)
se h = V então
caso pt.bal seja
-1: pt.bal := 0; h := F;
0: pt.bal := 1
1: caso2(pt, h)
fim caso
fim se
Fim algoritmo





// Insere um nó em árvore AVL
Algoritmo insere-AVL(x, pt, h)
se pt = NULO então
inicio-no(pt, x)
h := V
senão
se x < pt.chave então
insere-AVL(x, pt.esq, h)
baldir(pt, h)
senão
insere-AVL(x, pt->dir, h)
balesq(pt,h)
fim se
fim se
Fim algoritmo




// Percurso em pré-ordem
Algoritmo pre(pt)
visita(pt)
se pt.esq  NULO então pre(pt.esq)
se pt.dir  NULO então pre(pt.dir)
Fim algoritmo



// Percurso em in-ordem
Algoritmo in(pt)
se pt.esq  NULO então in(pt.esq)
visita(pt)
se pt.dir  NULO então in(pt.dir)
Fim algoritmo




// Percurso em pos-ordem
Algoritmo pos(pt)
se pt.esq  NULO então pos(pt.esq)
se pt.dir  NULO então pos(pt.dir)
visita(pt)
Fim algoritmo




// Remove que busca um nó para substituir na sub-árvore direita
Algoritmo busca-remove(ptb, pt, h)
aux := novo nó
se ptb.dir  NULO então
buca-remove(ptb.dir, pt, h)
balesq(ptb, h)
senão
pt.chave := ptb.chave
aux := ptb
ptb := ptb.esq
se ptb  NULO então
pai de ptb aponta para pai de aux
fim se
h := V
libera espaço alocado para aux
fim se
Fim algoritmo

// Remove um nó em árvore AVL
Algoritmo remove-AVL(x, pt, h)
se pt = NULO então
h := F
senão
se x < pt.chave então
remove-AVL(x, pt.esq, h)
balesq(pt, h)
senão
se x > pt.chave então
remove-AVL(x, pt->dir, h)
baldir(pt,h)
senão
se pt.dir = NULO então
se pt.esq  NULO então
pai de pt aponta para pt.esq
fim se
pt := pt.esq
h := V
senão
se pt.esq = NULO então
se pt.dir  NULO então
pai de pt aponta para pt.dir
fim se
pt := pt.dir
h := V
senão
busca-remove(pt.esq, pt, h)
balesq(pt, h)
fim se
fim se
fim se
fim se
fim se
Fim algoritmo

Answer 2

sei nem o que é isso.