Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores - Coggle Diagram

- - - - Ou seja, o número de arestas (edge) é igual ao números de vértices menos 1
      - Essa formula não prova que um grafo é uma árvore, porém se for um grafo conexo então é possível saber através dessa equação se o mesmo é uma arvore ou não, ou seja, se um grafo é conexo e essa formula é válida para ele, então ele não contem ciclos
- - - - Para qualquer vértice v em uma árvore T, todos os vértices no caminho entre a raiz e v são ancestrais de v, o v é ancestral dele mesmo ( o conjunto dos ancestrais de um vértice, desconsiderando ele mesmo, é chamado de ancestrais próprios)
        
        O último ancestral de v (u) é chamado de pai de v, e v é filho de u
        
        Vértices que tem o mesmo pai são chamados de irmãos
        
        Se um vértice não é pai de ninguém, então ele é chamado de folha
        
        Sendo w um vértice qualquer, se v for ancestral de w, então w é descendente de v
        
        O conjunto de descendentes próprios de v é o conjunto dos descendentes de v sem o v
        
        Todos o descendentes de v com todos as arestas que os conectam, formam a sub-árvore de T que tem v como raiz
        
        A profundidade do vértice v é o tamanho do caminho simples entre a raiz e x
        
        Tamanho é calculado pelo número de arestas
        
        A altura de uma árvore é o tamanho do maior caminho simples que vai da raiz até uma folha
  - - - São árvores ordenadas em que cada vértice não pode ter mais de 2 filhos, e cada filho é designado como o filho esquerdo ou filho direito de seu pai
        
        Um pai é sempre maior do que seu filho esquerdo (e seu descendentes, ou seja, a sub-árvore esquerda) e menor que seu filho direito ( e seus descendentes, ou seja, a sub-árvore direita)
        
        Isso são árvores de busca binária
        
        Para fazer uma busca por um elemento v numa arvore binária verificamos se o valor da raiz é igual a v, se for, então o elemento foi encontrado e a busca pode parar, caso não for verificamos se v é maior ou menor que o valor da raiz, se for menor então esse processo vai acontecer de novo com a sub-árvore da esquerda, se for maior então o processo vai acontecer na sub-árvore da direita
        
        Esse processo acontece recursivamente até a sub-árvore se esvaziar (por não achar ou por realmente ser uma árvore vazia)
        
        Isso é um exemplo de diminuir para conquistar, pois o problema está sempre diminuindo pela metade
        
        Um método para saber a altura de uma árvore é:
        
        A altura de uma árvore é igual a maior altura entre a sua árvore direita e sua árvore esquerda mais 1 (por causa da raiz), dessa forma definimos o método recursivamente (como condição de parada podemos usar a folha que possui null como filho, neste caso a altura seria 1)
        
        Dividir para conquistar
        
        1 more item...
        
        Para facilitar na visualização ( e na implementação), podemos considerar o fim da árvore como um nó extra chamado de externo, que é um nó vazio