Skip to content

Árvores Binárias

Uma árvore é um conjunto de elementos interligados entre si de forma que um elemento é a raiz e os demais se dividem em \(n\geq0\), subconjuntos disjuntos chamados subárvores.

Os elementos da árvore são chamados de nós e as ligações entre eles são chamadas de arestas. O nó que não possui pai é dito nó raiz e os nós sem filhos são ditos folhas. O grau de um nó é a quantidade de subárvores que se originam dele.

Se uma árvore for tal que \(grau(n)\leq2\ \forall\ n\ \in\ Árvore\), então dizemos que ela é uma árvore binária.

Níveis são "gerações" de nós na árvore, e a altura de uma árvore é o seu maior nível. Em uma árvore binária, um nível \(k\) pode ter no máximo \(2^k\) nós. O crescimento dos nós, conforme aumentamos o nível, é exponencial.

O máximo de nós numa árvore de altura \(h\) é: \(2^0+2^1+...+2^h = 2^{k+1}-1\), pela soma dos termos da PG de razão 2.

Propriedades

Uma árvore de altura \(h\) tem no mínimo \(h\) e no máximo \(2^h-1\) nós.

Figura 1: Árvores de altura 3 com o mínimo e máximo de nós. Fonte: [1]

Se a árvore tem \(n\geq1\) nós, então a altura é no mínimo \(\lfloor log_2(n+1) \rfloor\), quando a árvore é completa, e no máximo \(n\), quando cada nó não-terminal tem apenas um filho.

Árvore Binária Completa

Uma árvore binária é dita completa se todos os níveis, exceto o último, estão cheios e os nós do último nível estão o mais à esquerda possível.

Uma árvore binária completa com n nós tem \(\left \lceil log(n+1) \right \rceil = O(log n)\) níveis.

Podemos representar árvores binárias utilizando vetores.

Igualdade

Duas árvores são iguais se possuírem os mesmos dados e mesma estrutura. Árvores com os mesmos dados, mas estruturas diferentes, são ditas isomorfas.

Implementação

A implementação pode ser feita por meio de listas encadeadas ou vetores, ambas implementações tem vantagens e desvantagens, o uso de listas encadeadas pode diminuir a performance durante a varredura da árvore, pois os nós não estão salvos em posições sequenciais da memória, em contrapartida a inserção em uma árvore na estrutura de vetor é mais trabalhosa e pode exigir redimensionamento.

Listas Encadeadas

Cada nó da lista encadeada (Figura 2) possui a estrutura apresentada no trecho de Código 2.

Figura 2: Implementação de árvore utilizando lista encadeada. Fonte: [1]

arvores.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
typedef struct No
{
    int dado;
    struct No *esq, *dir;
} No;
typedef No *p_no;
typedef No *p_fila;

p_no criar_arvore(int dado, p_no esq, p_no dir);

p_no procurar_no(p_no raiz, int valor);
int numero_nos(p_no raiz);
int altura(p_no raiz);

// Percursos
void pre_ordem(p_no raiz);
void pos_ordem(p_no raiz);
void in_ordem(p_no raiz);
void em_largura(p_no raiz);

Criar árvore

A criação da árvore será das folhas para a raiz, criando-se a árvore esquerda, árvore direita e a raiz delas. Nesse caso já sabemos todos os elementos da árvore.

criar_arvore.c
1
2
3
4
5
6
7
8
9
// Cria um nó na árvore, com dado e filhos esquerdo e direito.
p_no criar_arvore(int dado, p_no esq, p_no dir)
{
    p_no raiz = malloc(sizeof(p_no));
    raiz->dado = dado;
    raiz->esq = esq;
    raiz->dir = dir;
    return raiz;
}

Procurar Nó

procurar_no.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Escolhe um tipo de varredura e faz a busca.
// Em ordem: esquerda, raiz, direita
p_no procurar_no(p_no raiz, int valor)
{
    p_no esq;
    if (raiz == NULL || raiz->dado == valor)
        return raiz;
    esq = procurar_no(raiz->esq, valor);
    if (esq != NULL)
        return esq;
    return procurar_no(raiz->dir, valor);
}

Número de Nós

numero_nos.c
1
2
3
4
5
6
7
// Faz a contagem do número de nós dos filhos e acrescenta a raiz.
int numero_nos(p_no raiz)
{
    if (raiz == NULL)
        return 0;
    return numero_nos(raiz->esq) + numero_nos(raiz->dir) + 1;
}

Altura

altura.c
1
2
3
4
5
6
7
8
9
int altura(p_no raiz)
{
    int esq, dir;
    if (raiz == NULL)
        return 0;
    esq = altura(raiz->esq);
    dir = altura(raiz->dir);
    return 1 + (esq > dir ? esq : dir);
}

Vetores

A árvore é distribuída em um vetor de forma que dada uma raiz na posição i, seus filhos esquerdo e direito estão nas posições 2*i+1 e 2*i+2, respectivamente.

