Árvore binária

Prévia do material em texto

Árvore binária:
Em ciência da computação, 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.
Termos de árvore
Nó: são todos os itens guardados na árvore. 
Raiz: é o item do topo da árvore (neste caso o número 50). 
Filho: são os itens logo abaixo da raiz, 30 e 90 e assim sequencialmente, por exemplo, o 20 é filho do 30. 
Parente: são os nós do mesmo nível, por exemplo, o 90 é parente do 100. 
Folha: é um nó que não tem filho, é o último item da árvore, por exemplo, 20, 40 e 100
Percorrendo uma árvore binária
Para a busca em uma árvore binária por um valor específico começamos examinando a raiz. Se o valor for igual a raiz, o valor existe na árvore. Se o valor for menor do que a raiz, então deve buscar na sub-árvore da esquerda, e assim recursivamente em todos os nós da sub-árvore. Similarmente, se o valor for maior do que a raiz, então deve buscar na sub-árvore da direita. Até alcançar o nó folha da árvore, encontrando ou não o valor requerido.
Percurso em árvore
Em uma árvore binária de busca pode-se fazer os três percursos que faz para uma árvore binária qualquer (percursos em inordem, preordem e posordem). Uma característica interessante é quando se faz um percurso em ordem em uma árvore binária de busca. Ao efetuar esse percurso, os valores 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".
Inserção
A inserção começa com uma busca procurando pelo valor, mas se não for encontrado, procuraremos as sub-árvores da esquerda ou direita como na busca. Eventualmente, alcançaremos a folha, e então inserimos o valor nesta posição. Ou seja nós examinamos a raiz e introduzimos um nó novo na sub-árvore da esquerda se o valor novo é menor do que a raiz, ou na sub-árvore da direita se o valor novo for maior do que a raiz. Uma outra maneira de explicar a inserção é que a fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menos do que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor.
Remoção
Remoção da folha
Remoção de um nó com um filho. O filho do nó removido passa a ocupar a posição do pai.
Exclusão de um nó com dois filhos. Neste caso pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais à esquerda da sub-árvore direita) ou pelo valor antecessor (o nó mais à direita da sub-árvore esquerda), e aí remove-se o nó sucessor (ou antecessor).
No exemplo acima, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 40 e como antecessor imediato do 40 o valor 35. Assim sendo, na exclusão, o filho do 40 será promovido no lugar o nó a ser excluído, o 40 continuará no mesmo lugar, como pode ser visto na figura.
Ao remover um nó, ou mesmo ao incluir um nó, pode haver o desbalanceamento da árvore, sendo corrigido, por exemplo, com o balanceamento AVL.
Balanceando uma árvore
Uma árvore binária de busca não garante acesso em tempo logarítmico. Inserções ou eliminações podem desbalancear. No pior caso a árvore degenera em lista ligada, onde a busca passa a gastar tempo linear. Balanceamento das árvores binárias de busca evitam esses casos degenerados, garantem tempo logarítmico para todas as operações, requerem algoritmos mais elaborados para inserção e eliminação. 
De modo geral, os nós das árvores balanceadas armazenam mais informações. Dois conhecidos modelos: árvores DSW e AVL.
Algoritmo DSW (Árvore Rubro-negra)
Uma árvore rubro-negra é uma árvore binária de busca em que cada nó é constituído dos seguintes campos: 
cor (1 bit): pode ser vermelho ou preto. 
key (e.g. inteiro): indica o valor de uma chave. 
left, right: ponteiros que apontam para a sub-árvore esquerda e direita, resp. 
pai: ponteiro que aponta para o nó pai. O campo pai do nó raiz aponta para nil. O ponteiro pai facilita a operação da árvore rubro-negra, conforme será visto a seguir. 
Arvore AVL
Uma árvore AVL é uma árvore binária de busca em cujos nós as alturas das sub-árvores diferem no máximo de uma unidade.
Após cada inserção ou eliminação, é necessário verificar o balanceamento de todos os nós da árvore
Grafos
Grafos são estruturas matemáticas usadas para representar ideias ou modelos, por intermédio de uma ilustração, gráfico ou esquema. Estritamente, em matemática, a teoria dos grafos é utilizada para representar o relacionamento entre dois ou mais conjuntos, grandezas ou valores. A representação de um mapa de rotas, redes e outros modelos semelhantes pode ser feita por meio do que se denomina grafos. 
Por exemplo, um mapa de rotas aéreas. 
Nota-se que existem várias rotas de um ponto a outro, por exemplo, de Florianópolis a Brasília existem as possibilidades via Curitiba, via São Paulo ou via Rio de Janeiro. Algumas rotas podem ter mais escalas, por exemplo, pode-se ir a Brasília por São Paulo, passando por Curitiba, Rio e Belo Horizonte. Neste exemplo, temos a linha que liga cada dois pontos. Note, entretanto, que existe uma rota de Florianópolis a Florianópolis que, digamos, pode representar um voo panorâmico pela ilha que decola e retorna ao mesmo ponto. O mapa de rotas contém pontos, que representam as cidades, e estão ligados por linhas, que representam as rotas aéreas. Cada um dos pontos de um grafo é denominado nó e cada uma das ligações são denominadas arcos. A representação de dados como estrutura de dados, pode ser aplicadas em: 
• Mapas de distâncias 
• Mapas Metabólicos 
• Diagramas e Fluxogramas
Redes de computadores 
•Redes Neurais
• Estruturas químicas
Representação de grafo
O conjunto de arcos de um grafo pode ser representado de várias maneiras: 
– Listas de Adjacência. – Matriz de Adjacência. – Matriz de Incidência.
Listas de adjacência
Matriz de Adjacência.
A matriz de adjacências de um grafo G = (V, A) contendo n vértices é uma matriz de nxn. A[i,j] é 1 se e somente se existe um arco do vértice i para o vértice j.
Algoritmos de busca
Um algoritmo de busca é um algoritmo que percorre um grafo andando pelos arcos de um vértice a outro.  Um algoritmo de busca examina sistematicamente os vértices e os arcos do grafo;  depois de examinar a ponta inicial de um arco, o algoritmo percorre o arco e examina sua ponta final.  Cada arco é examinado no máximo uma vez.
Algoritmo do caminho mínimo
https://brainstormdeti.wordpress.com/2010/08/10/grafos-algoritmo-do-caminho-minimo/
Referências:
http://www.comp.ita.br/~pauloac/ces11/ces11_arvoresbinarias2.pdf
https://pt.slideshare.net/renatopaschoal/rvores-binrias-balanceadas
http://www.ft.unicamp.br/liag/siteEd/definicao/arvore-binaria.php
http://www.inf.ufsc.br/~joao.dovicchi/pos-ed/ebook/e-book_estrut_dados_dovicchi.pdf
>>> http://www.dainf.ct.utfpr.edu.br/~kaestner/MatematicaDiscreta/Conteudo/Algoritmos/l13-graph-search.pdf
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/bfs.html
<<<