aula07

Prévia do material em texto

7ºAula
ÁRVORES B
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• compreender como funciona uma Árvore B;
• entender as operações possíveis em uma Árvore B.
Olá,
Nesta aula, vamos finalizar os estudos sobre as Árvores. 
Estudaremos um tipo de árvore que é muito utilizado nos 
sistemas de armazenamento. Trata-se das Árvores B, onde a sua 
definição e o seu processo de inserção serão o assunto principal 
da nossa aula.
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
47
Estrutura de Dados II 46
1. 
Seções de estudo
Introdução a Árvores B
2. Operações em uma Árvore B
1 - Introdução a Árvores B
Vocês devem saber que, normalmente, armazenamos 
nossos dados para uso futuro em dispositivos de 
armazenamento secundário de dados. Até o surgimento dos 
Discos de Estado Sólido (SSD), que usam a mesma tecnologia 
presente nos pendrives e cartões de memória, os dispositivos 
que faziam esse papel nos computadores eram os discos 
rígidos.
 Dentro dos discos rígidos temos uma série de pratos, 
que funcionam de forma análoga a um disco de vinil: uma 
agulha percorre os setores do disco e lê os dados armazenados 
no setor. 
Figura 1 - Parte interna de um disco rígido. Fonte: Disponível em: < https://www.
2018.
Apesar dos avanços na tecnologia, a velocidade dos 
discos rígidos sempre foi um gargalo nos computadores. 
Vejam esse comparativo:
Dispositivo Ta a de Transferência(em megabytes por segundo)
HD com conector IDE 133
HD com conector SATA 150 150
HD com conector SATA II 300
SSD mais simples 550
SSD mais avançado 2000
Memória RAM DDR2-800 6400
Memória RAM DDR3-1333 10664
Memória RAM DDR4-2133 17064
Fonte: Dados extraídos dos sites: < https://www.tecmundo.com.br/placa-
tecmundo.com.br/hardware/102277-hd-comum-hd-alta-velocidade-descubra-
das-mem%C3%B3rias-ram-r34433/ >. Acesso em: 23 set. 2018.
Assim, os cientistas da computação sempre procuraram 
formas de otimizar o acesso aos dados. Uma dessas tentativas 
foi criar uma árvore onde o seu objetivo era minimizar a 
quantidade de acesso aos dados. A solução consiste em 
armazenar um conjunto de dados em cada nó da árvore. Cada 
dado possui um ponteiro para a árvore com valores menores 
do que o seu e um ponteiro para a árvore com valores maiores 
do que o seu. Esse é o fundamento básico da Árvore B.
A figura 2 mostra uma árvore B. O nó M é a sua raiz. 
Assim como a árvore binária, temos ponteiros para as 
subárvores maiores e menores que o dado. Mas, a diferença 
é que na árvore binária os ponteiros são em relação ao nó, 
pois cada nó armazena um único dado. No caso da árvore B, 
os ponteiros são em relação ao dado, não em relação ao nó. 
Como o nó raiz só tem um dado, temos apenas dois ponteiros.
Na subárvore direita temos os valores que são maiores 
que M. O nó raiz dessa subárvore tem três dados: Q, T e X. 
Nesse nó temos quatro ponteiros: Os nós que são menores 
que Q, os nós que estão entre Q e T, os nós que estão entre T 
e X, e os nós que são maiores que X.
Para buscar um dado precisamos percorrer os dados 
desse nó para procurar se o dado está nesse nó ou deve estar 
em algum dos ponteiros para uma subárvore. Por exemplo, se 
estamos procurando a letra R, começamos pela raiz. Seguimos 
o caminho pela subárvore direita de M. Depois, vasculhamos 
todos os dados da raiz da subárvore direita de R. Seguimos 
pelo ponteiro que está entre T e X. Chegamos então, ao nó 
com a letra R. 
percorridos para chegar a letra R. Fonte: (CORMEN et. al, 2012, p. 352).
Além disso, visando a otimização da árvore, existe 
uma quantidade mínima de dados a ser armazenados, e 
uma quantidade máxima, que é equivalente a 2x-1, sendo x 
a quantidade mínima de dados a ser armazenados. Assim, 
cada nó pode ter de x+1 a 2x filhos. Uma árvore B, em que 
fixamos a quantidade mínima de dados como 2, pode ter de 
1 a 3 dados (que também são chamados de chaves) e de 2 a 
4 filhos.
Formalmente, podemos definir uma árvore B como uma 
árvore T, que possui uma raiz (denominado de T.raiz), que 
tem as seguintes características:
• Grau mínimo da árvore t, que determina os limites 
inferiores e superiores da quantidade de chaves do 
nó.
 Todo nó (exceto a raiz) tem pelo menos t-1 chaves.
 Todo nó (exceto a raiz) tem pelo menos 2t-1 chaves.
