Árvores (2,3) e Árvores B
Katia Guimarães
5 de novembro de
2015
1
Árvores de Busca com grau maior do que 2
Vimos que árvores de busca quando
balanceadas, como as árvores AVL,
permitem busca em tempo logarítmico.
No caso das árvores AVL, a busca se
dá em tempo log2 (n) no pior caso.
Poderíamos tentar melhorar procurando
fazer a busca em tempo logk (n), com k > 2.
Árvores 2-3
Similar às árvores AVL, mas
- Cada nó interno tem dois ou três filhos e
- Todos os nós externos têm a mesma
profundidade.
P
G
T
C
A
KM
F
[email protected]
H
L
R
O
Q
X
S
V
Z
3
Inserção em Árvores 2-3
Como nas árvores AVL, a inserção se dá
numa folha. Se há espaço para acrescentar
o novo elemento, ele entra aí.
Ex: Inserção do elemento G na árvore abaixo.
T
I
EG
[email protected]
VX
LP
U
W
Z
4
Inserção em Árvores 2-3
Se não há espaço para acrescentar o novo
elemento, gera-se dois nós com os dois
elementos extremos no nó, e promove-se
o elemento central, para ser incluído no
nível imediatamente superior.
Ex: Inserção do elemento N na árvore abaixo.
T
I
EG
VX
LP
N
[email protected]
U
W
Z
5
Inserção em Árvores 2-3
Ex: Inserção do elemento N na árvore abaixo.
Como um nó não pode ter três elementos, são criados dois nós
com um elemento cada, e o elemento do meio é promovido.
T
I N
EG
L
[email protected]
VX
P
U
W
Z
6
Inserção em Árvores 2-3
Se não há espaço para acrescentar o nó
promovido, procede-se da mesma forma que
no overflow anterior, até eventualmente
achar espaço suficiente ou chegar até a raiz.
Ex: Inserção do elemento C na árvore abaixo.
T
I N
EG
L
VX
P
U
W
Z
C
[email protected]
7
Inserção em Árvores 2-3
Se não há espaço para acrescentar o nó
promovido, procede-se da mesma forma que
no overflow anterior, até eventualmente
achar espaço suficiente ou chegar até a raiz.
Ex: Inserção do elemento C leva à promoção do elemento E.
I
E
C
T
N
G
L
[email protected]
VX
P
U
W
Z
8
Inserção em Árvores 2-3
Ex: Inserção do elemento C leva à promoção do elemento E
que por sua vez leva à promoção do elemento I.
IT
E
C
N
G
[email protected]
L
VX
P
U
W
Z
9
Árvores B
Note que a diferença crucial em termos de tempo de
acesso entre a árvores binárias e as árvores 2-3 é que
agora o acesso pode ser feito em tempo logarítmico,
mas com base 3, o que é mais rápido.
Podemos pensar então numa forma de diminuir mais
ainda o tempo de acesso, aumentando o número de
elementos em cada nó.
[email protected]
10
Árvores B
ÁRVORES B são uma extensão da noção de árvores 2-3,
onde cada nó que não é a raiz pode ter entre k e 2k chaves.
Esta estrutura normalmente é usada em memória externa.
Deve haver um compromisso entre o maior número de
elementos por nó e a capacidade de acesso em disco,
além de uma técnica de busca dentro do nó.
[email protected]
11