Árvores são estruturas de dados não lineares e hierárquicas formadas por vértices e arestas.

Árvores são casos especiais de grafos cuja nomenclatura é importada da botânica.

As árvores são classificadas de acordo com o número de arestas que cada vértice pode ter e a forma como os vértices são ordenados.

A árvore mais simples é a árvore binária.

Vazia: são árvores sém vértices.

Root Tree: uma árvore que só tem a raiz.

Heap: os pais tem valores maiores que os valores dos filhos.

Binary Search Tree: assim como o heap as BTS têm regras especias de construção.

Existem três formas principais e não únicas, de se percorrer uma árvore.

In-order é a primeira delas, percorremos os vértices de forma recursiva da esquerda para direita e de baixo para cima, começando na raiz.

Visitaremos: $D, B, E, A, F, C, G$

Primeiro a raiz depois o vértice da esquerda, depois o vértice da direita.

Visitaremos: $A, B, D, E, C, F, G$

A raiz é visitada por último, então vemos esquerda, direita, raiz.

Visitaremos: $D, E, B, F, G, C, A$

Árvores binárias são árvores que cada vértice pode ter no máximo duas arestas.

Ou, usando a nomenclatura de árvores: cada pai pode ter apenas dois filhos.

Dizemos que a árvore binária é completa quanto todos os pais têm dois filhos.

Uma árvore binária é composta de um pai e dois filhos. E esta estrutura pode ser repetida recursivamente para cada filho. Assim, cada galho, será formado por no máximo duas folhas.

Usamos árvores como estrutura de dados entre outras coisas por que: $O(nlogn)$.

A altura é o número de vértices entre a raíz e a última folha.

Se a árvore é binária, dada uma altura $h$ teremos: $$n = 1 +2^1+2^2+2^3+...+2^h$$

Que pode ser reduzida a $$n = 2^{h=1}-1$$.

E podemos mostrar que $$h = floor(log_2 n)$$

A busca de um vértice específico irá tomar, no pior caso: $ceiling(log_2 n)$ Como isso também é verdade para a adição de um vértice temos: $O(log n)$.