Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arvores de Busca Balanceada - Coggle Diagram
Arvores de Busca Balanceada
É uma estrutura de dados que possui um elemento principal chamado de raiz
A raiz forma duas subárvores
A subárvore da
esquerda
tem todos os elementos ordenados que são
menores
que a raiz
A subárvore da
direita
tem todos os elementos ordenados que são
maiores
que a raiz
A sua complexidade tanto para inserção, remoção e busca é
Big O
da altura dessa árvore
Na inserção, remoção e busca ganha-se na
eficiência do tempo
tendo em vista que se encontra em
Log(n)
Porém, a eficiência de tempo se encontra em
Log(n)
no
médio caso
por isso a necessidade da árvore estar
balanceada
Por isso, temos árvores de
auto equilíbrio
São elas a
árvore AVL
e a
ávore Vermelho Escuro
Árvore AVL
Na árvore AVL a
diferença de altura
das subárvores de cada nó nunca ultrapassam
1
Árvore Vermelho Escuro
Na árvore Vermelho Escuro aceita uma
diferença de altura
sendo o dobro de outra de outra subárvore
Caso uma árvore perca o seu equilíbrio ele pode ser devolvido por meio de
rotações
Rotações
são transformações locais da subárvore cujo saldo do nó ultrapassou o limite permitido
1 more item...