Observe que como uma árvore binária de com k níveis tem, no máximo 2^k nós, sabendo a altura da árvore é possível alocar o tamanho certo do vetor.

Figura 3: Exemplo de árvore (binária de busca). Fonte: [2]

A árvore da Figura 3 ocuparia o vetor v da maneira representada a seguir, onde -1 indica posições desocupadas do vetor.

// Posição:       0  1  2  3  4  5  6  7
            v = [ 6, 5, 7, 2, 5,-1, 8,-1]

As funções que calculam as posições dos pais e filhos podem ser definidas utilizando macros. O vetor pode ser encapsulado em uma struct contendo também o seu tamanho.

arvore.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#define item int

typedef struct
{
    item *content;
    int size;
} tree;

typedef tree *p_tree;

#define PAI(n) ((int)n / 2)
#define ESQ(n) (2 * n + 1)
#define DIR(n) (2 * n + 2)

void criar_arvore(p_tree tree, int height);
int inserir(p_tree tree, item value, int start);

A definição de item por macro permite a alteração do tipo em tempo de compilação, com a flag -D, utilizando o gcc. Esse tipo de implementação fornece maior versatilidade no código.

gcc -o  a.out -Ditem=float a.c

Criar árvore

criar.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void criar_arvore(p_tree tree, int height)
{
    int size = pow_2(height);
    tree->size = size;
    tree->content = malloc(size * sizeof(item));
    for (int i = 0; i < tree->size; i++)
    {
        tree->content[i] = -1;
    }
}

Inserir Nó (ABB¹)

inserir.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int inserir(p_tree tree, item value, int start)
{
    for (int i = start; i < tree->size; i++)
    {
        if (tree->content[i] == -1)
        {
            tree->content[i] = value;
            return i;
        }
        if (value < tree->content[i])
            return inserir(tree, value, ESQ(i));
        if (value > tree->content[i])
            return inserir(tree, value, DIR(i));
    }
    return -1;
}

¹Árvore Binária de Busca

Varredura

Árvores são estruturas de dados não lineares, pois há várias formas distintas de percorrer seus elementos. As três formas padrão são:

  • Em ordem (esquerda-raiz-direita)
  • Pré-ordem (raiz-esquerda-direita)
  • Pós-ordem (esquerda-direita-raiz)

Pós ordem

O algoritmo para a varredura pós ordem visita:

  1. A subárvore esquerda da raiz, em ordem e-d-r
  2. A subárvore direita da raiz, em ordem e-d-r
  3. A raiz

Figura 4: Ordem de visitação dos nós em pós-ordem. Fonte: [1]

posordem.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Pós ordem visita os nós na ordem: esquerda, direita, raiz.
void pos_ordem(p_no raiz)
{
    if (raiz != NULL)
    {
        pos_ordem(raiz->esq);
        pos_ordem(raiz->dir);
        printf("%d ", raiz->dado);
    }
}

Pré ordem

O algoritmo para a varredura pré ordem visita:

  1. A raiz
  2. A subárvore esquerda da raiz, em ordem r-e-d
  3. A subárvore direita da raiz, em ordem r-e-d

Figura 5: Ordem de visitação dos nós em pré-ordem. Fonte: [1]

preordem.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Pré ordem visita os nós na ordem: raiz, esquerda, direita.
void pre_ordem(p_no raiz)
{
    if (raiz != NULL)
    {
        printf("%d ", raiz->dado);
        pre_ordem(raiz->esq);
        pre_ordem(raiz->dir);
    }
}

Em ordem

O algoritmo para a varredura em ordem visita:

  1. A subárvore esquerda da raiz, em ordem e-r-d
  2. A raiz
  3. A subárvore direita da raiz, em ordem e-r-d

Figura 6: Ordem de visitação dos nós em ordem. Fonte: [1]

em_ordem.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Em ordem visita os nós na ordem: esquerda, raiz, direita.
void in_ordem(p_no raiz)
{
    if (raiz != NULL)
    {
        in_ordem(raiz->esq);
        printf("%d ", raiz->dado);
        in_ordem(raiz->dir);
    }
}

Em largura

O percurso em largura visita os nós por níveis, da esquerda para a direita.

Figura 7: Percurso em Largura. Fonte: [1]

em_largura.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// Em largura visita os nós, por nível, da esquerda pra direita.
void em_largura(p_no raiz)
{
    p_fila f;
    f = criar_fila();
    enfileirar(f, raiz);
    while (!fila_vazia(f))
    {
        raiz = desenfileirar(f);
        if (raiz != NULL)
        {
            enfileirar(f, raiz->esq);
            enfileirar(f, raiz->dir);
            printf("%d ", raiz->dado); /*visita raiz*/
        }
    }
    destruir_fila(f);
}

Referências

[1] Árvores Binárias - Notas de aula do professor Rafael C. S. Schouery, disponíveis no link.

[2] Introduction to Algorithms, 3rd edition.