Please enable JavaScript.
Coggle requires JavaScript to display documents.
TREES: Buscas balanceadas, Mudando apenas o numero de nós nas sub-arvores…
TREES: Buscas balanceadas
Tempo de eficiência
Normal
Omega (LOG N)
Pior
Omega (N)
ADTs que preservam, boas propriedades da TBS
Self-balancing
a arvore é transformada em uma arvore balanceada, com suas definições de balanceamento, diferindo uma implementação de outra
Instance-simplification variety
AVL Tree
As alturas dos nós da esquerda e direita nunca excede um
Red-Black Tree
tolera a altura duas vezes, que a sub arvore
Caso o altura exceda isso a arvore é reestruturada
transformações chamadas
Rotações
representation-change variety
B-Trees
2-3 Trees
2-3-4 Trees
AVL Tree
Uma árvore AVL é uma árvore de pesquisa binária em que o fator de equilíbrio década nó, que é definido como a diferença entre as alturas do nó
Rotação
Rotação à direita
Conecta a raiz com o nó filho da esquerda
Rotação a esquera
Conecta a raiz com o nó filho da direita
Rotação dupla esquerda-direita
Primeiro é executado a l-Rotation followed by the R-Rotatition
Rotação dupla direita-esquerda
Primeiro é executado a l-Rotation depois a R-Rotatition
Eficiencia
Numero de nós(N), é o responsável por esse ponto
Pior caso
Omega (LOG N)
Mudando apenas o numero de nós nas sub-arvores