Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores binárias - Coggle Diagram
Árvores binárias
'Binary Search Tree'/BST
Uma árvore binária ordenada. Na figura acima, por exemplo: Os filhos à esquerda do pai são sempre menores que ele e os da direita, sempre maiores.
Inserção(utilizando a ordem utilizada no exemplo): É basicamente o mesmo processo de busca, com a adição de que o processo de busca pela posição do novo valor, um objeto nulo é encontrado, ao invés de um filho, essa é posição que o novo valor "habitará".
Busca de um valor 'v' (utilizando a ordem utilizada no exemplo):
- Se a árvore está vazia, a busca falhou.
- Comparamos o valor de 'v' com o valor da raiz. Se eles são iguais, a busca acabou e obteve êxito.
3.Se não são iguais, e 'v' é menor que a raiz, Busca recursiva de 'v' na subÁrvore da esquerda.
4.Se não são iguais, e 'v' é maior que a raiz, Busca recursiva de 'v' na subÁrvore da direita.
Caso a árvore "penda" muito para apenas um lado, por exemplo após uma sequência de inserções de valores em ordem crescente ou decrescente, ela acaba ficando estruturalmente semelhante à uma lista ligada, logo a eficácia da busca no pior caso cai em Θ(n). A eficiência média é Θ(log n).
Métodos
Height(T):
Se T == vazio, retorne -1.
Senão, retorne MAX(Height(Tesquerda), (Tdireita)).
Navegar pela BST
pre-ordem: O nó é visitado antes dos filhos.
em-ordem: O nó é visitado depois do filho esquerdo e antes do direito.
pos-ordem: O nó é visitado depois dos filhos.
Árvores
-
-
'Rooted trees'
-
Quando um nó é arbitrariamente selecionado para ser a raiz e a árvore "livre" vira uma árvore com raiz.
-
-
raiz: O nó selecionado para ser a raiz da ávore.
Folhas: nós sem filhos.
Filhos: Ex.: na imagem, 'h' é filho de 'c'.
Altura: Distância mais longa entre a raiz e uma folha(caminho direto/simples).
Profundidade: Distância de um nó 'v' para a raiz.
Árvores Binárias
Uma 'ordered tree' onde cada nó tem no máximo 2 filhos (designados filhos esquerdo e direito, respectivamente).
Como cada nó também é uma subárvore binária, é possível resolver vários problemas que as envolvem com recursão.
-
A eficiência de muitos dos algoritmos envolvendo árvores binárias depende da altura 'h' de uma árvore de 'n' nós, de acordo com a inequidade:
|log2 n| ≤ h ≤ n − 1.
