Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL trees, Captura de Tela 2022-03-12 às 00.47.59, Captura de Tela 2022-03…
AVL trees
Rotação - transformação da subárvore cujo balance factor da raiz ficou com 2 ou -2, possuem o objetivo de manter a árvore ordenada (feita no nó mais próximo do novo elemento inserido)
L rotation - espelhamento da R rotation, feita após a inserção na direita do filho direito de uma raiz com balance factor de -1
LR rotation - rotação L na subárvore a esquerda da raiz r + rotação R na nova árvore com raiz em r, feita após a inserção na subárvore a direita no filho à esquerda de uma raiz com balance factor +1
R rotation - feita após a inserção na esquerda do filho esquerdo de uma raiz com balance factor de 1
RL rotation - espelhamento da rotação LR, feita após a inserção na subárvore a esquerda no filho à direita de uma raiz com balance factor -1
Eficiência
floor(log2n) ≤ h < 1,4405 log2(n+2) - 1,3277, sendo n o número de nós e h a altura
-
-
Árvore binária de busca, onde o balance factor de cada nó é 0, 1 ou -1
Se a inserção desordenar a árvore, uma rotação é feita
A diferença entre a altura das subárvores da direita e da esquerda não podem ser maiores que 1 para todo nó
Balance factor - diferença da altura entre as subárvores da esquerda e da direita (obs: raiz não conta no cálculo da altura)
-
-
-
-
-
-
-
