Árvores binárias de pesquisa com balanceamento
Algoritmos e Estruturas de Dados II

Árvores binárias de pesquisa
Pior caso para uma busca é O(n)
1
Ordem de inserção:
132456
3

2

4

5

6

2

Árvore completamente balanceada
Nós folha (externos) aparecem em no máximo dois níveis diferentes
Minimiza o tempo médio de pesquisa
Assumindo distribuição uniforme das chaves

Problema: manter árvore completamente balanceada após cada inserção é muito caro

3

Árvore completamente balanceada
Para inserir a chave 1 na árvore à esquerda e manter a árvore completamente balanceada precisamos movimentar todos os nós

4

Árvores “quase balanceadas”
Objetivo:
Funções para pesquisar, inserir e retirar eficientes
O(lg(n))

Solução intermediária que mantém a árvore
“quase balanceada”, em vez de tentar manter a árvore completamente balanceada

5

Árvores “quase balanceadas”
Várias formas de definir e construir uma árvore
“quase balanceada”
Exemplos de restrições aplicadas a árvores para fazê-las “quase balanceadas”
Fazer que todas as folhas aparecem no mesmo nível
Restringir a diferença entre as alturas das subárvores de cada nó
Minimizar o comprimento do caminho interno da árvore

8=0+1+1+2+2+2

6

Árvores SBB
Uma árvore SBB é uma árvore binária com apontadores verticais e horizontais, tal que:
Todos os caminhos da raiz até cada nó externo possuem o mesmo número de apontadores verticais
Não podem existir dois apontadores