Árvores Binárias

Árvores e Árvores
Binárias

Roteiro
Contextualização
Árvores
Árvores Binárias

Roteiro
Contextualização
Árvores
Árvores Binárias

Contextualização
Importância de estruturas unidimensionais ou lineares
(vetores e listas) é inegável.
Contudo, elas não são adequadas para representar dados que devem ser dispostos de maneira hierárquica. Por exemplo, diretórios criados em um computador.

Exemplo de estrutura hierárquica

Um exemplo de estrutura de diretório no Windows 2000

Roteiro
Contextualização
Árvores
Árvores Binárias

Árvores
Árvore é uma estrutura de dado adequada para representar hierarquias.
Forma mais natural de definirmos uma estrutura de árvore é usando recursividade.

Definições
Uma árvore é composta de um conjunto finito de nós.
Desse conjunto, há um nó r denominado de raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r.
Esses nós raízes das sub-árvores são ditos filhos do nó pai, r.
Nós com filhos são comumente chamados de nós internos. Nós que não têm filhos são chamados de nós externos (folhas).

Estrutura de árvores

Exemplos de árvores (1/2) raiz da árvore

Quantas sub-árvores existem na árvore acima?
Quais são as sub-árvores?
Quais nós são as raízes das sub-árvores da árvore acima?
Quais nós são considerados nós internos?
Quais nós são considerados nós externos (folhas)?

Exemplos de Árvores (2/2)

Propriedade Fundamental de Árvores
Existe um único caminho da raiz para qualquer nó da árvore.
Portanto, podemos definir a altura de todas as árvores como sendo o comprimento do caminho mais longo da raiz até uma das folhas. Por definição, a altura de uma árvore que possui somente um elemento é zero.

Exemplo de altura em árvores

árvore A1 árvore A2
Qual a altura da árvore A1?

Qual a altura da árvore A2?

Roteiro
Contextualização
Árvores
Árvores Binárias

Árvores Binárias (AB)
Uma árvore binária é constituída de um conjunto