Arvores

Sejam bem-vindos a mais uma aula do curso Estruturas de Dados Essenciais. Hoje vamos falar sobre árvores.

Árvores são estruturas de dados que representam uma hierarquia de elementos. Cada elemento é um nó que contém um valor e uma referência para outros nós. A referência para outros nós é chamada de filho. O nó que contém a referência para outro nó é chamado de pai.

Aqui está um exemplo de uma árvore com três elementos:

  1
 / \
2   3

Tipos de Árvores

Existem vários tipos de árvores. As mais comuns são:

Árvore Binária: Cada nó contém no máximo dois filhos.
Árvore Binária de Busca: Árvore binária onde o valor do filho da esquerda é menor que o valor do pai e o valor do filho da direita é maior que o valor do pai.

Conceitos

Raiz: O nó no topo da árvore.
Folha: O nó no final da árvore.
Nó Interno: O nó que não é folha.
Altura: O comprimento do caminho mais longo da raiz até uma folha.
Profundidade: O comprimento do caminho da raiz até um nó.
Nível: A profundidade de um nó mais um.
Grau: O número de filhos de um nó.
Grau de uma Árvore: O grau do nó com o maior grau.
Árvore Binária Cheia: Árvore binária onde todos os nós têm grau 0 ou 2.
Árvore Binária Completa: Árvore binária onde todos os níveis estão completos, exceto possivelmente o último, que está preenchido da esquerda para a direita.

ADT Árvore Binária

build(X): Cria uma nova árvore binária.
insert(value): Insere um novo valor na árvvore binária.
delete(value): Remove um valor da árvore binária.
search(value): Busca um valor na árvore binária.
size(): Retorna o número de elementos na árvore binária.
height(): Retorna a altura da árvore binária.

Implementação

Vamos implementar uma árvore binária simples em Ruby.