Meu trabalho bolado

Sumário

Ávores AVL
Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade. As árvores binárias de pesquisa são projectadas para um acesso rápido à informação. O nome AVL vem de seus criadores Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962
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 depesquisa, 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 edireita é no máximo 1. Uma outra definição para árvores AVL será aquela em que paraqualquer 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árvoreesquerda 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,5no caso de uma árvore binária de pesquisa e no caso de uma árvore AVL .

Diferenciação
Árvore Binária de Pesquisa Árvore AVL

Se o factor