Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa mental 8 - Coggle Diagram
Mapa mental 8
Capítulo 6: "
Transform and Conquer
".
Seção 6.3: "
Balanced Search Trees
".
A transformação de um conjunto para uma árvore de busca binária é um exemplo da técnica de mudança de representação.
E também é uma boa transformação, visto que as eficiências de tempo das operações de busca, adição e remoção ficam todas em \(Θ(\log n)\) no caso médio.
No pior caso, quando a árvore está degenerada e tem altura igual a \(n-1\), elas estão em \(Θ(n)\).
Os cientistas da computação se esforçaram para encontrar uma estrutura que preserve as boas características da árvore de busca binária, principalmente a eficiência logarítmica de tempo, mas não tenha a degeneração do pior caso.
A primeira abordagem diz respeito à
variedade de simplificação de instância
, em que uma árvore de busca binária não balanceada se torna balanceada.
Dessa forma, essas árvores são chamadas de árvores de busca binária de
auto-equilíbrio
.
Uma árvore
AVL
requer que a diferença entre as alturas das subárvores da direita e da esquerda não exceda \(1\).
1 more item...
Uma árvore
vermelho-escuro
requer que a altura de uma subárvore seja no máximo o dobro que a outra subárvore do mesmo nó.
Se a adição ou remoção de um novo nó violar o equilíbrio requerido, a árvore é reestruturada por uma de uma família de transformações especiais chamada de
rotações
, que restaura o equilíbrio.
A segunda é da variedade de mudança de representação: a qual permite mais de um elemento em um nó de uma árvore de busca.
Alguns casos específicos dessa árvores são:
Árvores \(2-3.\)
1 more item...
Árvores \(2-3-4\).
1 more item...
Árvores B
1 more item...