Árvores Balanceadas

Prévia do material em texto

Adriana Carvalho da Cruz
Árvores Balanceadas
Corumbá - MS
2016
Adriana Carvalho da Cruz
Árvores Balanceadas
Trabalho sobre tipos de árvores balanceadas,
para a disciplina de Estruturas de Dados e
Programação.
Universidade Federal do Mato Grosso do Sul - UFMS
Campus Pantanal
Sistemas de Informação
Orientador: Luiz Felipe de Souza Jimenez
Corumbá - MS
2016
Resumo
Ao utilizar uma das estruturas de árvore balanceada, é importante compreender que cada
tipo possui suas particularidades, tendo como foco no desenvolvimento de problemas
específicos. É muito utilizado em empresas, onde utiliza métodos eficientes na inserção,
busca ou até remoção de alguma informação. O foco principal é resolver problemas de forma
eficiente, sempre olhando qual o melhor percurso ou ferramenta para implementar um
sistema. Árvores são essenciais na programação, por mostrar a estrutura e como o programa
é organizado, tendo uma conexão com toda a programação, eficiência e interagindo entre
o programa através de chamadas de funções.
Lista de ilustrações
Figura 1 – Modelo de uma árvore . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Figura 2 – Exclusão do nó pai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Figura 3 – Exclusão do nó filho . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Figura 4 – Rotação a direita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Figura 5 – Rotação dupla a direita . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Figura 6 – Rotação a esquerda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Figura 7 – Rotação dupla a esquerda . . . . . . . . . . . . . . . . . . . . . . . . . 15
Figura 8 – Árvore Rubro-Negra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Figura 9 – Pseudo-código da inserção RB . . . . . . . . . . . . . . . . . . . . . . . 20
Figura 10 – Pseudo-código da remoção RB . . . . . . . . . . . . . . . . . . . . . . . 22
Figura 11 – Unidade de um disco típico . . . . . . . . . . . . . . . . . . . . . . . . 25
Figura 12 – ÁrvoreB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Figura 13 – Pseudocódigo árvore B . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Figura 14 – Técnicas de Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Figura 15 – Técnicas de remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Sumário
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 ÁRVORE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1 Árvore Binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 ÁRVORE AVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1 Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 ÁRVORE RUBRO-NEGRA . . . . . . . . . . . . . . . . . . . . . . . 17
3.1 Rotações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 ÁRVORE B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1 Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5
Introdução
Este trabalho visa discutir sobre técnicas diferenciadas balanceamento, através de
árvores de modelos diferentes, como é a funcionalidade de cada uma, desde uma árvore
binária que pode-se dizer que foi onde tudo começou ou quase tudo, servindo como ponto
importante no desenvolvimento de técnicas mais eficientes que ela mesma, começando pela
árvore AVL que possui uma eficiência no sentido de busca, tornando a cada tipo de novas
técnicas mais eficientes ao passar do tempo e como base para a árvore Rubro-Negra que
segue a linha de pensamento da AVL com o bit para coloração, como o nome da árvore
mesmo diz rubro (vermelho) e negra (preta), cada nó tem uma coloração.
A árvore B dentre todas que foram discutidas é a técnica mais difícil de implementar,
pois possui várias particularidades, como a diferença da forma do crescimento, enquanto
as árvores ABB, ARN e AVL crescem de cima para baixo de forma ordenada, a árvore B
cresce de baixo para cima, sendo que a cada nova altura ela cresce mais nas laterais do
que para cima, criando novas possibilidades de inserção.
Este trabalho foi dividido em: capitulo 1- Árvore, descrevendo o que é uma árvore,
tendo um subitem 1.1 sobre Árvore Binária. O capitulo 2 trata sobre Árvore AVL e
suas propriedades, sendo dividido em 2.1 inserção e 2.2 remoção.O capitulo 3 trata da
Árvore Rubro-Negra e suas particularidades, sendo explanado os subintens 3.1 rotações,
3.2 Inserção e 3.3 Remoção. O capitulo 4 é sobre a Árvore B e como ela é estruturada, suas
divisões nos subitens foram 4.1 Busca, 4.2 Inserção e 4.3 Remoção. E por fim o capitulo 5
que é a conclusão.
6
1 Árvore
Árvores são estruturas que funcionam de forma hierárquica em relação aos dados,
possuindo um conjunto de nós e vértices. A árvore de estruturas de dados é representada
de baixo para cima, iniciando com a raiz, tendo os galhos, filhos e as folhas. São diferentes
das árvores naturais, que são de baixo para cima.(BAILEIRO, 2015) em seu livro descreve
uma árvore da seguinte forma:
Diferente das árvores naturais, que têm sua origem de baixo para cima,
uma estrutura de dados em forma de árvore é representada de cima para
baixo. A árvore é composta de nós e arestas (conexões). Os nós, deno-
minados também com vértice, são estruturas de dados que representam
as informações a serem processadas. As arestas são as conexões entre
os nós. Conexões podem ser do tipo: unidirecional ou bidimensional. O
tipo unidirecional pode ir apenas de um nó para o outro, mas não pode
fazer o caminho contrário. Já o bidirecional pode de qualquer nó chegar
a outro. Sendo que o topo é representado pelo nó raiz e os demais nós se
conectam a ele, ou a outro que já esteja conectado a ele. O nó raiz é o
nó pai dos demais. Um nó pai pode estar conectado a vários nós filhos.
Cada nó filho pode estar conectado à apenas um nó pai. A exceção fica
por conta do nó raiz que não tem nó pai. (Balieiro, 2015, p.23).
A árvore de estruturas de dados segue o desenho de uma árvore natural, isso
significa que ela precisa ter raiz, de outra forma a árvore não existe, é nula, com ligações
com as outras partes que são os galhos, que tem ligação com as folhas que são nós sem
filhos ou nó terminal, na figura 1 é possível visualizar uma árvore natural e uma árvore de
estruturas de dados, mostrando a raiz da árvore, as ramificações, os galhos e as folhas que
é aonde termina a árvore, a árvore estruturada possuí raiz que diferente da árvore cresce
de cima para baixo, tendo a ligação com os galhos que são os nós, e os nós apresenta uma
ligação até encontrar o nó folha que não recebe ninguém até ser inserido um novo elemento
na árvore.
Figura 1: Modelo de uma árvore
Capítulo 1. Árvore 7
1.1 Árvore Binária
É uma estrutura de conjunto finito de elementos que pode ser predefinidos, que
não ter nenhum elemento, ela está vazia, ou ter nó raiz sem subárvore esquerda e direita,
apontando os dois lados da árvore para nulo, ou ainda, ser uma árvore com raiz que aponta
para a subárvore esquerda e subárvore direita, esse tipo de árvore é estritamente binária
com n folhas. No site da (UNICAMP, b) uma árvore binária é definida como:
...aárvore de busca binária ou árvore de pesquisa binária é uma árvore
binária onde todos os nós são valores, todo nó a esquerda contêm uma
sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os
nós da sub-árvore a direita contêm somente valores maiores ao nó raiz.
(Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo
da aplicação). Os valores são relevantes na árvore de busca binária. O
objetivo desta árvore é estruturar os dados de forma flexível permitindo
pesquisa binária. Nó são todos os itens guardados na árvore. Raiz é o
item do topo da árvore. Filho são os itens logo abaixo da raiz. Parente
são os nós do mesmo nível. Folha é um nó que não tem filho, é o último
item da árvore.
Na página da internet Brasport é possível entender que a árvore possui um caminho a
ser percorrido dentro da árvore que são as sequências de nós, onde nó j é pai de nó j+1,
formando um caminho de comprimento k-1. O nível de uma nó por sua vez é definido
como o nó raiz possui nível 0, e os filhos tem o nível igual a 1 os sucessores do filhos são
os netos que tem nível 2 e assim sucessivamente, tendo sempre o filho um nível a mais que
o seu pai. A altura do nó é o comprimento do maior caminho percorrido do nó raiz até
um dos descendentes folha.
Uma árvore completa é uma árvore estritamente binária, onde todas as folhas
se encontram no mesmo nível. Seguindo a mesma linha de pensamento da Unicamp o
(UNICAMP, a) define o objetivo de uma árvore de busca binária da seguinte forma:
O objetivo de organizar dados em árvores de busca binária é facilitar
a tarefa de procura de um determinado valor. A partir da raiz e de
posse da informação a ser encontrada, é possível saber qual o caminho
(galho) a ser percorrido até encontrar o nó desejado. Para tanto, basta
verificar se o valor procurado é maior, menor ou igual ao nó que se
está posicionando. Deve-se observar que não existe uma única forma de
organizar um conjunto de informações em uma árvore de busca binária,
afinal, dependendo da escolha do nó raiz, obtêm-se árvores diferentes.
A árvore binária pode inserir, buscar, remover e imprimir os valores postos na
árvore. É fundamental primeiro definir a estrutura da árvore, definindo o nome, uma
variável como valor do tipo int, e os ponteiros esquerdo e direito, após a definição da
estrutura podemos dizer que a árvore está nula e criarmos a estrutura insere, onde será
criado a função para inserir um elemento na árvore.
Inserção: é feita verificando primeiro se a árvore é nula, se for insere o valor na
raiz, apontando a subárvore esquerda e subárvore direita para nulo. Após a inserção na
Capítulo 1. Árvore 8
raiz da árvore, ela passa a não ser nula precisando criar uma condição para verificar se o
nó é menor que raiz ou se nó é maior que raiz, caso seja menor antes de inserir é feita
uma busca para ver se o elemento já existe na árvore, se existir emite um mensagem
dizendo que elemento já “existe”, se não existir, insere na subárvore esquerda, se elemento
for maior que a raiz insere na subárvore direita. É preciso entender que o valor antes de
ser inserido é comparado com o nó raiz. O nó raiz é sempre o primeiro elemento que foi
inserido, o novo elemento a ser inserido sempre será um nó folha.
Busca:para efetuar uma busca é preciso iniciar examinando a raiz, verificando se
o valor é igual a raiz, se for igual retorna a verificação encontrando o valor, se for diferente
compara se o valor é menor que a raiz se for menor percorre a subárvore esquerda fazendo
comparações até encontrar, encontrando retorna o valor, se não tiver o valor na árvore,
informa que “elemento não encontrado!”. Quando o elemento é maior que a raiz, em vez
de buscar na subárvore esqueda, faz-se uma varredura na subárvore direita, comparado os
elementos do nó com o elemento que está sendo buscado, se encontrar o elemento retorna
“elemento encontrado!”, caso contrário informa que elemento não foi encontrado na árvore.
Exclusão:primeiro é feita uma busca para verificar se o elemento está na árvore,
fazendo comparações primeiro com a raiz, até chegar na folha, comparando se elemento é
maior ou menor que o elemento anterior. Existem três casos:
• Exclusão na folha: o elemento a ser removido é uma folha.
• Exclusão de um nó com um filho:exclui o nó, e o nó avó passa a fazer ligação
com o nó neto, ou seja, é excluído o nó pai da folha. É possível ver a exclusão na figura 2.
Figura 2: Exclusão do nó pai
• Exclusão de um nó com dois filhos:pode ser feito de duas formas diferentes.
A primeira substituindo valor entre o valor a ser retirado com o valor sucessor (o nó mais
a esquerda da subárvore direita) ou pelo valor antecessor (o nó mais à direita da subárvore
esquerda), substituindo os valores e removendo o nó agora na folha, como exemplo a seguir
da figura 1.3. O nó com valor 30 será removido, mas possui sucessor e antecessor imediato
40 e 35, foi feita uma troca entre o 35 e o 30, tornando o 35 nó pai do 40, recebendo como
filho o nó 37 que é uma folha e o 45 que já era filho do 40.
O percurso que uma árvore percorre pode ser de três formas: em ordem, pré ordem
ou pós ordem. A (UNICAMP, b) explica que:
Uma característica interessante é quando se faz um percurso em ordem
em uma árvore binária de busca. Ao efetuar esse percurso os valores
Capítulo 1. Árvore 9
Figura 3: Exclusão do nó filho
dos nós aparecem em ordem crescente. A operação “percorre” tem como
objetivo percorrer a árvore numa dada ordem enumerando os seus nós.
Quando um nó é enumerado, dizemos que ele foi “visitado”.
• Percurso em ordem:primeiro percorre a subárvore esquerda até chegar na
folha, começa a visita percorrendo a subárvore esquerda, visita a raiz e percorre a subárvore
direita, imprimindo de forma ordenada esquerda, raiz, direita.
• Percurso pré ordem:primeiro visita a raiz, percorre a subárvore esquerda e a
subárvore direita, fazendo uma impressão de forma a imprimir primeiro raiz, esquerda,
direita.
• Percurso pós ordem:percorre a subárvore esquerda, percorre a subárvore
direita e por último imprime a raiz, a ordem fica: esquerda, direita e raiz.
O nível de um nó raiz é 0 e os outros níveis são maiores uma unidade do nível pai.
A altura do nó é o número de nós do maior caminho. Uma árvore binária tem 0, 1 ou dois
filhos o pai, a raiz pode ser nula, o pai pode ter 0 filhos, isso significa que é nó folha, se
tiver 1 filho é nó pai e no máximo dois filhos.
10
2 Árvore AVL
A árvore AVL surgiu nos meados de 1962 pelos matemáticos Adelson Velskii e
Landis que proporão em vez de utilizar um balanceamento estático em uma árvore binária
de pesquisa seria preciso reorganizar uma árvore, calculando a altura da árvore.
No balanceamento estático era preciso pegar uma árvore binária e reorganizar
utilizando o percurso em ordem sobre a árvore, gerando um vetor ordenado, criando uma
árvore binária de pesquisa. (EGYPTO, 2004) descreve em sua apostila de estruturas de
dados que um balanceamento estático consistem em:
...construir uma nova versão de uma árvore binária de pesquisa, reorganizando-
a. Essa reorganização possui duas etapas: 1. Percurso in-ordem sobre a
árvore, para gerar um vetor ordenado com o conteúdo de todos os seus
nós. 2. Criação de uma ABP a partir desse vetor, da seguinte forma: a)
Identifica-se o nó médio do vetor, que passa a ser considerado a raiz da
ABP que está sendo criada. b) Cada uma das metades do vetor é tratada
analogamente, de modo que cada nó intermediário será a raiz de uma
sub-árvore. (2004, p.57)
Uma árvore balanceada não seria tão fácil de ser feita, por ser preciso fazer
modificações iniciais que em uma árvore binária funcionaria muito bem, mas com uma
deficiência em relação ao tempo. Já o balanceamento dinâmico apesar de ter um grau de
dificuldade maior que uma árvore binária de busca proporciona com que a busca seja mais
rápida ou eficiente. (EGYPTO, 2004) descreve por suavez o balanceamento dinâmico:
Em 1962, dois matemáticos russos (Adelson-Velskii e Landis) definiram
uma nova estrutura para balanceamento de árvores ABP e deram o
nome de AVL. Esta nova estrutura permite o balanceamento dinâmico
da árvore e com boa performance. Fator de Balanceamento (FB) de um
nó É a altura da subárvore direita do nó menos a altura da subárvore
esquerda do nó. (2004, p.57)
Árvore AVL é uma árvore que possui as propriedades de uma árvore binária de
busca, contendo um fator de balanceamento para deixar a árvore balanceada. Esta árvore
tem a finalidade de manter a árvore balanceada, rebalancendo as subárvores quando for
preciso, ou a árvore toda, utilizando o fator de balanceamento para calcular. A árvore AVL
é altamente balanceada. O diferencial da AVL para a ABB é a altura da árvore, mantendo
o mais próximo possível balanceada, diferindo apenas em -1, 0 ou 1 na altura da subárvore
esquerda da direita, caso contrário é feita um dos tipos de rotação.A altura é O(log n),
utilizando o fator de balanceamento que é calculado da seguinte forma:
FB=he – hd
ou
FB=hd – he
Capítulo 2. Árvore AVL 11
É preciso definir qual dos dois será utilizado, sendo o mais comum o primeiro.
FB significa o cálculo do fator de balanceamento que é igual ao he (altura da subárvore
esquerda) – hd (altura da subárvore direita), sendo possível o segundo exemplo, tendo
apenas que inverter a ordem da explicação. Sendo balanceada quando os valores do FB é
-1, 0 ou 1. -1 ocorre quando a subárvore direita é mais alta que a esquerda. 0 subárvore
esquerda e direita são da mesma altura. 1 quando a subárvore esquerda é mais alta que
a direita. Quando o fator é menor que -1 ou maior que 1, ela está desbalanceada.Esta
árvore é uma árvore binária de altura equilibrada. (BARANAUS, a) descre no site que
uma árvore AVL é balanceada quando:
Através do balanceamento da árvore as operações de busca, inserção
e remoção em uma árvore com n elementos podem ser efetuadas em
O(log2n), mesmo no pior caso. ... Um teorema provado por Adelson
Velskii e Landis garante que a árvore balanceada nunca será 45% mais
alta que a correspondente árvore perfeitamente balanceada, independente
do número de nós existentes.
É preciso definir a estrutura, com nome, a subárvore esquerda, a subárvore direita,
um fator de balanceamento e a informação que será colocada dentro do nó. Conforme
trechos do código a seguir, que mostra uma estrutura de árvore.
1 . typede f _ telem ;
2 . typede f s t r u c t no { //nome da e s t ru tu ra
3 . s t r u c t no ∗ esq ;
4 . telem i n f o ; // i n f o r m a o que c o l o c a r no n .
5 . i n t ba l ; // f a t o r de balanceamento (FB)
6 . s t r u c t no ∗ d i r ;
7 . } tno ; // ape l i do da e s t ru tu ra
8 . typede f tno ∗ t av l ;
Após definir a estrutura é preciso criar as funções.Ao inserir ou remover vários nós
acaba ocorrendo uma diferença entre os níveis das folhas, dando diferença na performance
dos acesso aos nós, perdendo a eficiência da busca, tornando uma árvore degenerada. Uma
árvore balanceada possui a mesma altura dos dois lados da árvore, mas por ser dificultosa
aceita-se que uma árvore está balanceada quando o FB difere em no máximo 1 para mais
ou para menos.
2.1 Inserção
Para inserir um elemento é importante testar se a raiz é nula, se for nula o valor a
ser inserido será a raiz, ao inserir um novo elemento em um nó é preciso calcular o fator
de balanceamento, verificando se a árvore está balanceada, caso contrário será preciso
analisar a árvore e fazer um dos 4 tipos de rotação. Se a raiz não for nula, testa se o valor
é menor que a raiz, se for o novo elemento vai para a esquerda, se for maior que a raiz o
Capítulo 2. Árvore AVL 12
novo elemento irá para a direita, percorrendo nó por nó até encontrar uma posição que
aceita as propriedades definidas no início.
Cada inclusão de um nó é feita o FB, verificando se a árvore difere em algum
ponto sendo 2 ou -2, tendo em vista as propriedades da AVL, será preciso utilizar uma
das rotações para torna-la novamente balanceada.
Ao inserirmos um nó em uma árvore AVL e ela permanece balanceada, ela continua
AVL, caso tenha inserido um novo elemento na folha e ocorra o desbalanceamento o nó
ancestral ficou desbalanceado.
Seja he(x) e hd(x) as alturas da subárvore esquerda e direita de x.
Verifica se (he(x)hD(x)| > 1)
Se for a árvore está balanceada.
Senão verifica se (he(x)-hd(x)|=2)
Se o fator de balanceamento for igual a 2 significa que a árvore está desbalanceada
em algum ponto da árvore, estando desbalanceada justamente onde o FB foi igual a 2,
precisando fazer uma das rotações para que a árvore volte a ocupar a propriedade de árvore
AVL.O desbalanceamento da árvore pode acontecer na raiz, onde uma das subárvores ou
esquerda ou direita apresentam um grau de desbalanceamento superior a 1, tendo que fazer
a rotação, se a subárvore esquerda está maior, será efetuada uma rotação a direita, mas se
for a subárvore direita, a rotação será feita para a esquerda.O desbalanceamento pode ser
efetuado dentro de um nó interno, fazendo a rotação necessária, seguindo a mesma forma
como se utilizasse para a raiz. A rotação a esquerda sai da direita e vai para a esquerda,
a rotação a direita ocorre esquerda para a direita. Existem quatro tipos de rotação para
tornar a árvore balanceada, vamos analisar neste instante:
Rotação a direita:ao inserir um elemento na sub-árvore esquerda a árvore tornou-
se desbalanceada, sendo preciso utilizar a rotação a direita para reorganizar. Alguns trechos
de código fonte do livro de (EGYPTO, 2004) estão sendo mostrado na parte da rotação,
utilizando as figuras 4, 5, 6 e 7 com trechos de códigos que Machado criou.
void rot_dir ( t av l ∗T) {
tav l u ;
u = (∗T)−>esq ;
(∗T)−>esq = u−>d i r ;
u−>d i r = ∗T;
(∗T)−>bal = 0 ;
∗T = u ;
}
Capítulo 2. Árvore AVL 13
Figura 4: Rotação a direita
A função rotação a direita possibilita resolver o problema de uma árvore desbalan-
ceada na subárvore esquerda, ou nos galhos esquerdos a subárvore direita. Reorganiza as
variáveis para organizar aonde está com problema, verifica o FB.
Rotação dupla a direita: essa rotação é quando ocorre uma alteração em algum
ponto na altura da árvore, formando um desenho parecido com um joelho.
void rot_esq_dir ( t av l ∗T) {
tav l u , v ; u = (∗T)−>esq ;
v = u−>d i r ;
u−>d i r = v−>esq ;
v−>esq = u ;
(∗T)−>esq = v−>d i r ;
v−>d i r = ∗T;
i f (v−>bal == −1)
(∗T)−>bal = 1 ;
e l s e (∗T)−>bal = 0 ;
i f (v−>bal == 1)
u−>bal = −1;
e l s e
u−>bal = 0 ; ∗T = v ;
}
A rotação dupla a direita faz dois tipos de rotação, utilizando primeiro a rotação
simples a esquerda, tornando a árvore reta no nó que estava com problemas, seguido de
uma rotação simples a direita, reorganizando a árvore, restabelecendo o balanceamento.
Rotação simples a esquerda:neste caso foi inserido um novo valor na subárvore
direita ou no lado direito da subárvore esquerda, tornando um ponto da árvore desbalan-
ceada, tendo um filho a mais do lado direito.A baixo é possível visualizar trechos de uma
rotação simples a esquerda.
Capítulo 2. Árvore AVL 14
Figura 5: Rotação dupla a direita
void rot_esq ( t av l ∗T) {
tav l u ;
u = (∗T)−>d i r ;
(∗T)−>d i r = u−>esq ;
u−>esq = ∗T;
(∗T)−>bal = 0 ;
∗T = u ;
}
A seguir o código da rotação a esquerda, onde vemos o desenho de uma reta, onde
está desbalanceada do lado esquerdo, por estar com FB=-2.
Figura 6: Rotação a esquerda
Isso significa que uma rotação a esquerda resolve o problema da árvore, tornando
ela novamente balanceada, onde o ponteiro T aponta para a subárvore direita, T na posição
direita rege u apontando para a esquerda realocando e tornando a árvore balanceada
novamente.
Rotação dupla a esquerda:A rotação dupla a esquerda também utiliza dois
tipos de rotação, fazendo primeiro a rotação simples a direita, tornando a árvore reta,perdendo o desenho de joelho aonde ela está desbalanceada o nó que estava com problemas,
Capítulo 2. Árvore AVL 15
seguido de uma rotação simples a esquerda, reorganizando a árvore e balanceando.
void rot_dir_esq ( t av l ∗T) {
tav l u , v ;
u = (∗T)−>d i r ;
v = u−>esq ;
u−>esq = v−>d i r ;
v−>d i r = u ;
(∗T)−>d i r = v−>esq ;
v−>esq = ∗T;
i f (v−>bal == 1)
(∗T)−>bal = −1;
e l s e (∗T)−>bal = 0 ;
i f (v−>bal == −1)
u−>bal = 1 ;
e l s e
u−>bal = 0 ;
∗T = v ;
}
Figura 7: Rotação dupla a esquerda
Após fazer as rotações compara o fator de balanceamento, verificando se realmente
foi balanceado. Toda vez que insere um novo elemento é preciso buscar a posição que o
Capítulo 2. Árvore AVL 16
elemento será inserido e insere, verifica se está balanceado, se está balanceada a inserção
terminou, caso contrário utilizará um dos quatro tipos de rotações para reorganizar a
árvore, tornando as propriedades da AVL válida. O balanceamento será verificado todas
as vezes que inserir ou excluir um elemento, onde é verificado antes da inclusão o fator de
balanceamento, insere modificando o valor de balanceamento.Uma árvore AVL desbalance-
ada equivale a uma árvore Binária de Busca, conforme (MACHADO, 2008).
A operação básica em uma árvore AVL geralmente envolve os mesmos
algoritmos de uma árvore de busca binária desbalanceada. A rotação na
árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples
ocorre quando um nó está desbalanceado e seu filho estiver no mesmo
sentido da inclinação, formando uma linha reta. Uma rotação-dupla
ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado
no sentido inverso ao pai, formando um "joelho". (Machado, 2008).
2.2 Remoção
Antes de remover um elemento da árvore é preciso verificar se o elemento existe na
árvore, caso não esteja na árvore será emitida uma mensagem dizendo que o valor não foi
encontrado. Quando encontra o valor, retorna para o função remoção mostrando que o
valor existe na árvore após as comparações com raiz, e as subárvores conforme a condição.
No site da Unicamp é possível analisar o que eles falam sobre a correção da AVL.
Ao excluir um nó, ou mesmo ao incluir um nó, pode haver o desbalanceamento da
árvore, sendo corrigido, por exemplo, com o balanceamento AVL.
A retirada de um elemento é mais complexa do que a inserção, pois quando um
novo nó está sendo inserido é na raiz, um elemento que será retirado pode ser qualquer nó
tendo um grau maior na remoção. Faz-se a busca do elemento, caso não tenha ocorrido
alterações para tornar a árvore desbalanceada a remoção acaba. A remoção pode ser:
• Nó folha:caso o valor esteja na posição de folha, após a busca, remove o valor do
elemento, verificando o FB, caso seja preciso faz um dos tipos de rotações como explicado
anteriormente.
• Nó tem dois filhos:como no caso da árvore binária de busca, ocorrerá aqui
também, troca-se o valor que deseja remover com o maior valor a esquerda ou o menor
valor a direita da folha, após a troca, faz-se a remoção do nó.
• Nó tem um filho:após buscar e encontrar o elemento, remove o valor, fazendo
um ligação entre o nó avô com o nó filho.
Há complexidade da remoção está no desbalanceamento por remover e a árvore
perder um elemento da folha, reduzindo a altura da mesma, desequilibrando a árvore.
Acontecendo um problema de desbalanceamento terá que reaplicar o método para balancear
novamente, permitindo que ela seja AVL.
17
3 Árvore Rubro-Negra
Árvores rubro-negra também são conhecidas como árvore vermelho e preto, foi
inventada por Bayer e recebeu o nome de “Árvores Binárias Simétricas” em 1972, segue
as propriedades de uma árvore binária de busca, fator de balanceamento e um bit para
armazenar a cor de cada nó que pode ser preto ou vermelho. define como é uma árvore
vermelho e preto.
(CORMEM, 2002)
Uma árvore vermelho-preto é uma árvore de pesquisa binária com um
bit extra de armazenamento por nó: sua cor, que pode ser Vermelho ou
Preto. Restringindo o modo como os nós podem ser coloridos em qualquer
caminho desde a raiz até uma folha, as árvores vermelho-preto asseguram
que nenhum desses caminhos será maior que duas vezes o comprimento
de qualquer outro, de forma que a árvore é aproximadamente balanceada.
Cada nó da árvore contém agora os campos cor, chave, esquerda, direita
e p. Se um filho ou o pai de um nó não existir, o campo do ponteiro
correspondente do nó conterá o valor NIL. (2002,p.220).
Este tipo de árvore mantem-se balanceadas utilizando a coloração em alguns casos,
sem precisar rotacionar toda vez que estiver desbalanceada, esta árvore tem inserção,
remoção e busca, contendo uma estrutura mais complexa que a ABB e a AVL. Por
apresentar uma eficiência maior que a ABB é mais utilizada. O bit é um particularidade
deste tipo de árvore, por causa da cor, possui em sua estrutura um valor, subárvore
esquerda, subárvore direita e o fator de balanceamento.
É uma árvore que insere e remove de forma inteligente, assegurando que a árvore
esteja aproximadamente balanceada, como a AVL que pode considera uma árvore balance-
ada quando difere em no máximo -1 ou 1 da altura de uma subárvore em relação a outra
subárvore.
Para ser considerado como uma árvore vermelho-preto precisa satisfazer todas a
propriedades deste tipo de árvore. Cormem descreve 5 (cinco) propriedades:
1. Todo nó é vermelho ou preto;
2. A raiz é preta;
3. Toda folha (NIL) é preta;
4. Se um nó é vermelho, então ambos os seus filhos são pretos;
5. Para cada nó, todos os caminhos desde um nó até as folhas descendentes contêm o
mesmo número de nós pretos. (2002, p. 220).
Quando faz alguma operação na árvore, utilizando das propriedades, se ocorre de
uma propriedade não estiver em conformidade com o que as regras falam, para arrumar
pode ser atrás de rotação, recoloração ou as duas técnicas dependendo do problema que
surgiu. ARN são boas para pesquisas. O percurso entre o nó raiz até a folha de cada
Capítulo 3. Árvore Rubro-Negra 18
ramificação tem que ter a mesma quantidade de nós pretos, conhecido como altura negra.
A figura 3.1 mostra uma estrutura de uma árvore rubro negra.
O balanceamento é alcançado graças a regras que comporta este tipo, cada elemento da
Figura 8: Árvore Rubro-Negra
árvore possui um valor, o primeiro elemento a ser inserido entra na raiz, sendo inserido
como vermelho e é feita a coloração, transformando a raiz em preto. A raiz é maior que
seus elementos a da subárvore esquerda e menor que a subárvore direita. Nós vermelhos
são inseridos e não podem ser seguidos de vermelho. A altura de uma arvore rubro-negra
depende dos nós pretos da raiz até a folha.
3.1 Rotações
Da mesma forma que a rotação ocorre na AVL, aqui é essencial, por quê manter a
árvore balanceada, mas não é a única técnica utilizada, por conter o bit é possível modificar
a cor do bit e manter a árvore tecnicamente balanceada. (CORMEM, 2002) descreve que
é possível utilizar métodos para balancear a árvore como a seguir:
... devemos mudar as cores de alguns nós na árvore e também mudar
a estrutura de ponteiros. Mudamos a estrutura de ponteiros atráves da
rotação, uma operação local em uma árvore de pesquisa que preserva
a propriedade de árvores de pesquisa binária. ... quando fazemos uma
rotação à esquerda em um nó x, supomos que seu filho da direita y não é
nil[T]. A rotação à esquerda “faz o pivô” em torno da ligação de x para
y. Ela faz de y a nova raiz da subárvore, tendo x como filho da esquerda
de y e o filho da esquerda de y como filho da direita de x. (2002, p.223).
Ao inserir ou remover um nó da árvore sempre terá que verificar as propriedades
da árvore garantindo sempre que ela está seguindo o que define uma rubro-negra.
• Rotação simples à direita:foi inserido um elemento na folha que já possuía
na estrutura da árvore a raiz e um filho esquerdo e o nó folha entrou a esquerda filho
Capítulo3. Árvore Rubro-Negra 19
esquerdo. Neste caso será preciso rotacionar a direita balanceando a árvore e modificando
a cor, tendo a raiz como preto, esquerda e direita da árvore.
• Rotação simples a esquerda:foi inserido um elemento na folha que já possuía
na estrutura da árvore a raiz e um filho direito e o nó folha entrou a direita do filho direito.
Neste caso será preciso rotacionar a esquerda balanceando a árvore e modificando a cor,
tendo a raiz como preto, esquerda e direita da árvore.
• Rotação dupla à esquerda:tenho a raiz, o filho direito da raiz inserido e será
inserido um novo elemento só que a esquerda do filho direito, tornando um joelho. Neste
caso será preciso fazer primeiro uma rotação simples a direita, subindo o nó folha no lugar
do nó pai, descendo o nó pai, tornando o joelho em uma reta, essa é a primeira rotação.
A segunda rotação será como se utilizasse a rotação a esquerda, ou seja, após estar reto,
faz-se uma nova rotação tornando o novo elemento em raiz, a raiz vira filho a esquerda e o
pai fica filho da folha que agora é raiz. É preciso utilizar a coloração para que a árvore
seja vermelho e preto.
• Rotação dupla a direita:tenho a raiz, o filho esquerdo da raiz inserido e será
inserido um novo elemento só que a direita do filho esquerdo, tornando um joelho. Neste
caso será preciso fazer primeiro uma rotação simples a direita, subindo o nó folha no lugar
do nó pai, descendo o nó pai, tornando o joelho em uma reta, essa é a primeira rotação. A
segunda rotação será como se utilizasse a rotação a direita, ou seja, após estar reto, faz-se
uma nova rotação tornando o novo elemento em raiz, a raiz vira filho a direita e o pai fica
filho esquerdo da folha que agora é raiz. É preciso utilizar a coloração para que a árvore
seja vermelho e preto.
3.2 Inserção
Esta árvore precisa de uma busca eficiente, toda vez que for inserir será preciso
verificar se valor já está na árvore, se é raiz, filho esquerdo ou filho direito. Faz uma
varredura para encontrar a posição que o novo nó será inserido, sempre na cor vermelha.
Se árvore vazia, faz-se a inserção na raiz como vermelho e altera a cor para preto.
Uma regra importante é que nó vermelho só tem filhos pretos, já os pretos podem
ter filhos pretos, sendo preciso usar a coloração sempre que dois nós vermelhos forem
seguidos de vermelho.(CORMEM, 2002) apresenta no livro como é feita a inserção em
uma árvore rubro-negra:
A inserção de um nó em uma árvore vermelho-preto de n nós pode ser
realizada no tempo O(lg n). Usamos uma versão ligeiramente modificada
do procedimento TREE-INSERT para inserir o nó z na árvore T como
se ela fosse uma árvore de pesquisa binária comum, e depois colorimos
z de vermelho. Para garantir que as propriedades vermelho-preto serão
preservadas, chamamos então um procedimento auxiliar RB-INSERT-
Capítulo 3. Árvore Rubro-Negra 20
FIXUP para recolorir os nós e executar rotações. A chamada RB-INSERT
(T,z) insere o nó z, cujo campo chave já deve ser preenchido, na árvore
vermelho-preto T. (2002, p. 225).
No caso específico de Cormem, ele utiliza a inserção como uma árvore pesquisa
binária, utilizando como diferencial a parte da coloração. Como podemos visualizar a
figura 9 que mostra trechos do código RB-INSERT.
Figura 9: Pseudo-código da inserção RB
É preciso colocar o nome na função RB-INSERT, após definir o nome, define que y
recebe nil, x recebe a raiz. Faz um enquanto x for diferente de nil, entra em um loop e
verifica a posição [T] y recebe o x, pois a raiz aponta para os nil esquerdo e direito, entrando
em uma condição para testar se o elemento que existe (raiz) é menor que o elemento a
ser inserido, se for verdadeiro o elemento será inserido abaixo do nó raiz na subárvore
esquerda, caso contrário do lado direito. Compara se y é igual a nil, se for verdadeiro cria
os dois nil, esquerdo e direito. Utiliza uma variável para colocação vermelho.
Os casos comuns da inserção são: 1a- quando o valor inserido for raiz, pois a árvore
estava vazia, insere na raiz um elemento com a cor vermelha e depois colore para preto,
cumprindo as regras. 2a – quando o nó a ser inserido é vermelho e possui raiz preta e
dois filhos vermelhos, será preciso modificar a cor do pai e do tio. 3a – quando a árvore
possui a raiz preta, um filho vermelho e insere um novo elemento na mesma subárvore,
será preciso rotacionar ou para a direita ou para a esquerda, dependendo do lado que
está desbalanceado, tornando o nó filho abaixo da raiz o nó pai da raiz e da folha que
foi inserida, recolorindo ambos, pois a raiz será preta e os dois filhos serão vermelhos.
Capítulo 3. Árvore Rubro-Negra 21
Este caso pode utilizar um dos quatro tipos de rotação, conforme a necessidade da sua
resolução, onde foi explicado na seção rotações.
3.3 Remoção
A remoção como a inserção precisa utilizar a busca para encontrar o elemento,
antes seria inserido e neste caso será removido, desbalanceando em um ponto da árvore,
sendo preciso fazer a coloração ou um dos tipos de rotações, mas sem inserir elemento e
sim retirando, lembrando que o elemento foi removido e precisou reestruturar a árvore,
tornando ela dentro das propriedades de uma ARN, essas mudanças ocorrerão apenas
se durante a retirado do elemento foi destruída/quebrada alguma operação. A remoção
possui o caso de remoção:
• O nó removido possui dois filhos: neste caso será preciso trocar o nó pai
com um dos filhos ou a direita ou a esquerda (o menor filho a direita ou o maior filho a
esquerda), após a troca é só remover o filho, verificar o fator de balanceamento e caso
seja preciso trocar de cor ou fazer uma das rotações. Se o nó removido for vermelho será
removido sem causar grandes alterações na árvore, mas se o nó for preto será alterado o
percurso entre a raiz até aquele ponto específico precisando altera a cor ou efetuar algum
tipo de rotação.(CORMEM, 2002) diz que a remoção é:
Como as outras operações básicas em uma árvore vermelho-preto de n
nós, a eliminação de um nó demora o tempo O(log n). A eliminação
de um nó de uma árvore vermelho-preto é apenas ligeiramente mais
complicada que a inserção de um nó. O procedimento RB-DELETE é
uma modificação secundária do procedimento TREE-DELETE. Após
extrair um nó, ele chama um procedimento auxiliar RB-DELETE-FIXUP
que muda as cores e executa rotações para restaurar as propriedades
vermelho-preto. (2002, p. 231).
A remoção é um pouco mais complicada que a inserção, dependendo da posição
onde o valor foi retirado será preciso reorganizar ou até mudar as cores. A remoção
conforme Cormem utiliza de uma coloração para restaurar as propriedades ARN. A figura
10 mostra o trecho do código que Cormem mostra em seu livro.
É possível observar que ele cria um função chamada RB-DELETE, onde ele testa
as possibilidades, se a esquerda e direita recebe nil significa que é uma folha, removendo e
apontando para o valor anterior se for uma folha que tem elementos acima do elemento
que foi removido, caso contrário é um raiz, e a árvore fica vazia. Testa também se o nó a
esquerda é diferente de nulo, se for é nó pai, precisando verificar a quantidade de filhos, se
for um filho, remove e realoca o avô no neto, se tiver dois filhos precisará trocar de valor
com o filho e eliminado o elemento. Verifica se árvore desbalanceou e se precisa de uma
rotação para voltar a balancear ou se trocando a coloração já resolve o problema.
Capítulo 3. Árvore Rubro-Negra 22
Figura 10: Pseudo-código da remoção RB
23
4 Árvore B
Diferente das outras árvores balanceadas que crescem de cima para baixo a árvore
B ou 123 cresce sempre de baixo para cima, mantendo propriedades específicas para esta
espécie, são árvores criadas para trabalhar com dispositivos de armazenamento secundário
de memória como no caso do disco magnético, é utilizada também em Banco de Dados. A
estrutura desta árvore não segue o da ABB, pois pode ter vários filhos,não limitando a
apenas dois (subárvore esquerda e subárvore direita). A descrição e as propriedades dessa
árvore são encontradas no site da (UNICAMP, b) diz o seguinte:
Elas visam otimizar as operações de entrada e saída nos dispositivos. O
tempo de acesso às informações em um disco é prejudicado principalmente
pelo tempo de posicionamento do braço de leitura. Uma vez que o braço
esteja posicionado no local correto, a leitura pode ser posicionado no
local correto, a leitura pode ser feita de forma bastante rápida. Desta
forma, devemos minimizar o número de acessos ao disco. Diferente das
árvores binárias, cada nó em um árvore B pode ter muitos filhos, isto é,
o grau de um nó pode ser muito grande.
Esta árvore facilita no que diz respeito ao tempo de acesso quando efetua um busca
em um disco magnético, sendo eficaz na busca. Como foi dito antes, segue as definições
encontradas no site da (UNICAMP, b).
Definição: Uma árvore B possui as seguintes propriedades: 1. Todo o nó X possui
os seguintes campos:
a. n, o número de chaves armazenadas em X;
b. as n chaves k1, k2...kn são armazenadas em ordem crescente;
c. folha, que indica se X é uma folha ou um nó interno.
2. Se X é um nó interno então ele possui n+1 ponteiros f1, f2...fn+1 para seus filhos
(podendo alguns serem nulos);
3. Se ki é alguma chave na sub-árvore apontada por fi, então
4. Todas as folhas da árvore estão na mesma altura (que é a altura da árvore).
5. Existe um número máximo e mínimo de filhos em um nó. Este número pode ser descrito
em termos de um inteiro fixo t maior ou igual a 2 chamado grau mínimo.
a. Todo o nó diferente da raiz deve possuir pelo menos t-1 chaves. Todo o nó interno
diferente da raiz deve possuir pelo menos t filhos. Se a árvore não é vazia, então a raiz
possui pelo menos uma chave.
b. Todo o nó pode conter no máximo 2t - 1 chaves. Logo um nó interno pode ter no
máximo 2t filhos. Dizemos que um nó é cheio se ele contém 2t - 1 chaves.
Este tipo de árvore permite manter mais de um nó em cada chave, que seria os k1,
Capítulo 4. Árvore B 24
k2, k3,...kn que aparece, um elemento é inserido é na folha, esta árvore garante que todos
os nós folhas estão no mesmo nível (altura), sua estrutura garante que a sequência de
entrada dos dados não é tão relevante, não esquecendo que ao inserir um elemento e ocorrer
um estouro o elemento mais do meio sobe da chave e o novo elemento entra, dividindo
desta forma a chave no nível folha. Este tipo de árvore cresce pouco para cima e muito
nas laterais, pois ao inserir vários elementos ocorre estouro, aumentando a quantidade de
elementos que ainda podem ser inseridos, crescendo mais nas laterais do que em altura.
Todo nó x tem um número de chaves armazenadas no nó x, o nó chave é chave1<=
a chave2<=...<=chave n[x], a folha é booleano indicando se o nó x é folha ou não. O nó
interno contém n[x]+1 ponteiros, os nós folhas não tem filhos.
As chaves chavei[x] separam os intervalos de chaves armazenada em cada subárvore.
Todas as folhas tem a mesma altura, o número de chaves é limitado, no mínimo m chaves
e no máximo 2m. (CORMEM, 2002) define a de maneira semelhante a árvore B:
As árvores B são semelhantes às árvores vermelho-preto, no fato de que
toda árvore B de n nós tem altura O(lg n), embora a altura de uma
árvore B possa ser consideravelmente menor que a altura de uma árvore
vermelho-preto, porque seu fator de ramificação pode ser muito maior.
Então, as árvores B também podem ser usadas para implementar muitas
operações sobre conjuntos dinâmicos no tempo O(lg n). As árvores B
generalizam árvores de pesquisa binária de maneira natural. ...se um nó
interno x são usadas como pontos de divisão que separam o intervalo de
chaves manipuladas por x em n[x]+1 filhos. As chaves no nó x são usadas
como pontos de divisão que separam o intervalo de chaves manipuladas
por x em n[x]+1 subintervalos, cada qual manipulado por um filho de
x. Quando procuramos por uma chave em uma árvore B, tomamos uma
decisão de (n[x=1]) modos, com base em comparações com as n[x] chaves
armazenadas no nó x. (2002, p.349).
A diferença de uma árvore B de uma vermelha-preto é a forma que elas são estru-
turada, onde uma vermelho-preto tem no máximo dois filhos, enquanto uma árvore B tem
no mínimo d e no máximo 2d filhos em cada chave. (BARANAUS, b) explica as definições
e propriedades que uma árvore B possui:
A ordem de uma árvore-B é dada pelo número máximo de descendentes
que uma página, ou nó, pode possuir. A definição apresentada vincula
a ordem de uma árvore-B ao número de descendentes de um nó (isto
é, de ponteiros). Deste modo, numa árvore-B de ordem m, o número
máximo de chaves em uma página é m-1. Para uma árvore-B de ordem
m: 1. cada página tem no máximo m descendentes e m-1 chaves. 2. cada
página, exceto a raiz e as folhas, tem um mínimo de round (m/2) filhos.
3. cada página, exceto a raiz, tem um mínimo de round (m/2) - 1 chaves.
4. todas as folhas aparecem num mesmo nível (o nível mais baixo). 5.
uma página que não é folha e possui k filhos, e contém k-1 chaves.
É uma árvore complexa, mas sua eficiencia supera as dificuldades, sendo preciso
seguir todas as propriedades como qualquer outra árvore, tendo especificações diferentes,
Capítulo 4. Árvore B 25
pois para acessar uma informação é preciso percorrer um caminho até encontrar a trilha e
chegar na chave acessando a informação.
4.1 Busca
A busca de uma árvore B é parecida com uma árvore binária, a diferença entre as
duas é que na ABB percorre no máximo dois caminhos, já a árvore B tem vários caminhos
a percorrer, a árvore é ordenada, por esse motivo as chaves já estão ordenadas. As chaves
estão armazenadas em uma memória secundária que são divididas em setores, cada nó
ocupa um setor no disco. Conforme figura 11.
Figura 11: Unidade de um disco típico
Para acessar a informação dentro de um disco rígido, posiciona o braço da cabeça de
leitura, ela pode ser movida de dentro pra fora, quando a cabeça do disco está posicionada
é chamada de trilha, tendo as cabeças de leitura alinhadas de forma vertical, acessando as
trilhas de forma eficiente. Abaixo é possível vermos a figura 12 como é uma árvore B e a
figura 13 é um pseudocódigo de uma busca em árvore B.
Figura 12: ÁrvoreB
A busca por uma chave dentro de um nó pode ser feita através de uma busca
binária, uma vez que as chaves ficam ordenadas dentro de cada nó, buscando primeiro
pelas páginas, verificando se é possível encontrar dentro da chave aquele elemento no
intervalo, e faz a varredura na árvore primeiro o elemento mais à esquerda do que pretende
buscar, até encontrar o elemento, se não encontrar passa para a segunda ramificação do
intervalo que busca, não encontrando retorna nulo e informa que o que está sendo buscado
não existe na árvore. Quando encontra retorna o elemento encontrado.
Capítulo 4. Árvore B 26
Figura 13: Pseudocódigo árvore B
4.2 Inserção
Primeiro busca o nó folha para saber em qual posição deve ser inserida a nova
chave, lembrando que mantem a ordem e não ultrapassa o limite de 2d, caso isso ocorra,
é preciso fazer a cisão da árvore para conseguir inserir o novo elemento na árvore, testa
primeiro se o tamanho é maior que 2d, se for, sobe o elemento mais ao meio do nó folha
que deu problema na árvore, coloca o auxiliar para segurar o elemento que ainda vai
ser inserido, dividindo aquele pedaço que deu problema, é como se fosse em uma árvore
binária, verifica se o elemento é menor que o elemento que ocorreu o estouro e insere todos
os elementos menores a esquerda e os maiores a direita tendo uma ligação pela ramificação,
sendo possível inserir o elemento que estava aguardando resolver o problema. Segundo
(BARANAUS, b), “cisão significa transferir a chave central para o pai e dividir o nó em dois”.
1 . Buscar n f o l h a em que deve s e r i n s e r i d a a nova chave .
2 . I n s e r i r a chave mantendo a o r d e n a o (sem se preocupar
em u l t r apa s s a r o l im i t e 2d) .
3 . Se ja t o t o t a l de chaves do n que s o f r e a i n s e r o
4 . Se t > 2d
5 . Efetuar C i s o
6 . Propagar t e s t e para o pai ( l i nha 3 em diante )
7 . S e n o
8 . Fim .
Ao inserir em árvore B é armazenado outras informações nas chaves, para determinar
o caminho que percorrerá, esse caminho é a referência da posição do registro associado
até a chave do arquivo, que é a informação que está sendo inserida, é como se fosse um
caminho que será percorrido. Quando a raiz da árvore está cheia, subdivide os nós da
chave, pega o elemento do meio e sobe, a chave do nó folha é dividido para receber na aba
do nó que subiu a nova chave e redistribui ligando o que é menor do lado esquerdo da nova
Capítulo 4. Árvore B 27
chave e do lado direito com o que é maior, abrindo mais possibilidades de inserir novos
elementos na árvore. Quando ocorre o estouro de elementos na chave é o procedimento
explicado acima, pode receber o nome de cisão ou promoção do nó tornando o nó chave
(folha) em nó chave (raiz). Sempre que ocorrer um estouro ocorrerá a cisão subindo um
grau a mais na árvore. Abaixo foi acrescentado alguns tipos de interações de árvores B,
sendo possível analisar observando a figura como um elemento é inserido em uma árvore
B.
Figura 14: Técnicas de Inserção
4.3 Remoção
A função remoção serve para remover algum elemento dentro da árvore B, pre-
cisando antes percorrer a árvore para buscar o nó chave que está solicitado a remoção.
É preciso seguir as propriedades da árvore ao eliminar uma chave (nó).Existem 2 casos
específicos quando vai remover um elemento em uma árvore.
1. O elemento é uma folha;
2. O elemento é um nó interno.
Caso 1. Elemento é uma folha:
Capítulo 4. Árvore B 28
• Quando o elemento a ser removido for uma folha precisa verificar se o número
de elemento mínimo da chave está sendo respeitada, como em uma árvore de ordem 2,
ela tem que ter no mínimo 1 elemento e no máximo 3. No caso de o elemento ser uma
folha e respeita essa condição, a chave é retirada e os registros internos da página são
reorganizados.
• O segundo tipo quando o elemento é uma folha, mas o número mínimo de chaves
é menor do que a quantidade mínima conforme a definição do tamanho da árvore. É preciso
redistribuir, procurando na página irmã ou no pai, pesquisando para ver se algum pode
“emprestar um elemento”, pegando emprestado quando o irmão ou o pai tiverem mais que
a quantidade mínima na chave, isso significa que o elemento a ser percorrido empresta o
maior elemento a esquerda ou o maior elemento a direita do que está pedindo emprestado,
subindo para o nó pai e o nó pai desce para que a propriedade seja cumprida, então pode
fazer a remoção do nó na chave. Pode ocorrer uma alteração na chave separadora no
sentido do pai descer e o nó que está sendo emprestado sobe, tornando-se o pai da chave.
• O terceiro tipo na folha é quando o irmão da esquerda, da direita e o nó pai
não tem como emprestar nenhum elemento, por não ter chaves suficientes para empresta,
neste caso é feita a concatenação, onde junta o conteúdo das duas páginas, página pai e a
página filho, tornando uma única página, sendo possível remover o elemento da chave. A
concatenação é a junção de duas páginas podendo ocorrer erros.
• O quarto caso é quando ocorre o underflow da página pai, pois ao concatenar
ocorre um erro por diminuir a altura da árvore.
Caso 2. Elemento é um nó interno • Quando o elemento a ser removido não
está na folha, troca-se a chave que pretende eliminar com a chave sucessora imediata que
pode ser o maior elemento da chave que tem ligação até chegar no nó folha subistituindo
os elementos (trocando de posição) até chegar no nó folha que trocará de lugar com o nó
que não era folha, tornando essa página folha, então será possível eliminar o elemento da
chave folha.
O site da Unicamp mostra um pseudo-código da remoção, sendo possível verificar
que primeiro é feita a busca na remoção, verificando em qual chave encontra-se o elemento,
faz comparação para saber se o nó é uma folha, se for testa se tem quantidade mínima
para remover sem sofre mudanças bruscas na árvore, se corresponder elimina da folha, se
não pede para o irmão próximo, enviando o irmão para a posição do pai e o pai desce
para tornar possível a remoção da chave. Se não for raiz faz a concatenação da chave e no
último caso, se não for compatível com nenhuma condição anterior faz a redistribuição que
é juntar duas chaves (pai e folha) para conseguir remover o elemento. É possível observar
isso no pseudo-código da UCDB, onde Pistori mostra, conforme os trechos abaixo:
Buscar chave r a ser removida. (Seja R o nó com a chave r) {
Se R é folha
Capítulo 4. Árvore B 29
Remova r de R
Senão
Troque r pelo sucessor. (Certamente está numa folha).
Seja r a nova chave e R o novo nó, aonde ocorrerá a remoção.
Remova r de R
Se ch(R) <= d ou R é Raiz (Quase OK)
Se R é Raiz e r era a última chave de R
Retirar Raiz.
Se Raiz não era folha
Filho da Raiz passa a ser a nova Raiz.
(Raiz só deve ter um filho, resultado de uma concatenação).
Fim.
Senao
Se R tem irmão adjacente S e ch(R)+ch(S) < 2d
Efetuar Concatenação
Propagar teste para o pai
Senão
Efetuar Redistribuição
Fim.
}
A concatenação é agrupar irmãos adjacente em um único nó, juntando a chave
do nó pai com a folha. A redistribuição é a concatenação do irmão adjacente seguida de
uma cisão. Por fim é importante visualiza as possíveis forma de remoção em uma árvore
através de visualização, como anexo.
Capítulo 4. Árvore B 30
Figura 15: Técnicas de remoção
31
5 Conclusão
Árvores balanceadas são eficientes no sentido de busca, garantindo que será possível
percorrer a árvore em um menor tempo quando comparado a uma ABB, é possível verificar
que em algum momento é utilizado propriedades da árvore ABB em alguma funcionalidade
das árvores.
Conclui-se então que cada tipo de árvore tem sua eficiência desenvolvida para um problema,
como no caso da árvore B que é uma árvore eficiente quando utilizada em Banco de Dados
e em disco magnético, enquanto as outras acabam perdendo a eficiência, uma árvore AVL
proporciona uma busca eficiente, pois garante que a árvore estará no máximo um nó
desbalanceado ou da subárvore esquerda em relação a subárvore direita. A rubro-negra é
eficiente também na busca, principalmente quando se fala em geometria computacional,
sendo que elas se completam em algum ponto, desde a árvore binária de busca quanto
as outras árvores que são balanceadas ou consideradas balanceadas, mantendo sempre as
suas particularidades.
32
Referências
BAILEIRO, R. Estrutura de dados. [S.l.]: Seses, 2015. v. 1a edição. Citado na página 6.
BARANAUS, J. A. Arvores AVL. Disponível em: <http://www.Dcm.ffclrp.usp.br/
~augusto/teaching/aedi/AED-I-Arvores-AVL.pdf.> Citado na página 11.
BARANAUS, J. A. Arvores AVL. Citado 2 vezes nas páginas 24 e 26.
CORMEM, T. H. Algoritmos. Teoria e prática. [S.l.]: Elsevier, 2002. Tradução da segunda
edição. Citado 5 vezes nas páginas 17, 18, 19, 21 e 24.
EGYPTO, C. Estrutura de Dados. [S.l.]: CFETP, 2004. Citado 2 vezes nas páginas 10
e 12.
MACHADO, C. Árvores AVL. [S.l.]: UFRGS, 2008. Citado na página 16.
UNICAMP. Estrutura de Dados com Algoritmos e C. Disponível em: <http:
//www.ft.unicamp.br/liag/programacao/arvorebin.html>. Citado na página 7.
UNICAMP. Árvore B. Disponível em: <www.ft.unicamp.br/liag/siteEd/definicao/
arvore-b.php>. Citado 3 vezes nas páginas 7, 8 e 23.
	Folha de rosto
	Resumo
	Lista de ilustrações
	Sumário
	Introdução
	Árvore
	Árvore Binária
	Árvore AVL
	Inserção
	Remoção
	Árvore Rubro-Negra
	Rotações
	Inserção
	Remoção
	Árvore B
	Busca
	Inserção
	Remoção
	Conclusão
	Referências