Fica como pré-requisito, a
leitura de árvore binária genérica
parte 1 e
parte 2, a partir desse projeto,
irá ser acrescentado o suporte a árvore AVL, o que ajuda a simplificar o
desenvolvimento, com toda a estrutura já criada basta incluir a alteração nas
rotinas de inserir e excluir nó, tais rotinas ficam no arquivo
bstavl.c e com as declarações em
bstalv.h, a única modificação no projeto
original de árvore binária será a declaração do tipo nó dentro do arquivo
btgen.h, aonde é incluída a informação
da altura da árvore.
// tipo de dados
abstrato noh
typedef struct
tagSNODE
{
struct
tagSNODE *sLink[2]; // ligacaoh para
os nosh das subarvores
void *pData; // ponteiro
generico de dados
// dado utilizado somente por arvores AVL
int iHeight;
// altura da arvore AVL
} SNODE;
|
Rotinas Utilitárias
As rotinas de incluir e excluir
utilizam algumas ações compartilhadas,
dentre elas teremos 3 rotinas de uso comum, funções Higher e Height indicam a
altura de uma árvore através do incremento da altura dos filhos que tem mais
descendente e a função Balance que
retorna o fator de balanço.
Função:
|
Higher
|
Propósito:
|
Retorna o maior numero
|
Parâmetros:
|
int a, int b -> números a serem comparados.
|
Retorno:
|
Maior numero de dois
|
Descrição:
|
Retorna o maior numero após comparação.
|
PRIVATE int Higher(int a, int b)
{
return (a > b) ? a : b;
}
|
Função:
|
Height
|
Propósito:
|
Retorna a altura de um nó dentro da árvore
|
Parâmetros:
|
SLINK slkNode -> nó da árvore
|
Retorno:
|
Fator de balanço do nó slkNode.
|
Descrição:
|
Retorna o dado de altura armazenado no nó.
|
PRIVATE int Height(SLINK
slkNode)
{
if (slkNode)
return slkNode->iHeight;
else // if (slkNode
== NULL)
return 0;
}
|
Para
manter o valor de índices coerentes em uma árvore de busca binária, a sua ordem
não pode ser alterada, existem duas operações básicas que podem ser realizadas
a partir de um nó, a rotação direita e a rotação esquerda, caso fosse criada
funções para cada uma destas rotações o resultado final seria uma sequencia de
operações simétricas, fácil de reparar ao observar a figura que descreve as
rotações como um reflexo.
PRIVATE
SLINK RotateLeft(SLINK slkNode)
{
SLINK slkChild;
SLINK slkGrandChild;
slkChild = slkNode->sLink[RIGHT];
slkGrandChild = slkChild->sLink[LEFT];
slkChild->sLink[LEFT] = slkNode;
slkNode->sLink[RIGHT] =
slkGrandChild;
. . .
PRIVATE
SLINK RotateRight(SLINK slkNode)
{
. . .
slkChild = slkNode->sLink[LEFT];
slkGrandChild =
slkChild->sLink[RIGHT];
slkChild->sLink[RIGHT] = slkNode;
slkNode->sLink[LEFT] =
slkGrandChild;
. . .
|
Aqui fica visível a
vantagem do uso de um vetor de ponteiros para indicar as subárvores, é possível
montar apenas uma rotina e passar a direção desejada como parâmetro para obter
o mesmo resultado.
PRIVATE
SLINK Rotate(SLINK slkNode, int iDir)
{
. . .
slkChild = slkNode->sLink[iDir];
slkGrandChild =
slkChild->sLink[!iDir];
slkChild->sLink[!iDir] = slkNode;
slkNode->sLink[iDir] =
slkGrandChild;
. . .
// x y
// / \ / \
// T1 y x T3
// / \
==> / \
// T2 T3
T1 T2
#define RotateLeft(x) Rotate((x), RIGHT)
// y x
// / \ / \
// x T3 T1 y
// / \
==> / \
// T1 T2 T2 T3
#define RotateRight(x) Rotate((x), LEFT)
|
Junto da rotina temos
duas definições para ter a declaração dentro do projeto das duas rotações
básicas a serem utilizadas mais adiante nos quatro casos que necessitam de
rotações para ajustar o balanço da árvore.
Função:
|
Rotate
|
Propósito:
|
Realiza uma rotação entre os nós da árvore e suas subárvores
|
Parâmetros:
|
SLINK slkNode -> nó da árvore da onde será efetuada a rotação
int iDir -> sentido da rotação.
|
Retorno:
|
SLINK slkChild -> o novo nó pai resultante da rotação.
|
Descrição:
|
T1, T2 e T3 são subárvores enraizadas em y (lado esquerda) ou em x
(no lado direito):
Índices em ambas as árvores obedecem à ordem:
índice (T1) <
índice(x) < índice (T2) < índice(y) < índice (T3)
De tal forma que a propriedade de busca binária não é violada em
nenhum dos casos. Como as duas rotações se espelham, é possível definir a lógica
da troca de nós de uma rotação esquerda e para mudar para direita, inverter
os valores de direção.
|
PRIVATE SLINK Rotate(SLINK slkNode, int iDir)
{
SLINK slkChild;
SLINK
slkGrandChild;
slkChild =
slkNode->sLink[iDir];
slkGrandChild =
slkChild->sLink[!iDir];
// Rotacaoh esquerda
//
//
node(x)
child(y)
// / \ / \
// T1 child(y) node(x) T3
//
/ \ ==>
/ \
// grandchild(T2)
T3 T1
grandchild(T2)
//
// Rotacaoh direita
//
//
node(y)
child(x)
//
/ \ / \
// child(x) (T3) T1 node(y)
// / \ ==> / \
// T1
grandchild(T2)
grandchild(T2) T3
//
slkChild->sLink[!iDir]
= slkNode;
slkNode->sLink[iDir]
= slkGrandChild;
slkNode->iHeight
= Higher( Height(slkNode->sLink[RIGHT]),
Height(slkNode->sLink[LEFT])
) + 1;
slkChild->iHeight
= Higher( Height(slkChild->sLink[RIGHT]),
Height(slkChild->sLink[LEFT])
) + 1;
return slkChild;
}
|
Rotinas de Inclusão
Mesmo não sendo obrigatório, o
modelo escolhido aqui para inserir o nó em uma árvore é através de uma rotina
recursiva, neste caso em particular a recursão fornece além de um modelo
simplificado, a possibilidade de voltar no caminho percorrido dentro da árvore
para incluir o nó, uma situação especialmente útil para verificar o fator de
balanço e a correção através da rotação.
Abaixo vemos a rotina
simplificada para apenas incluir um nó como se fosse uma simples árvore binária.
PRIVATE
SLINK InsNodeAvl(SBINTREE *BST,
SLINK slkNode,
SLINK slkNew)
{
if
(slkNode == NULL)
{
// retorna o enderecoh do noh para o link
return slkNew;
}
else
{
int
iCmp, iDir, iBalance = 0;
iCmp =
NodeDataCmp(slkNew->pData, slkNode->pData);
// comparacaoh retorna -1(menor),
0(igual) e 1(maior)
// corrige <= (-1 e 0) para 1(LEFT) e >(1) para
0(RIGHT)
iDir
= iCmp < 0;
// avanca a posicaoh
slkNode->sLink[iDir]
= InsNodeAvl(BST, slkNode->sLink[iDir], slkNew);
}
// retorna a si mesmo
return slkNode;
}
|
Será no momento de retorno da chamada
de inclusão que será incluído todo o código de tratamento para a correção do
balanceamento da árvore. Primeiro passo consiste em verificar o fator de
balanço.
. . .
// atualiza altura
slkNode->iHeight
= Higher( Height(slkNode->sLink[RIGHT]),
Height(slkNode->sLink[LEFT])
) + 1;
// calcula o balancoh atual no noh
iBalance
= Balance(slkNode);
. . .
|
Através do fator de balanço
sabemos que a árvore pode estar balanceada (de -1 a 1), esquerda pesada(acima
de 1) ou direita pesada (abaixo de -1), ou seja, aqui ocorre à primeira
separação dos casos, uma árvore com a esquerda pesada utiliza as rotações para
os casos Esquerda Esquerda e Esquerda Direita, com o restante acontecendo com a
direita pesada utilizando os casos Direita Direita e Direita Esquerda.
O balanço resultando em esquerda
pesada indica que o filho esquerdo do nó atual precisa ser reajustado, ao
comparar os dados do novo nó com a posição atual descobre-se se o novo nó foi
inserido por “fora”(menor temos o caso EE) ou “dentro”(maior o caso ED).
. . .
if
(iBalance > 1)
{
int iCmpL;
iCmpL =
NodeDataCmp(slkNew->pData, slkNode->sLink[LEFT]->pData);
//
// z y
// / \ / \
// y
T4 RotateRight(z) x z
// / \ -------------> /
\ / \
// x T3 T1 T2
T3 T4
// / \
// T1
T2
// Caso Esquerda Esquerda
if (iCmpL < 0)
{
slkNode =
RotateRight(slkNode);
}
//
// z z x
// / \ /
\ / \
// y T4 RotateLeft(y)
x
T4 RotateRight(z) y
z
// / \ ------------> / \
-------------> / \ / \
//
T1 x y
T3 T1 T2 T3
T4
// / \ / \
// T2
T3 T1 T2
// Caso Esquerda Direita
if (iCmpL > 0)
{
slkNode->sLink[LEFT]
= RotateLeft(slkNode->sLink[LEFT]);
slkNode =
RotateRight(slkNode);
}
}
. . .
|
A
situação se repete parcialmente quando temos a direita pesada, mudando apenas
o resultado da comparação, ocorrendo desbalanceamento à direita, compara o
filho direito com nó recém-inserido para saber se está “dentro”(menor temos o caso
DE) ou “fora” (maior temos o caso DD) da árvore.
if (iBalance < -1)
{
int
iCmpR;
iCmpR = NodeDataCmp(slkNew->pData,
slkNode->sLink[RIGHT]->pData);
//
// z y
// /
\ /
\
// T1 y
RotateLeft(z) z x
//
/ \ ------------> / \
/ \
//
T2 x T1 T2 T3
T4
// / \
//
T3 T4
// Caso Direita Direita
if (iCmpR > 0)
{
slkNode = RotateLeft(slkNode);
}
//
// z z x
// / \ / \ / \
// T1 y
RotateRight(y) T1 x
RotateLeft(z) z x
// / \
-------------> / \
------------> / \ / \
// x
T4 T2 y T1 T2
T3 T4
// / \ / \
// T2 T3 T3 T4
if (iCmpR < 0)
{
slkNode->sLink[RIGHT] =
RotateRight(slkNode->sLink[RIGHT]);
slkNode = RotateLeft(slkNode);
}
}
|
Como
será observado no código final, as rotina acima foram simplificadas para
fazerem uso do vetor de ponteiros e utilizar a vantagem inerente da simetria
que faz parte destas operações, a implementação acima permite descrever cada um
dos quatro casos.
if
(iBalance < -1 || iBalance > 1)
{
BOOL bDouble =
FALSE;
iDir =
(iBalance > 1);
iCmp =
NodeDataCmp( slkNew->pData,
slkNode->sLink[iDir]->pData);
bDouble = iDir
? (iCmp > 0) : (iCmp < 0);
if (bDouble)
slkNode->sLink[iDir]
= Rotate(slkNode->sLink[iDir],
!iDir);
slkNode =
Rotate(slkNode, iDir);
}
|
Além de utilizar a indicação de
direção, a função final se vale do fato que um desbalanceamento sempre exige ao
menos uma rotação, caso seja um desbalanceamento por dentro, faz a dupla
rotação.
Função:
|
InsNodeAvl
|
Propósito:
|
Adicionar um novo nó em uma árvore AVL balanceada
|
Parâmetros:
|
SBINTREE *BT -> ponteiro para estrutura de dados que trata a árvore
c/ ponteiros paras funções de comparação e tratamento de duplicados
SLINK slkNode -> posição atual da árvore que será percorrida para adição
de slkNew
SLINK slkNew -> nó a ser inserido na árvore
|
Retorno:
|
SLINK slkNode -> em caso de balanceamento a rotina pode alterar o endereço
original de slkNode
|
Descrição:
|
A partir da
raiz, desce a ramificação obedecendo à regra de busca binária, para encontrar
a posição em que irá ser inserido, sendo um novo elemento irá se posicionar
no fim da ramificação como uma nova folha, que irá ser a situação padrão, uma
vez que não aceita incluir duplicado nesta implementação.
Ao terminar de
incluir o novo nó, a rotina retorna recursivamente o caminho percorrido até a
raiz novamente, neste momento é possível analisar o balanceamento de cada nó
visitado durante a travessia.
Ao verificar o
balanceamento da árvore, se utiliza a solução AVL para corrigir os valores
cuja diferença seja maior do que 1. Realiza uma rotação simples por 'fora'
nos casos DD ou EE, ou uma rotação dupla por 'dentro' nos casos DE ou ED.
|
PRIVATE SLINK InsNodeAvl( SBINTREE
*BST,
SLINK
slkNode,
SLINK slkNew)
{
// chegou no
fim da ramificacaoh
// insere o
dado na arvore
if
(slkNode == NULL)
{
//
indica o fator de balanco
//
acabou de ser inserido, naoh tem filhos, logo = 1 de altura
slkNew->iHeight = 1;
// soma
o novo noh no total
NodeCount++;
//
retorna o enderecoh do noh para o link
return slkNew;
}
else
{
int iCmp;
int iDir;
int iBalance = 0;
iCmp =
NodeDataCmp(slkNew->pData, slkNode->pData);
// comparacaoh retorna -1(menor), 0(igual) e 1(maior)
//
corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)
iDir = iCmp < 0;
if
(iCmp == 0) // noh duplicado
{
//
o que fazer com noh duplicado
DuplicatedNode(slkNew,
slkNode);
//
naoh inclui o duplicado
//
apaga os dados dependente da implementacaoh do objeto
DeleteData(slkNew->pData);
//
desalocamos o noh
free(slkNew);
}
else // noh
maior ou menor
{
//
avanca a posicaoh
slkNode->sLink[iDir] =
InsNodeAvl( BST,
slkNode->sLink[iDir],
slkNew);
}
//
atualiza altura
slkNode->iHeight = Higher( Height(slkNode->sLink[RIGHT]),
Height(slkNode->sLink[LEFT])
) + 1;
// calcula o balancoh atual no noh
iBalance
= Balance(slkNode);
if (iBalance < -1 || iBalance > 1)
{
BOOL
bDouble = FALSE;
iDir
= (iBalance > 1);
iCmp
= NodeDataCmp( slkNew->pData,
slkNode->sLink[iDir]->pData);
bDouble
= iDir ? (iCmp > 0) : (iCmp < 0);
if (bDouble)
slkNode->sLink[iDir]
= Rotate(slkNode->sLink[iDir],
!iDir);
slkNode =
Rotate(slkNode, iDir);
}
}
// retorna a
si mesmo
return
slkNode;
}
|
Função:
|
AddNodeAvl
|
Propósito:
|
Adicionar um bloco de dados em uma árvore AVL
|
Parâmetros:
|
SBINTREE *BST -> ponteiro para estrutura de dados que trata a árvore
c/ ponteiros paras funções de comparação e tratamento de duplicados
void *pData -> nó a ser inserido na árvore
|
Retorno:
|
Nenhum
|
Descrição:
|
Ao receber o bloco de informação apontado por pData, é criado um nó que
será adicionado na árvore, para isso acontecer, está função é ponto de
entrada para chamada recursiva InsNodeAvl, que irá percorrer a árvore a
partir da raiz em direção à posição de inserção. Junto da inicialização do nó
a ser adicionado.
|
void AddNodeAvl(SBINTREE
*BST, void *pData)
{
SLINK slkNew;
slkNew = CreateNode(BST, pData); // cria o noh e
passa o endereco
if
(slkNew) // conseguiu alocar o noh
{
BSTRoot->sLink[RIGHT]
= InsNodeAvl( BST,
BSTRoot->sLink[RIGHT],
slkNew);
}
}
|
Rotinas de Exclusão
Algumas
pequenas modificações em relação ao processo de correção do balanço tornam a
rotina para excluir um nó diferente da inclusão.
Para
excluir um nó, repete o tratamento visto anteriormente para árvore binária simples,
tratamos os três possíveis casos (sem filhos, um filho ou dois filhos), com
especial atenção para quando o nó a ser excluído tem duas subárvores.
Quando isto acontece trocamos de
posição com o menor elemento da subárvore e reiniciamos o processo de busca
pelo nó, o que permite o processo de exclusão chegar o mais próximo possível do
fim da ramificação e a partir deste ponto realizar o balanceamento durante o
retorno da função.
Com a exclusão do nó não temos
como comparar com o nó atual para descobrir se o desbalanceamento é por “dentro”
ou por “fora”, o que exige que verifiquemos o fator de balanço da subárvore
filha na ramificação em que foi excluído o nó, apesar de considerar -1, 0 e +1
como balanceado, aqui os valores +1 ou -1 ajudam a indicar a direção interna ou
externa do deslocamento.
// esquerda pesada
if
(iBalance > 1)
{
// Left Left Case
if (Balance(slkNode->sLink[LEFT]) >= 0)
slkNode =
RotateRight(slkNode);
// Left Right Case
if (Balance(slkNode->sLink[LEFT]) < 0)
{
slkNode->sLink[LEFT]
= RotateLeft(slkNode->sLink[LEFT]);
slkNode =
RotateRight(slkNode);
}
}
// direta pesada
if (iBalance < -1)
{
// Right Right Case
if (Balance(slkNode->sLink[RIGHT]) <= 0)
slkNode =
RotateLeft(slkNode);
// Right Left Case
if (Balance(slkNode->sLink[RIGHT]) > 0)
{
slkNode->sLink[RIGHT]
= RotateRight(slkNode->sLink[RIGHT]);
slkNode =
RotateLeft(slkNode);
}
}
|
Outra diferença na exclusão
acontece na durante o processo de correção do balanço geral da árvore, na
inclusão as rotações deixam de ser necessárias assim que um nó volta a ter o
fator de balanço igual ao valor anterior a inserção, com a exclusão pode
ocorrer casos em que todos os ancestrais do nó serão corrigidos até chegar à
raiz.
Função:
|
RemoveNodeAvl
|
Propósito:
|
Remove um nó de uma árvore AVL balanceada
|
Parâmetros:
|
SBINTREE *BST -> ponteiro para estrutura de dados que trata a árvore
c/ ponteiros paras funções de comparação e tratamento de duplicados
SLINK slkNode -> posição atual da árvore que será percorrida para exclusão
SLINK slkFind -> informação de busca a ser excluída da árvore.
|
Retorno:
|
SLINK slkNode -> em caso de balanceamento a rotina pode alterar o endereço
original de slkNode
|
Descrição:
|
Realiza uma
busca recursiva pelo nó a ser excluído, slkFind possuem uma copia do dado que
está sendo feita a busca, ao encontrar o nó que deve ser excluído, três situações
podem ocorrer:
1 - o nó é uma folha (não tem filhos), basta excluir.
|
2 - possui apenas um filho (subárvore), filho toma lugar do pai na
hierarquia da árvore, e exclui antigo pai.
|
3 - têm os dois filhos, procura o menor descendente
direito, troca de posição com o descendente, reinicia busca recursiva que
irá encontrar o nó na situação 1 ou 2.
|
Existe um fato
importante em excluir o nó que se encontra no fim de uma ramificação, obriga
a rotina a percorrer a árvore até o extremo, ao retornar recursivamente, poderá
analisar o balanceamento de cada nó percorrido.
Durante o
retorno do processo de exclusão, verifica-se o balanceamento da árvore e
utiliza a solução AVL para corrigir os valores cuja diferença seja maior do
que 1. Realiza uma rotação simples por 'fora' nos casos DD ou EE, ou uma rotação
dupla por 'dentro' nos casos DE ou ED.
|
PRIVATE SLINK RemoveNodeAvl(SBINTREE *BST,
SLINK slkNode,
SLINK slkFind)
{
// chegou no
fim da ramificacaoh
// naoh
encontrou o noh a ser excluido
if
(slkNode == NULL)
{
//
libera o noh de busca
DeleteData(slkFind->pData);
free(slkFind);
}
else
{
int iCmp;
int iDir;
int iBalance = 0;
iCmp =
NodeDataCmp(slkFind->pData, slkNode->pData);
// comparacaoh retorna -1(menor), 0(igual) e 1(maior)
//
corrige <= (-1 e 0) para 1(LEFT) e >(1) para 0(RIGHT)
iDir = iCmp < 0;
//
encontramos o noh a ser excluido
if (iCmp ==
0) //
noh duplicado
{
if ( slkNode->sLink[RIGHT]
== NULL ||
slkNode->sLink[LEFT]
== NULL)
{
SLINK
slkDel;
// salva a posicaoh do noh a ser excluido
slkDel = slkNode;
if (slkNode->sLink[RIGHT] == NULL)
{
slkNode
= slkNode->sLink[LEFT];
}
else
{
slkNode =
slkNode->sLink[RIGHT];
}
// desalocamos o noh de busca
DeleteData(slkFind->pData);
free(slkFind);
DeleteData(slkDel->pData); // apaga o dado
free(slkDel); //
libera o noh
NodeCount--; //
subtrai o noh do total
}
//
ultimo caso
//
encontre o menor descendente esquerdo do filho direito
//
substitui pelo menor descendente
else
{
SLINK slkMinor;
void
*pTmp;
slkMinor
= slkNode->sLink[RIGHT];
while (slkMinor->sLink[LEFT])
{
slkMinor
= slkMinor->sLink[LEFT];
}
// trocar os dados entre os nohs
pTmp =
slkNode->pData;
slkNode->pData =
slkMinor->pData;
slkMinor->pData
= pTmp;
// procura na ramificacao com que se fez a troca
slkNode->sLink[RIGHT] = RemoveNodeAvl(BST,
slkNode->sLink[RIGHT],
slkFind);
}
}
else // noh maior ou menor
{
// avanca a posicaoh
slkNode->sLink[iDir]
= RemoveNodeAvl(BST,
slkNode->sLink[iDir],
slkFind);
}
if (slkNode)
{
// atualiza altura
slkNode->iHeight
= Higher(Height(slkNode->sLink[RIGHT]),
Height(slkNode->sLink[LEFT])
) + 1;
// calcula o balancoh atual no noh
iBalance
= Balance(slkNode);
if (iBalance < -1 || iBalance > 1)
{
BOOL
bDouble;
iDir
= (iBalance > 1);
iBalance
= Balance(slkNode->sLink[iDir]);
bDouble
= iDir ? (iBalance < 0) : (iBalance > 0);
if (bDouble)
slkNode->sLink[iDir]
= Rotate(slkNode->sLink[iDir],
!iDir);
slkNode =
Rotate(slkNode, iDir);
}
}
}
// retorna a
si mesmo
return
slkNode;
}
|
Função:
|
DelNodeAvl
|
Propósito:
|
Remover um bloco de dados em uma árvore AVL
|
Parâmetros:
|
SBINTREE *BST -> ponteiro para estrutura de dados que trata a árvore
c/ ponteiros paras funções de comparação e tratamento de duplicados
void *pData -> informação a ser excluída da árvore
|
Retorno:
|
Nenhum
|
Descrição:
|
Ao receber o bloco de informação apontado por pData, é criado um nó
que será utilizado para procurar o dado a ser removido na árvore, para isso
acontecer, está função é ponto de entrada para chamada recursiva
RemoveNodeAvl que irá percorrer a árvore.
|
void
DelNodeAvl(SBINTREE *BST, void *pData)
{
SLINK slkFind;
slkFind = CreateNode(BST, pData); // cria o noh e
passa o endereco
if
(slkFind) // conseguiu alocar o noh
{
BSTRoot->sLink[RIGHT]
= RemoveNodeAvl(BST,
BSTRoot->sLink[RIGHT],
slkFind);
}
}
|
As alterações
no código feitas em btdriver.c foram
feitas para poder suportar as duas árvore criada no arquivo principal para
efeitos de comparação foi incluída uma árvore binária simples e uma árvore AVL
de busca binária.
int main(int argc, char
*argv[])
{
SBINTREE *BT, *AVL;
// configura
a estrutura de dados da arvore binária
BT = CreateBinTree( CreateData,
DeleteData,
DuplicatedNode,
NodeDataCmp,
PrintData);
AVL =
CreateBinTree(CreateData,
DeleteData,
DuplicatedNode,
NodeDataCmp,
PrintData);
// controla
as opcoes para teste
// na arvore
criada
// possui um
loop interno que serah finalizado
// quando o
usuario escolher a opcaoh
Menu(BT, AVL);
// libera
toda a memoria utilizada pela arvore binária
DestroyBinTree(BT);
DestroyBinTree(AVL);
return (EXIT_SUCCESS);
}
|
Todo o
controlador para teste incluído no exemplo visto em árvore binária genérica
parte 2 permanece, com as operações sendo realizadas simultaneamente em duas árvores,
o que irá permitir realizar uma comparativo entre as duas árvores resultantes.
( 1 ) Inserir
( 2 ) Apagar
( 3 ) Busca
( 4 ) Carrega arquivo
( 5 ) Descarrega arquivo
( 6 ) Imprime
( 7 ) Salva
( 0 ) Sair
Escolha umas das alternativas anteriores : 1
Incluir palavra : q
Incluir palavra : w
Incluir palavra : e
Incluir palavra : r
Incluir palavra : t
Incluir palavra : y
Incluir palavra : u
Incluir palavra : i
Incluir palavra : o
Incluir palavra : p
Incluir palavra : a
Incluir palavra : s
Incluir palavra : d
Incluir palavra : f
Incluir palavra : g
Incluir palavra : h
Incluir palavra : j
Incluir palavra : k
Incluir palavra : l
Incluir palavra : z
Incluir palavra : x
Incluir palavra : c
Incluir palavra : v
Incluir palavra : b
Incluir palavra : n
Incluir palavra : m
Incluir palavra :
( 1 ) Inserir
( 2 ) Apagar
( 3 ) Busca
( 4 ) Carrega arquivo
( 5 ) Descarrega arquivo
( 6 ) Imprime
( 7 ) Salva
( 0 ) Sair
Escolha umas das alternativas anteriores : 6
+-(3) z
+-(2) y
| +-(3) x
+-(1) w
| | +-(5) v
| | +-(4) u
| | +-(3) t
| | | +-(4) s
| +-(2) r
+-(0) q
| +-(4) p
| +-(3) o
| | |
+-(7) n
| | |
| +-(8) m
| | |
+-(6) l
| | | +-(5) k
| | +-(4) j
| +-(2) i
| | | +-(5) h
| | | +-(4) g
| | +-(3) f
+-(1) e
| +-(3) d
| | +-(4) c
| | +-(5) b
+-(2) a
Total de nohs: 26
Profundidade: 8
+-(4) z
+-(3) y
| +-(4) x
+-(2) w
| | +-(4) v
| +-(3) u
+-(1) t
| | +-(3) s
| +-(2) r
+-(0) q
| +-(4) p
| +-(3) o
| | +-(4) n
| |
+-(5) m
| +-(2) l
| | +-(3) k
| | +-(4) j
+-(1) i
| +-(4) h
| +-(3) g
| | +-(4) f
+-(2) e
| +-(4) d
+-(3) c
| +-(5) b
+-(4) a
Total de nohs: 26
Profundidade: 5
|
No
exemplo acima já é possível ver como a inserção aleatória (ordem do teclado) dos
caracteres resulta em uma árvore menor e melhor distribuída, como sempre fica
aqui a sugestão de baixar dois livros em domínio publico do
projeto Gutenberg,
para que se possa utilizar as opções 4 e 5 para ter um volume de teste maior.
Em
termos de desempenho as operações de rotação (esquerda e direita) possuem o
tempo fixo uma vez que apenas alguns ponteiros estão sendo alterados. Atualizar
a altura e calcular o fator de balanço também tem o tempo de execução constante.
Tempo de inserção e exclusão das rotinas AVL permanece igual à de uma árvore de
busca binária que consiste em
0(a)
onde
a é a altura da árvore, uma vez
que esta árvore se mantém balanceada , sua altura é
O(logn).
A árvore
AVL resulta em uma árvore mais balanceada quando comparada a outras árvores de
busca binária, em parte devido ao maior numero de rotações executadas quando
adiciona ou retira nós, caso a aplicação exija um grande numero de inserções e
exclusões, outras opções podem ser consideradas.
