Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL - Coggle Diagram
AVL
Uma árvore AVL é uma árvore binária de busca na qual o fator de equilíbrio de cada nó, que é definido como a diferença entre as alturas dos nós das subárvores esquerda e direita. Esse fator de equilíbiro pode ser 0, +1 ou −1.
-
Se a inserção de um novo nó torna uma árvore AVL desbalanceada, transformamos
a árvore por uma rotação.
Uma rotação em uma árvore AVL é uma transformação local de sua subárvore enraizada em um nó cujo saldo se tornou +2 ou −2.
Se houver vários desses nós, rotacionamos a árvore enraizada no nó desbalanceado que é o mais próximo da folha recém-inserida.
Existem apenas quatro tipos de rotações, em que duas delas são apenas imagens espelhadas dos outros dois.
Especificamente, a altura h de qualquer árvore AVL com n nós satisfaz as desigualdades.
-
Encontrar uma fórmula exata para a altura média de uma árvore AVL construída para listas aleatórias de chaves provou ser difícil, mas sabe-se por extensos experimentos que é cerca de 1,01log2 n + 0,1, exceto quando n é pequeno.
Assim, pesquisar em uma árvore AVL requer, em média, quase o mesmo número de comparações que pesquisar em uma matriz ordenada por busca binária.
A operação de exclusão de chave em uma árvore AVL é consideravelmente mais difícil do que a inserção, mas felizmente acaba por estar na mesma classe de eficiência que a inserção, ou seja, logarítmica.
As desvantagens das árvores AVL são as rotações frequentes e a necessidade de manter o equilíbrio de seus nós.
Essas desvantagens impediram que as árvores AVL se tornassem a estrutura padrão para a implementação de dicionários.
Ao mesmo tempo, sua ideia subjacente – a de reequilibrar uma árvore de busca binária por meio de rotações – provou muito frutífera e levou a descobertas de outras variações interessantes do árvore de busca binária clássica.
O primeiro tipo de rotação é chamado de rotação única à direita ou rotação R. É executado após uma nova chave ser inserida na subárvore esquerda do filho esquerda de uma árvore cuja raiz tinha saldo de +1 antes da inserção.
A rotação simétrica única à esquerda, ou rotação L, é a imagem espelhada da rotação R única. É executad após uma nova chave ser inserida na subárvore direita do filho direito de uma árvore cuja raiz tinha o saldo de -1 antes da inserção.
O segundo tipo de rotação é chamado de dupla rotação esquerda-direita (rotação LR). É, na verdade, uma combinação de duas rotações: realizamos a rotação L da subárvore esquerda da raiz r seguida pela rotação R da nova árvore enraizada em r. É executado após uma nova chave ser inserida na subárvore direita do filho esquerdo de uma árvore cuja raiz tinha o saldo de +1 antes da inserção.
-
As rotações não apenas devem garantir que uma árvore resultante seja equilibradas, mas também devem preservar os requisitos básicos de uma busca binária árvore.
as desigualdades implicam imediatamente que as operações de busca e inserção são theta(log n) no pior caso.