• Cada nó x tem as seguintes informações:
 A quantidade n de chaves (dados) armazenados, 
denominado de x.n.
 As chaves, denominados de x.chave, que armazena 
de forma crescente os dados. Os dados estão dispostos de 1 
até n.
48
47
• Um atributo booleano folha (x.folha) que indica se 
esse nó é folha. Se configurado como verdadeiro, o 
nó é folha. Se for falso, ele possui filhos.
• Cada nó interno x contêm n+1 ponteiros, 
denominados de x.c[1] até x.c[n+1], que apontam 
para os seus filhos.
• As chaves separam os intervalos armazenados em 
cada subárvore.
• Toda folha tem a mesma profundidade, que é a 
altura h da árvore.
• Uma árvore B pode ter as seguintes variações:
• Árvore 2-3-4: é uma árvore B mais simples, onde t 
= 2. Assim, cada nó pode ter apenas 2, 3 ou 4 filhos.
• Árvore B*: é um tipo de árvore B que exige que cada 
nó esteja 2/3 completo.
• Árvore B+: nesse tipo de árvore, ela armazena os 
dados somente nas folhas. A raiz e os nós internos 
só armazenam ponteiros.
Mas, por que a árvore B é útil para a nossa situação? 
Vamos para um exemplo. Suponhamos que queremos 
armazenar um bilhão de chaves em uma árvore. Enquanto 
que em uma árvore binária, poderemos ter uma altura de no 
mínimo 23 níveis, em uma árvore B que armazena no máximo 
1000 chaves, poderemos ter uma árvore de 3 níveis. E terá 
espaço de sobra.
Figura 3 - Árvore B com mais de 1 bilhão de chaves, com a sua altura 3 (ou 2, 
(CORMEN et. al, 2012, p. 355).
Agora que você sabe o que é uma árvore B e o seu uso, 
vamos para as operações que são realizadas em uma árvore B.
2 - Operações em uma Árvore B
Assim como em toda árvore, a árvore B tem operações 
de manipulação e busca dos dados. Nesta aula, vamos 
apresentar como funciona os algoritmos de busca e inserção 
de dados em uma árvore B. Além disso, vamos abordar como 
criar uma árvore B vazia.
2.1 - Buscando dados em uma 
árvore B
A busca de dados em uma árvore B segue o seguinte 
fluxo, dado a raiz da árvore e o valor a ser buscado:
• Percorre todos os valores presentes no nó, até 
que encontramos o índice i do primeiro valor que 
não seja menor que o valor que estamos buscando 
dentro do nó.
• Ao pararmos, vamos verificar se o índice i se refere 
ao valor que estamos procurando. Se for, retornamos 
o nó e o respectivo índice.
• Se não for o valor que estamos procurando, 
verificamos se o nó é folha. Se for, indica que o valor 
não foi encontrado na árvore. Retornamos NULO;
• Se não for um nó folha, a busca prossegue no filho 
que se refere apontado pelo ponteiro do índice i da 
árvore.
A seguir, apresentamos o pseudocódigo da operação de 
busca em uma árvore B.
funcao busca(x: *TArvore, k: inteiro): 
*TArvore, inteiro
declare
 i : inteiro
inicio
 i <- 1
 enquanto (i <= x.n E k > x.chave[i]) faca
 i <- i + 1
 fimenquanto
 se (i <= x.n E k = x.chave[i] entao
 // Achou
 retorne (x, i)
 senao
 se (x.folha) entao
 // Se nao achou o valor e é folha, 
nao temos
 retorne NULO
 senao
 //Lê um filho do nó
 leia-disco(x.c[i])
 retorne busca(x.c[i], k)
 fimse
 fimse
fimalgoritmo
Agora, vamos mostrar como funciona o processo de 
criação de uma árvore B.
2.2 - Criando uma árvore B
Para criar uma árvore B seguimos os seguintes passos:
• Alocamos um novo nó x.
• Marcamos esse novo nó x como folha.
• Indicamos o seu número de dados presentes como 
0, pois não temos nenhum dado nessa árvore.
• Escrevemos esse nó no disco e marcamos ele como 
a raiz da árvore.
O pseudocódigo desta operação demonstramos a seguir:
procedimento criarArvoreB()
declarex: *TArvore
início
 x <- alocaNo()
 x.folha <- VERDADEIRO
 x.n <- 0
 escreve-disco(x)
 T.raiz <- x
fimprocedimento
2.3 - Adicionando nós a árvore
Devido à natureza de uma árvore B, a operação de 
49
Estrutura de Dados II 48
inserção não é tão trivial, pois precisamos adicionar os valores 
a um nó já existente, para respeitarmos a regra de número 
mínimo e máximo de valores que estão em uma árvore B. 
Basicamente, o processo consiste em buscar em qual nó 
deve ser inserido o novo valor. Se o nó que for escolhido 
como local do novo valor estiver cheio, devemos dividir os 
valores do nó em dois, escolhendo um valor mediano. Esse 
valor mediano é promovido a condição de pai dos dois subnós. 
Vale lembrar que se o nó onde o dado será promovido estiver 
cheio, devemos fazer a separação da mesma forma.
Esse processo se chama de repartição do nó. Esse 
processo consiste em receber um nó interno x não cheio 
e um índice i que aponta para um nó cheio de x. Esse 
procedimento divide esse filho apontado pelo nó x.c[i] em 
dois. Detalhadamente, podemos definir esse processo nos 
seguintes passos:
• Alocamos um novo nó z.
• Declaramos uma nova variável y, que recebe o 
ponteiro x.c[i]. Nesse caso, y tem todos os valores 
do nó a ser repartido.
• z recebe a indicação se y é ou não é folha e tem o 
seu valor n indicado com a quantidade mínima de 
nós admitidos.
• Depois, percorremos os valores de chave de y nas 
posições 1+t a t-1 e preenchemos os valores 1 a t-1 
do nó z. Por exemplo, se t for 4, o nó z recebe os 
valores das posições 5 a 7 do nó y.
• Se y não for folha, percorremos os valores dos 
ponteiros das posições t+1 até 2t de y e passamos 
para o nó z, tornando os valores acima do nó médio 
como sendo filhos de z. Em uma árvore de t = 4, o 
nó z recebe os ponteiros da posição 5 a 8 do array 
c do nó y.
• Em seguida, atualizamos a quantidade de valores do 
nó y como t-1.
• Depois, atualizamos os ponteiros do nó x, colocando 
os ponteiros que estarão após o valor a ser 
promovido na próxima posição. Assim, o ponteiro 
c[5] será alocado na posição c[6], o ponteiro c[6] 
ficará na posição c[7], e assim sucessivamente. Em 
seguida, colocamos o ponteiro c[i+1] no valor do nó 
z, passando a apontar para z.
• Em seguida, fazemos essa operação de forma análoga 
com os valores das chaves do nó x, postergando eles 
para a próxima posição. Depois colocamos o valor 
médio do nó filho cheio entre as chaves do nó x. 
Assim, promovemos ele a condição de “pai” dos 
nós y e z.
• Depois, atualizamos a quantidade de nós de x, e 
escrevemos os nós x, y e z dentro do disco.
A seguir, apresentamos o código dessa operação:
procedimento divideNo(x: *TArvore, i: 
inteiro)
declare
 z, y: *TArvore
 j : inteiro
inicio
 z <- alocaNo()
 y <- x.c[i]
 z.folha <- y.folha
 z.n <- t - 1
 
 para i de 1 ate (t - 1) faca
 z.chave[j] <- y.chave[j+t]
 fimpara
 se (nao(y.folha)) entao
 para j de 1 ate t entao
 z.c[j] <- y.c[j+t]
 fimpara
 fimse
 y.n <- t-1
 
 para j de (x.n+1) ate i+1 passo -1 faca
 x.c[j+1] <- x.c[j]
 fimpara
 x.c[i+1] <- z
 para j de x.n ate i passo -1 faca
 x.chave[j+1] <- x.chave[j]
 fimpara
 x.chave[i] <- y.chave[t]
 
 x.n <- x.n +1
 escreva-disco(y)
 escreva-disco(z)
 escreva-disco(x)
fimalgoritmo 
t=4. A chave mediana S é promovida à condição de pai dos novos subnós. Fonte: 
(CORMEN et. al., 2012, p. 359).
Agora que mostramos como funciona a divisão do nó, 
vamos mostrar como funciona o algoritmo de inserção. Ele 
consiste em dois procedimentos. O primeiro é o procedimento 
InsereArvore, que recebe uma chave k, um ponteiro T para a 
árvore. Esse procedimento segue os seguintes passos:
• r recebe a raiz da árvore.
• Verifica se a raiz está cheia. Se estiver cheia, criamos 
um nó s e dividimos o nó raiz em dois, usando o 
procedimento divideNo, para colocar o nó mediano 
no novo nó s e dividir o nó em dois. Depois 
chamamos o procedimento auxiliar insereNaoCheio 
usando o nó s.
• Se não estiver cheio chamamos o procedimento 
insereNaoCheio usando o nó r.
O procedimento insereNaoCheio abordaremos a 
seguir. Agora, vamos mostrar como é o pseudocódigo do 
procedimento InsereArvore:
procedimento InsereArvore(T: *Arvore, k: 
50
49
inteiro)
declare
 r, s: *TArvore
inicio
 r <- T.raiz
 se r.n = (2t-1) entao
 #Cria o nó s e divide a raiz
 s <- alocaNo()
 T.raiz <- s
 s.folha <- FALSO
 s.n <- 0
 s.c[1] <- r
 divideNo(s,1)
 insereNaoCheio(s,k)
 senao
 insereNaoCheio(r,k)
 fimse
fimalgoritmo
com t=4. A chave mediana S é promovida à condição de pai dos novos subnós e de 
Al., 2012, p. 361).
O procedimento insereNaoCheio faz a inserção 
propriamente dita da chave k na árvore. Esse procedimento 
recebe um ponteiro para um nó da árvore, denominado de x e 
o valor “k” a ser inserido. Ela segue os seguintes passos:
• Verifica se o nó x é folha. Se for, o procedimento 
coloca os valores das chaves que são maiores que 
k nas posições subsequentes a atual. Logo, um 
dado que estava na posição 2 passa a posição 3, um 
dado que estava na posição 3 ficará na posição 4, e 
assim sucessivamente. Esse processo ocorre até que 
todas as chaves estejam percorridas ou quando é 
encontrado uma chave menor que o valor k. O valor 
k é inserido na posição i+1 após o percurso pelos 
valores do nó. Depois, o valor n de x é atualizado.
• Se o nó não for folha, o procedimento procura o 
próximo nó filho a ser lido pelo procedimento. 
Assim, o algoritmo percorre os valores do nó x até 
quando encontrarmos um valor que seja menor que 
o valor “k” a ser inserido. Depois lemos a posição 
do ponteiro c[i] de x, e verificamos a necessidade de 
dividir o nó apontado por x.c[i]. Se for, dividimos 
esse nó chamando o método divideNo. Em seguida, 
verificamos em qual subárvore seguir, atualizando o 
valor de i;
• Finalmente, chamamos o mesmo procedimento 
recursivamente para o nó apontado pelo ponteiro 
x.c[i].
A seguir, mostraremos o pseudocódigo deste 
procedimento.
procedimento insereNaoCheio(x: *TArvore, k: 
inteiro)
declare
 i : inteiro
inicio
 i <- x.n
 se (x.folha) entao
 enquanto i >= 1 e k < x.chave[i]
 x.chave[i+1] <- x.chave[i]
 i <- i-1
 fimenquanto
 x.chave[i+1] <- k
 x.n <- x.n + 1 //Atualiza a qtde n
 escreva-disco(x)
 senao
 enquanto i >= 1 e k < x.chave[i]
 i <- i-1
 fimenquanto
 i <- i+1
 leia-disco(x.c[i])
 se x.c[i].n = 2t-1 entao
 //No cheio - divide
 divideNo(x, i)
 se k > x.chave[i] entao
 i <- i + 1
 fimse
 fimse
 
 insereNaoCheio(x.c[i], k)
 fimse 
fimalgoritmo
E com isso, finalizamos a nossa aula. Na próxima aula, 
vamos mostrar como funciona a compactação de arquivos. 
Até lá!
Retomando a aula
Chegamos ao nal da nossa sétima aula. Vamos 
relembrar?
1 - Introdução a Árvores B
Nessa seção, vimos que uma árvore B é uma árvore T, que 
possui uma raiz (denominado de T.raiz), que tem as seguintes 
características: Grau mínimo da árvore t, que determinam os 
limites inferiores e superiores da quantidade de chaves do nó, 
sendo que todo nó (exceto a raiz) tem pelo menos t-1 chaves 
e tem pelo menos 2t-1 chaves; Nesta árvore cada nó x tem 
as seguintes informações: A quantidade n de chaves (dados) 
armazenados, denominado de x.n; as chaves denominados 
de x.chave, que armazena de forma crescente os dados. Os 
dados estão dispostos de 1 até n, e um atributo booleano 
folha (x.folha) que indica se esse nó é folha. Se configurado 
como verdadeiro, o nó é folha. Se for falso, ele possui filhos. 
51
Estrutura de Dados II 50
Cada nó interno x contêm n+1 ponteiros, denominados de 
x.c[1] até x.c[n+1], que apontam para os seus filhos; as chaves 
separam os intervalos armazenados em cada subárvore e toda 
folhatem a mesma profundidade, que é a altura h da árvore.
2 - Operações em uma Árvore B
Nesta aula, aprendemos como funcionam os principais 
algoritmos de manipulação de dados em uma árvore B, 
que são o algoritmo de busca de um dado e o algoritmo de 
inserção de um dado.
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
KNUTH, Donald Ervin. The art of computer programming. 
3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, 
Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: 
LTC, 1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe 
J.; LANGSAN, Yedidyah. et al. Estruturas de dados usando 
C. São Paulo: Pearson Makron Books; São Paulo: Makron 
Books do Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com 
implementação em PASCAL e C. 3. ed. São Paulo: Cengage 
Learning, 2011.
Vale a pena ler
FEOFILOFF, Paulo. Árvores B (B-trees). USP, 2018. 
Disponível em: <https://www.ime.usp.br/~pf/estruturas-
de-dados/aulas/B-trees.html>. Acesso em: 23 set. 2018.
GALLES, David. B Tree Visualization (Simulador de 
Árvore B). USF, s.d. Disponível em: <https://www.cs.usfca.
edu/~galles/visualization/BTree.html>. Acesso em: 23 set. 
2018. 
Vale a pena acessar
Vale a pena
Minhas anotações
52