Árvore Binária

Árvore Binária

---

• Uma estrutura não linear
• Não é possível definir o início, saber onde um elemento vai ser colocado
• Se eu quiser fazer uma inserção numa posição específica...não existe posição
• Nas estruturas lineares, é necessário conhecer as características de cada tipo de estrutura, porque cada uma delas vão ter características que vão nortear o nosso desenvolvimento

Representações de Árvores

---

                                                                                  árvore não-binária     

• círculos representam os nós da árvore
• são ligados conforme são armazenados
• também trabalha-se com encadeamento de objetos
• existe a ideia de nó principal
• para acessar essa estrutura é necessário pelo menos ter uma referência ao meu nó principal
• nó principal é a raiz
• grau é o número de subárvores 
• quantidade de apontamentos do nó
• nó grau 0 é folha
• nível é a quantidade de linhas que ligam determinado elemento a raiz
• altura é o maior nível, a partir do nó principal
• floresta é um conjunto de árvores

Diagrama de inclusão

• A ligado a B e C
• B tem subárvore D
• C tem as subárvores E, F e G
• E contém H e I

Representação Hierárquica

Diagrama de Barras

Parênteses Aninhadas

---

Tipos de Árvore

O tipo de árvore, é a lógica por trás, de como ela vai ser preenchida, percorrida, mantida e por trás da remoção de um elemento e consulta.

Árvore Binária, Ávore B, Árvore B+, Árvore R, Árvore Rubro Negra... 

Para Estrutura de Dados, focaremos no tipo de árvore mais simples, mas já conseguimos perceber todas as van

gens, o potencial de se trabalhar com ela.

Não é o tipo mais popular, contudo, é capaz de tratar facilmente as situações que realmente justificam trabalhar com estruturas não-lineares. Nesta disciplina iremos trabalhar com a Árvore Binária.

Árvore Binária

Para uma árvore ser binária, quer dizer que obrigatoriamente, só poderei ter nós de grau zero, um ou dois.

A questão da simetria, entre as árvores binárias. Mesmo lidando com árvores, cujo valor é exatamente igual, mas elas não são iguais. Porque o fato do nó estar a esquerda ou a direita faz diferença. 

"Obrigatoriamente terei de exercitar a forma de desenhar árvores." - cobra em prova

Como vai ficar a estrutura da árvore binária, a partir de um conjunto de inserção

/*--- pouco utilizado ↓ ---*/

Árvore extritamente binária. cada nó possui exatamente 0 ou 2 nós

Árvore binária completa. se tiver um nó com a subárvore vazia, ele se encontrará num dos 2 últimos níveis.

Árvore binária cheia. sempre que o nó apresentar uma de suas subárvores vazias, ele se encontrará no último nível da árvore.

/*--- pouco utilizado ↑ ---*/

Armazenamento na Árvore Binária

Para inserir, regras são necessárias:

• o primeiro elemento é a raiz

• o menor valor é colocado a esquerda e o maior a direita

• quando é repetido, geralmente fica a esquerda, contudo, utilizamos árvores para garantir valores não repetidos

• melhor tempo de busca

    • quanto mais embaralhado, maior será o                        desempenho de busca quando comparado com           estruturas lineares

• quanto menor a altura da árvore, mais otimizada ela é, porque a altura da árvore é o número máximo de iterações para encontrar um elemento

    • o balanceamento deixa a árvore com a altura menor

• sempre gasta tempo menor ou igual ao de estruturas lineares na busca de elementos

• quanto mais ao meio estiver a raiz, mais distribuída estará a árvore binária, logo mais otimizada ela estará.

Como veio minimamente ordenada de maneira decrescente, acabou gerando uma lista.

12 é menor que 30 e 20, e é maior que 10. Logo vai a direita de 10.

2 é menor que 30, 20, 10 e 7. Logo fica a esquerda de 7.

31 é maior que 30, vai a direita do mesmo.

30 é um valor repetido e vai agir de acordo com o que estiver predefinido.Seja não inserir e dar um feedback, inserir a esquerda ou a direita.

37 é maior que 30 e 31, fica a direita de 31.

23 é menor que 30 e maior que 20. Fica a direita de 20.

 

40 é maior que 30, 31 e 37. Fica a direita de 37

Assim sendo, a árvore fica desta forma representada:

Representação Hierárquica

Mais um exemplo:

Formas de Navegar 

• Pré-ordem 

    1.ver (V) 

    2.esq (E)

    3.dir (D)

