Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvore de busca balanceada - Coggle Diagram
Árvore de busca balanceada
auto balanceamento
árvore AVL
as alturas das subárvores esquerda e direita de cada nó nunca podem exceder 1
fator de equilíbrio: diferença entre as alturas das subárvores esquerda e direita do nó (só pode assumir valores 1, 0 e -1)
rotações
rotação única à direita (R-rotation)
rotação única à esquerda (L-rotation)
rotação dupla esquerda-direita (LR-rotation)
rotação dupla direita-esquerda (RL-rotation)
eficiência logarítmica no pior caso
inserção e deleção logarítmicas
pontos negativos
rotações constantes
necessidade de manter equilíbrio entre seus nós
árvore rubro-negra
tolera a altura de uma subárvore ser o dobro da outra subárvore do mesmo nó
árvore splay
se a inserção ou remoção de um nó afeta o equilíbrio da árvore, ela se reestrutura para restaurar o equilíbrio por meio de uma transformação chamada
rotação
aumento da quantidade de elementos armazenados por um nó
árvore 2-3
árvore 2-3-4
árvore-B