Árvores avl

Estruturas de Informação Árvores AVL _______________________________________________________________________________________________

ÁRVORES AVL
As árvores binárias de pesquisa são projectadas para um acesso rápido à informação. Idealmente a árvore deve ser razoavelmente equilibrada e a sua altura será dada (no caso de estar completa ), como já vimos anteriormente por h=log2 (n+1) – 1, isto é de O(log2 n), sendo n o número total de elementos da árvore. Contudo, com alguns dados, a árvore binária de pesquisa pode degenerar, tendo no pior caso altura n -1, tornado-se o acesso muito mais lento, O(n). É o que acontece no caso em que a construção da árvore é feita por inserções sucessivas e os valores são dados com chaves ordenadas (crescentes ou decrescentes). Assim, vamos analisar um tipo de estrutura que nos dá o poder das árvores binárias de pesquisa, sem ocorrerem as condições do pior caso que esta última apresenta. Estudaremos então as árvores AVL, em que cada nó está equilibrado em altura, significando isto que, em cada nó, a diferença de alturas entre as subárvores esquerda e direita é no máximo 1. Uma outra definição para árvores AVL será aquela em que para qualquer nó P se verifica que o módulo do factor de equilíbrio é sempre < ou = 1. Entende-se por factor de equilíbrio de um nó P a diferença da altura da subárvore esquerda de P e altura da subárvore direita de P. Factor de Equilíbrio(P)= altura(filho_ direito(P))-altura(filho_esquerdo(P)) As árvores abaixo representadas evidenciam o caso da introdução dos valores 1,2,3,4,5 no caso de uma árvore binária de pesquisa e no caso de uma árvore AVL . Árvore Binária de Pesquisa Árvore AVL

Se o factor de equilíbrio num nó é negativo, significa que a altura da subárvore esquerda é maior (em 1) do que a altura da subárvore direita, diremos então que o nó é pesado à esquerda. Se o factor de equilíbrio num nó é positivo, significa que a altura da subárvore direita é maior (em 1) do que a altura da subárvore