Arvores binarias c

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2822 palavras )
  • Download(s) : 0
  • Publicado : 17 de julho de 2011
Ler documento completo
Amostra do texto
ÁRVORE AVL
ÁRVORE BALANCEADA Sucessivas inserções e remoções de nós em uma árvore binária de pesquisa fazem com que existam diferenças entre os níveis das suas folhas, o que acarreta grandes diferenças de performance no acesso a seus nós. No pior caso, se os dados já estão ordenados, a árvore será uma lista, perdendo toda a eficiência da busca. Nesses casos, diz-se que a árvore ficou degenerada.Uma árvore é dita balanceada quando, para qualquer nó, as suas sub-árvores à esquerda e à direita possuem a mesma altura. Isso equivale a dizer que todos os ponteiros nulos estão no mesmo nível, ou seja, que a árvore está completa. Isso nem sempre é possível, por conta do número de nós da árvore. Um critério mais simplificado seria considerar uma árvore balanceada se o número máximo de nós da sub-árvore esquerda diferencie no máximo 1 da sub-árvore direita.

BALANCEAMENTO ESTÁTICO Consiste em construir uma nova versão de uma árvore binária de pesquisa, reorganizando-a. Essa reorganização possui duas etapas: 1. Percurso in-ordem sobre a árvore, para gerar um vetor ordenado com o conteúdo de todos os seus nós. 2. Criação de uma ABP a partir desse vetor, da seguinte forma: a)Identifica-se o nó médio do vetor, que passa a ser considerado a raiz da ABP que está sendo criada. b) Cada uma das metades do vetor é tratada analogamente, de modo que cada nó intermediário será a raiz de uma sub-árvore.

BALANCEAMENTO DINÂMICO: AVL Em 1962, dois matemáticos russos (Adelson-Velskii e Landis) definiram uma nova estrutura para balanceamento de árvores ABP e deram o nome de AVL. Esta novaestrutura permite o balanceamento dinâmico da árvore e com boa performance. Fator de Balanceamento (FB) de um nó É a altura da subárvore direita do nó menos a altura da subárvore esquerda do nó. Inserção AVL: O que pode acontecer quando um novo nó é inserido numa árvore balanceada? Na árvore abaixo:

-

Nós 9 ou 11 podem ser inseridos sem balanceamento. Subárvore com raiz 10 passa a ter umasubárvore e subárvore com raiz 8 vai ficar melhor balanceada. Inserção dos nós 1, 3, 5 ou 7 requerem que a árvore seja rebalanceada.

2 Seja T uma árvore AVL na qual serão feitas inserções de novos nós. Para que a árvore se mantenha AVL (ABP e balanceada), é preciso efetuar operações de rebalanceamento quando necessário. A idéia consiste em verificar, após cada inclusão, se algum nó ficoudesbalanceado, isto é, se a diferença de altura entre as 2 sub-árvores ficou maior do que 1. Em caso afirmativo, aplicam-se as transformações apropriadas para rebalanceálo. Torna-se então necessário que a estrutura dos nós da árvore contenha mais um campo (bal) além dos já existentes (ESQ, INFO e DIR). Este novo campo armazenará o Fator de Balanceamento (FB) de cada nó. Veja abaixo como será a estrutura dedados para uma árvore AVL: typedef _____ telem; typedef struct no { struct no *esq; telem info; int bal; struct no *dir; } tno; typedef tno *tavl;

Serão utilizadas 4 transformações, indicadas nas figuras dos casos abaixo. Observe que as subárvores T1, T2, T3 e T4 podem ser vazias ou não. O ponteiro T aponta para o nó raiz p, que é o nó raiz da transformação. Observe que a ordem dos nós nopercurso inordem é preservada em todas as rotações, e portanto é possível aplicar qualquer número de rotações sobre uma árvore para torná-la balanceada, sem alterar a ordem dos nós. Ou seja, as transformações preservam a árvore como sendo ABP. Vamos analisar o que pode ocorrer durante o processo de inserção em uma árvore AVL - e aí vai ficar claro o contexto em que estas transformações são aplicadas.Suponha que um nó q foi inserido em uma árvore AVL T. Se, após a inserção todos os nós de T permanecem balanceados, a árvore continua AVL. Caso contrário, seja p o nó mais próximo às folhas de T que ficou desbalanceado (ou seja, o ancestral mais jovem que ficou desbalanceado). Observe que não há ambigüidade na escolha de p, pois qualquer sub-árvore de T que se tornou desbalanceada após a inclusão...
tracking img