Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees - Coggle Diagram
Balanced Search Trees
BST: Search, insertion, deletion: Θ(log n) no caso médio
Θ(n) no pior caso
Como preservar as boas características da BST? Duas maneiras se destacam
Árvores AVL: uma árvore de busca binária não-balanceada se torna balanceada
São chamadas "self-balancing trees". Elas se auto balanceiam
Se o equilíbrio da árvore for quebrado com uma adição ou remoção de um nó a árvore é reestruturada através de uma "rotação", restaurando assim o equilíbrio
Existe uma família de transformações especiais chamadas rotações!
Rotações também serão utilizadas em árvores AVL caso a adição de um nó a desequilibre
Se tiverem muitos nós desequilibrados a transformação é feita na raiz do nó desequilibrado mais próximo a folha inserida
1 more item...
As rotações são transformações não-triviais que podem ser realizadas em tempo constante, e garantem os requisitos mínimos de uma árvore balanceada e de uma BST
A altura de uma árvore continua sendo o critério principal na determinação da eficiência dela
1 more item...
"Red black tree": a altura de uma subárvore é no máximo o dobro da altura da outra subárvore no mesmo nó
Definindo: a diferença entre a altura das subárvores direita e esquerda da AVL não excede 1.
Diferença entre a altura das subárvores esquerda e direita de cada nó (fator de equilíbrio) assume três valores: -1, 0, +1
Mudança de representação: mais de um elemento no nó!
Árvores 2-3, 2-3-4, B-trees
Possuem diferenças no número de elemtentos no nó, mas todas são balanceadas
Mudança de instância, mais simples!