começa pela raiz

r: 30, 15, 12, 11, 7

esq de 7 não tem nada, volta

dir de 7 não tem nada, volta

esq de 11 já tinha verificado

dir de 11 não tem nada, volta

esq de 12 já tinha verificado

dir de 12 não tem nada, volta

esq de 15 já tinha verificado

dir de 15 existe

verifica o 23

r: 30,15, 12, 11, 7, 23

esq de 23 existe

verifica o 18

r: 30, 15, 12, 11, 7, 23, 18

esq de 18 não tem nada, volta

dir de 18 não tem nada, volta

esq de 23 já tinha verificado

dir de 23 não tem nada, volta

esq de 15 já tinha verificado

dir de 15 já tinha verificado

esq de 30 já tinha verificado

dir de 30 existe

verifica 42

r: 30, 15, 12, 11, 7, 23, 18, 42

esq de 42 existe

verifica 37

r: 30, 15, 12, 11, 7, 23, 18, 42, 37

esq de 37 não tem nada, volta

dir de 37 existe

verifica 40

r: 30, 15, 12, 11, 7, 23, 18, 42, 37, 40

esq de 40 não tem nada, volta

dir de 40 não tem nada, volta

esq de 37 já tinha verificado

dir de 37 já tinha verificado

esq de 42 já tinha verificado

dir de 42 existe

verifica 43

r: 30, 15, 12, 11, 7, 23, 18, 42, 37, 40, 43

desempilha 43 e desempilha 42

• Central (ordenação de forma natural)

    1.esq (E)

    2.verifica o elemento (V)

    3.dir (D)

Começa pela raiz

esq de 30

esq de 15

esq de 12

esq de 11

esq de 7, não tem nada

mostra o 7

dir de 7, não tem nada 

desempilha

já fez esq de 11

mostra o 11

dir de 11, não tem nada 

desempilha

já fez esq de 12

mostra o 12

dir de 12, não tem nada 

desempilha

já fez esq de 15

mostra o 15

dir de 15

esq de 23

esq de 18, não tem nada

mostra o 18

dir de 18, não tem nada

desempilha

já fez esq de 23

mostra o 23 

dir de 23, não tem nada

desempilha 

desempilha 

já fez esq de 30

mostra o 30

dir de 30

esq de 42

esq de 37, não tem nada

mostra o 37

dir de 37

esq de 40, não tem nada

mostra o 40

desempilha

desempilha

mostra o 42

dir de 42

esq de 43, não tem nada

mostra o 43

dir de 43, não tem nada

desempilha

desempilha

r: 7, 11, 12, 15, 18, 23, 30, 37, 40, 42, 43

•Pós-ordem

    1.esq

    2.dir

    3.ver

Começa pela raiz

esq de 30

esq de 15

esq de 12

esq de 11

esq de 7

dir de 7, nada

mostra 7

desempilha

dir de 11, nada

mostra 11

desempilha

dir de 12, nada

mostra 12

desempilha

dir de 15

esq de 23

esq de 18, nada

dir de 18, nada

mostra 18

desempilha

dir de 23, nada

mostra 23

desempilha

já fez esq e dir de 15

mostra 15

desempilha

dir de 30

esq de 42

esq de 37, nada

dir de 37 

esq de 40, nada

dir de 40, nada

mostra 40

desempilha

já fez 37

mostra 37

desempilha

dir de 42

esq de 43, nada

dir de 43, nada

mostra 43

desempilha

desempilha

já fez 30

mostra 30

r: 7, 11, 12, 18, 23, 15, 40, 37, 43, 42, 30

• Pré-ordem

Sempre gera estrutura que permite replicar a mesma estrutura de árvore.

Se pegar os valores na ordem do resultado, vai gerar uma árvore exatamente igual

• Central

Utiliza para apresentar os valores de forma ordenada

Ordenação crescente, evd

Ordenação decrescente, dve

• Pós-ordem

Sempre parte do ponto mais a esquerda da folha, e navega debaixo esquerda direita

Para descobrir o resultado:

    -Simular um comportamento recursivo

        -verificar a raiz

        -navegar

Árvore binária, extremamente otimizada para localizar elementos e também traz a possibilidade de ordenação natural.

Se fosse aplicar em uma estrutura linear um Bubble Sort ou Insertion Sort, ou qualquer outro algorítmo de ordenação, terei o custo computacional de mover os elementos.