# Trees

### Definição

Uma árvore (tree) é um tipo de estrutura de grafo (graph) composta por nós e arestas, tendo as seguintes propriedades:

* É acíclica
* Existe um caminho da raiz (root) para qualquer nó (node)
* Possui N - 1 arestas, onde N é o número de nós na árvore
* Cada node possui um parent node, exceto o root node&#x20;

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FeFQXAY7HlhRM7lfNrgfN%2Ftree_intro_examples.001.png?alt=media&#x26;token=1c307c8f-f885-4d77-9458-d4009a4ce4cd" alt=""><figcaption></figcaption></figure>

### Conceitos básicos

É importante se familiarizar com alguns conceitos:

* **Nodes**: Abstrações de objetos (aka os círculos)
* **Edge**: Relações entre nodes (aka as linhas)
* **Root**: O primeiro parent node&#x20;
* **Internal** **node**: Um node que possui pelo menos um child node&#x20;
* **Leaf** **node**: Um node que não possui nenhum child node
* **Ancestor**: Nodes que estão no caminho da root até o node atual
* **Descendent**: Nodes que são alcançados a partir do node atual quando descendo a árvore
* **Level**: O número de ancestors de um node até a root
* **Height**: O número de edges de um node até o caminho mais longo para um leaf node
* **Depth**: O número de edges da root para um node

### Binary Tree

Uma árvore n-ária (n-ary tree) é uma árvore em que cada nó tem no máximo n filhos, uma árvore binária é uma árvore n-ária onde n = 2, de modo que cada nó possua 0 a 2 filhos. Vejamos uma implementação de uma binary tree em Python:

```python
class Node:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
```



### Full, Complete & Perfect Binary Tree

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2F9eMbywmRCGglftus6Hyn%2Fspecial-trees.001.png?alt=media&#x26;token=6b63e12d-d2bd-454c-8554-63ea60adde1a" alt=""><figcaption></figcaption></figure>

Full: Cada node tem 0 ou 2 filhos

Complete: Todos os levels estão completos, exceto possivelmente o último, e todos os nodes no último level ficam o mais à esquerda possível.

Perfect: Cada internal node tem exatamente 2 filhos, e todos os leaf nodes estão no mesmo level. \


Uma _perfect binary tree_ possui 3 propriedades interessantes:

1. A quantidade de nodes é sempre 2^n - 1, onde n é maior level da árvore.&#x20;
2. A quantidade de internal nodes é igual à quantidade de leaf nodes - 1.
3. O número total de nodes é igual a 2 \* quantidade de leaf nodes - 1.



### Binary Search Tree

Uma _binary search tree (BST)_ é um tipo especial de árvore binária em que cada node segue uma propriedade de ordenação: todos os descendentes da esquerda < node < todos os descendentes da direita.&#x20;

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FclEwYIKHebGnxndi3lHn%2Fbst-21.png?alt=media&#x26;token=9d7939cf-43b3-4b4a-bf53-d98aa72c099e" alt=""><figcaption></figcaption></figure>

### Balanced Binary Tree

Cada node em uma _balanced binary tree_ segue uma regra de que a diferença da altura da subtree da esquerda e da direita do node atual não é maior que 1.&#x20;

Ou seja, ela não possui diferenças grotescas na altura da árvore, ela está _balanceada_.&#x20;

Searching, insertion & deletion em uma _balanced binary tree_ tem uma time complexity de O (log N), ao invés de O (N) em uma _unbalanced binary tree_, justamente por causa desse balanceamento.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FdClzoFtzSilYGyCLlmcj%2Ftree_intro.004.png?alt=media&#x26;token=56c8a738-42ae-4c3c-a449-7c94e7d28ed4" alt=""><figcaption></figcaption></figure>



### Tree Traversal

Tree Traversal são formas de você acessar cada node de uma árvore, diferente de estruturas de dados lineares, como arrays, linked lists, stacks, queues, árvores podem ser acessadas de diferentes maneiras.

#### In-order Traversal

Visita os nodes da esquerda primeiro, e então o node atual, e então finalmente os nodes da direita.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FteWXSbXLEDG10Wp5LDtY%2Finorder_traversal.gif?alt=media&#x26;token=b96d3026-b826-4281-a85e-8cdf9b470f87" alt=""><figcaption></figcaption></figure>

#### Pre-orderal Traversal

Visita o node atual primeiro, e então os nodes da esquerda, e, finalmente, os nodes da direita.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2Fz2BnmbiszwScfH3UXGzk%2Fpreorder_traversal.gif?alt=media&#x26;token=2e7eb505-ca1d-421d-9e52-5e70b88fbc24" alt=""><figcaption></figcaption></figure>

#### Post-order Traversal

Visita os nodes da esquerda primeiro, e então os nodes da direita, e, por fim, o node atual.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FGeJH1MjlpBXH87s9D9oX%2Fpostorder_traversal.gif?alt=media&#x26;token=f90e66ed-7120-4da1-8b06-ca998706de4e" alt=""><figcaption></figcaption></figure>



fonte: "Everything About Trees", AlgoMonster.

keywords: tree, node, edge, root, internal node, leaf node, ancestor, descendent, level, depth, height, full binary tree, complete binary tree, perfect binary tree, binary search tree, balanced binary tree, unbalanced binary tree, tree traversal, in-order traversal, pre-order traversal, post-order traversal
