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

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

• Internal node: Um node que possui pelo menos um child node

• 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:

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

Full, Complete & Perfect Binary Tree

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.

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.

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.

Ou seja, ela não possui diferenças grotescas na altura da árvore, ela está balanceada.

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.

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.

Pre-orderal Traversal

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

Post-order Traversal

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

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