Please enable JavaScript.
Coggle requires JavaScript to display documents.
6.3 Balanced Search Trees (246) - Coggle Diagram
6.3 Balanced Search Trees (246)
Na transformação de um conjunto(set) para uma árvore de pesquisa binária é um exemplo da técnica de mudança de representação.
Nessa transformação ganhamos na eficiência do tempo de busca, inserção e exclusão, que estão todos em (log n), mas apenas no caso médio. No pior caso, essas operações estão em (n) porque a árvore pode degenerar em uma árvore gravemente desequilibrada com altura igual a (n − 1).
AVL Tree
Uma árvore AVL é uma árvore de pesquisa binária na qual o fator de equilíbrio de cada nó, que é definido como a diferença entre as alturas das subárvores esquerda e direita do nó, é 0 ou +1 ou −1
-1 -> aŕvore vazia
Se a inserção de um novo nó desequilibra uma árvore AVL, transformamos a árvore por uma rotação
Rotações
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, giramos a árvore com raiz no nó desequilibrado que está mais próximo da folha recém-inserida
Existem apenas quatro tipos de rotações;
1.
2.
3.
4.
rotação dupla direita-esquerda (rotação RL) (double right-left rotation (RL-rotation))
2 more items...
Rotação dupla esquerda-direita (rotação LR) (double left-right rotation (LR- rotation))
É, 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
É realizado após uma nova chave ser inserida na subárvore direita do filho esquerdo de uma árvore cuja raiz tinha saldo +1 antes da inserção.
rotação única esquerda simétrica, ou rotação L (symmetric single left rotation, or L-rotation,)
é a imagem espelhada da rotação R única.
É realizado após uma nova chave ser inserida na subárvore direita do filho direito de uma árvore cuja raiz tinha saldo -1 antes da inserção.
rotação única à direita ou rotação R. (single right rotation, or R-rotation)
realizada após uma nova chave ser inserida na subárvore esquerda do filho esquerdo de uma árvore cuja raiz tinha saldo +1 antes da inserção.
girar para a direita a aresta que conecta a raiz e seu filho esquerdo na árvore binária
não devem apenas garantir que a árvore resultante seja balanceada, mas também preservar os requisitos básicos de uma árvore de busca binária.