Trabalho de Algoritmos e Estrutura de Dados Avançado

Prévia do material em texto

Trabalho de Pesquisa Individual – 1300 PTs 
 
Reginaldo Marques – 4º Período – Manhã 
 
Pesquisa sobre estrutura de dados Árvores; 
Binárias; 
AVL; 
Rubro-Negras; 
Árvores B. 
 
Primeiramente iremos falar de Árvores antes de abordarmos suas variações, para que 
possamos ter pleno entendimento do que será falado a respeito das árvores binárias, 
AVL, Rubro-Negras e árvores B. 
Árvore é uma das estruturas de dados não lineares mais importantes da programação, 
sendo ela um conjunto finito de um ou mais nós (ou vértices) tal que, existe um nó 
especial denominado Raiz, e outros nós que constituem um único conjunto ou são 
divididos em n ≥ 1, conjuntos disjuntos não vazios, subárvores. 
Vejamos um exemplo de árvore: 
 
 
 
 
 
 
 
 
 
Agora podemos entender melhor o que é uma árvore onde, os quadrados são os nós, e 
o quadrado 15 é o nó raiz. Abaixo do nó raiz (15) temos também as subárvores (8 e 23) 
e mais abaixo as folhas (2, 12, 20, 30). 
Nesse exemplo podemos observar que cada nó tem grau 2, porque a partir de cada nó 
saem 2 subárvores, exceto das folhas que tem grau 0. 
Lembrando que para identificarmos os níveis de uma árvore, basta observarmos da 
raiz até as folhas das árvores, onde o nó raiz (15) é o nível 0, as subárvores (8 e 23) o 
nível 1, e as folhas (2, 12, 20 e 30) são o nível 2. 
Profundidade: a profundidade de um nó é a distância percorrida da raiz a esse nó. 
Profundidade do 15: 0. 
Profundidade do 8: 1. 
15 
8 23 
2 12 30 20 
Profundidade do 12: 2. 
Descendentes: os nós abaixo de um determinado nó, são seus descendentes. 
Por exemplo: 
Descendentes do 8: 2, 12. 
Descendentes do 15: todos os demais nós. 
Altura(h): a altura de uma árvore é a altura da raiz, porém, a altura de um nó vai ser o 
maior caminho da distância dele até uma folha. 
 
Vejamos mais um exemplo: 
 
 h=2 
 
 h=1 ........................................................................................... nível 0 
 
 .................................................................................................................................. nível 1 
 h=0 
 ..................................................................................................................... nível2 
 
Agora para que nosso entendimento não se confunda temos que entender de fato o 
que foi dito à cima, que a altura de um nó vai ser o maior caminho da distância dele 
até uma folha. Vamos ver mais um exemplo: 
 
 
 h=3 
 
 h=2 ........................................................................................... nível 0 
 
 .................................................................................................................................. nível 1 
 h=1 h=0 
 ..................................................................................................................... nível2 
 
 .................................................................................................................................. nível 3 
 
Podemos perceber que a altura do nó 12 é 0, porém a altura do nó 2 é 1, sendo que o 
nó 2 está no mesmo nível que o nó 12, porém, a distância do nó 2 até o nó 4 é de 1. 
 
15 
8 23 
2 12 30 20 
15 
8 23 
2 12 30 20 
4 
 
Árvores Binárias 
 
O que é uma árvore binária? 
Uma Árvore Binária é uma árvore em que, abaixo de cada nó, existem no máximo duas 
subárvores. 
Vejamos um exemplo: 
 
 
 
 
 
 
 
 
 
 
 
Para que possamos representar uma árvore binária computacionalmente precisamos 
unir nós. Como assim unir nós? 
Iremos precisar de 2 ponteiros para fazer isso, um ponteiro para a subárvore da 
esquerda e outro para a subárvore da direita, além de um campo para a chave de 
dados. Ou seja: 
 
 
 
 
 
A Chave é onde será guardada a informação que a árvore irá guardar, os 2 
ponteiros são os null (null porque ainda não tem nada), que serão os ponteiros 
utilizados para a subárvore dá direito e a subárvore à direita. 
 
Vejamos um exemplo em C: 
 
