Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária de busca (BST)

Passo 1

O enunciado pede para definirmos o que é uma árvore binária de busca, conhecida como BST (Binary Search Tree). O conteúdo está em estruturas de dados (árvores), e vamos precisar lembrar o que é uma árvore binária e como se impõe a propriedade de ordenação nos nós.

Passo 2

Uma árvore binária é um conjunto de nós em que cada nó possui no máximo dois filhos, chamados de subárvore esquerda e subárvore direita. Cada nó armazena uma chave (ou valor) k e ponteiros (referências) para as suas subárvores, que podem ser vazias (nulas).

Passo 3

A característica que torna essa árvore uma “de busca” é a seguinte regra de ordenação: para cada nó com chave k, todas as chaves na sua subárvore esquerda são estritamente menores que k e todas as chaves na sua subárvore direita são estritamente maiores que k. Em notação, se denotarmos por T_{esq} e T_{dir} as subárvores de um nó de chave k, então
\forall\,x\in T_{esq}:\;x<k \quad\text{e}\quad \forall\,y\in T_{dir}:\;y>k.

Passo 4

Graças a essa propriedade, operações básicas de busca, inserção e remoção de uma chave seguem um caminho do nó raiz até uma folha, comparando em cada passo e descendo para a subárvore esquerda ou direita. Se a altura da árvore for h, cada uma dessas operações leva tempo \mathcal{O}(h) no pior caso.

Resposta

Uma árvore binária de busca é uma árvore binária em que cada nó contém uma chave k e, para todo nó, todas as chaves na subárvore esquerda são menores que k e todas as chaves na subárvore direita são maiores que k. Essa propriedade de ordenação permite realizar busca, inserção e remoção de forma eficiente, em tempo proporcional à altura da árvore.

Exercícios relacionados