Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dicionários como Árvores Binárias - Coggle Diagram
Dicionários como Árvores Binárias
Uma das principais formas de representar um dicionário é com uma árvore binária ordenada
Uma das principais formas de representar um dicionário é com uma árvore binária ordenada
Por um lado, essa representação apresenta uma eficiência de classe logarítmica nos casos médios de inserção, acesso e remoção de itens
Por outro, casos específicos e variações do número de descendentes de um nódulo faz com que essas eficiências sejam da classe linear para os piores casos
Árvores Balanceadas
Para aproveitar das qualidades das árvores binárias balanceadas evitando seus defeitos nos piores casos, foram buscadas outras formas de representar um dicionário por árvores
Uma delas é fazer com que as árvores se mantenham balanceadas
Árvores que fazem isso são chamadas árvores de auto-balanceamento
As formas de realizar o balanceamento dependem da implementação
A outra forma é permitir a presença de mais de um elemento por nódulo
Árvores AVL
Árvores AVL são árvores binárias de auto-balanceamento que impoẽm um limite de 1 na diferença das alturas das subárvores de cada nódulo
Quando uma operação de inserção ou remoção gera um árvore desbalanceada, elas se reestruturam através de uma operação especial chamada rotação
A rotação ocorre no nódulo que gerou o desbalanceamento ou, se houver mais de um nódulo excedendo o o fator de balanceamento, na subárvore enraizada no nódulo mais próximo do recém-inserido
As rotações que mantém a árvore balanceada fazem com que as operações de busca, inserção e remoção sejam bastante eficientes, mas a manutenção constante do balanceamento da árvore inpediu que as árvores AVL virassem a implementação padrão dos dicionários
"Rotação" na verdade qualifica um grupo de operações que podem ser realizadas no balanceamento da árvore
Existem, no total, 4 tipos de rotações, mas elas podem ser separadas em dois subtipos
Rotações singulares
Imaginando a representação gráfica de uma árvore, essa rotação seria rotacionar os caminho entre uma raiz e seu filho de um determinado lado de forma que o filho se tornasse a nova raiz
Essa rotação pode acontecer...
2 more items...
Rotações duplas
Primeiro é realizada uma rotação singular para um lado em uma raiz r, depois outra rotação é realizada para outro lado na nova árvore enraizada em r
Elas podem acontecer nas seguintes ordens:
2 more items...
As rotações podem ser transformações bastante complicadas, mas são realizadas em tempo constante
Elas não apenas movem filhos e subárvores de lugar como mantem as propriedades da árvore binário organizada
Essa diferença é chamada fator de balanceamento