#include<stdio.h> 
#include<stdlib.h> 
8 23 
2 12 30 20 
15 
Chave 
null null 
#define true 1 
#define false 0 
typedef int boo1; 
typedef int TIPOCHAVE; 
typedef struct aux { 
TIPOCHAVE chave; 
/* Aqui será onde os dados serão armazenados */ 
struct aux *esq, *dir; 
struct aux *esq, *dir; 
} NO; 
typedef NO* PONT; 
 
Árvore Binária de Busca 
Mas o que define uma Árvore Binária de Pesquisa?? 
Uma Árvore Binária de Busca (ABB), é uma árvore onde os nós com registros 
menores estão nas subárvores esquerdas, e os nós com registros de chaves maiores 
nas subárvores direitas. As cores foram usadas apenas para que a visualização fosse 
melhor para entendermos de fato o que foi dito à cima. 
 
 
 
 
 
 
 
 
 
 
 
Árvores AVL 
O que é uma Árvore AVL? 
É uma árvore binária de busca balanceada. Uma árvore balanceada é uma 
árvore que minimiza o número de comparações feitas no pior caso para uma busca 
com chaves de probabilidades de ocorrências idênticas. Uma Árvore AVL verifica a 
altura das subárvores da esquerda e da direita garantindo que essa diferença não seja 
maior que ±1. 
 
8 23 
2 12 30 20 
15 
O nome dessa diferença é fator de balanceamento. 
fb= hesq – hdir 
Mas como assim uma Árvore Balanceada? O que é uma? 
É uma árvore que mantém automaticamente sua altura mesmo depois de 
sucessivas inserções e exclusões. 
Percebemos então que, toda árvore AVL é balanceada. 
 
Exemplo de uma árvore AVL: 
 
 
 
 
 2 
 
 1 1 
 
 0 0 
 
 
 
Uma coisa que não falamos é que a altura da uma árvore vazia é -1. 
 
 
 
 2 
 
 1 1 
 
 0 0 0 -1 
 
 
Note que onde está o -1, se encontra a árvore vazia. Porém, essa continua 
sendo uma árvore AVL e continua balanceada. 
 
 
8 23 
12 
15 
 
2 
 
8 23 
12 
15 
 
2 
 
23 
 
 
 3 
 
 1 2 
 
 0 0 1 -1 
 
 
 0 
 
 
 
Essa árvore à cima está desbalanceada e por isso ela não é uma AVL. 
 
 
Árvores Rubro-Negras 
O que é uma Árvore Rubro-Negra? 
É uma árvore balanceada de busca binária com atributo COR (vermelho ou 
preto), seu nome é devido a coloração dos seus nós, a coloração é utilizada para fazer 
o balanceamento da árvore. Todo nó da árvore é vermelho ou preto, sendo que a raiz 
é sempre preta. Todo nó filho ou folha são pretos e para cada nó todo caminho dele 
até seus nós folhas descendentes contém o mesmo número de nós pretos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
8 23 
12 
15 
 
2 
 
23 
18 
 
 
Árvore B 
 
A árvore B é muito parecida com a árvore Binária que já vimos no início desse trabalho. 
Mas a grande diferença entre as duas é que enquanto a Binária tem apenas 2 filhos 
por nó, a árvore B pode ter n filhos por nó. Porém, cada nó pai tem mais de uma 
chave. Vamos ver um exemplo de árvore B para que possamos entender melhor o que 
está sendo dito: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Podemos perceber que todas as folhas estão exatamente no mesmo nível (a imagem 
montada não deixa isso tão claro, mas essa é uma das principais caraterísticas das 
árvores B). A raiz é uma folha ou tem no mínimo 2 filhos, cada nó diferente da raiz e 
das folhas possui no mínimo d + 1 filhos. Outra coisa importante a ser falada é que em 
cada nó tem um número mínimo de chaves, sendo o número de chaves chamado de 
Ordem da Árvore (Cormen, 2001; Bayer e MacCreight, 1997), onde 50% do que cabe 
em um nó será a Ordem da Árvore, ou seja, se cabem 4 chaves dentro de um nó, esse 
nó é de orem 2. Sendo assim essa árvore à cima é uma árvore de Ordem 2. 
· 29 · · · · 
· 8 · 15 · · · 
· 1 · 3 · 4 · 7 · · 10 · 12 · 13 · 14 
· 
· 18 · 20 · 25 · · · 30 · 35 · · · 
· 40 · 41 · 42 · 43 
· 
· 70 · 77 · 83 · · 
· 37 · 45 · 70 · · 
· 51 · 52 · · ·