Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL - Coggle Diagram
AVL
-
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; na verdade, dois deles são imagens espelhadas dos outros dois
O primeiro tipo de rotação é chamado de rotação única à direita ou rotação R. É realizada após a inserção de uma nova chave no subárvore esquerda do filho esquerdo de uma árvore cuja raiz tinha o saldo de +1 antes do inserção
A rotação simétrica única à esquerda, ou rotação L, é a imagem espelhada do rotação R única. É executado 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). Ele é 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
-
-
é 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 do nó subárvores esquerda e direita, é 0 ou +1 ou -1
-
Uma árvore AVL requer que a diferença entre as alturas das subárvores esquerda e direita de cada nó nunca exceda 1
foram inventadas em 1962 por dois cientistas russos, GM Adelson-Velsky e EM Landis