Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária de busca (BST)
Á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)
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
, todas as chaves na sua subárvore esquerda são estritamente menores que
e todas as chaves na sua subárvore direita são estritamente maiores que
. Em notação, se denotarmos por
e
as subárvores de um nó de chave
, então
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
, cada uma dessas operações leva tempo
no pior caso.
Resposta
Uma árvore binária de busca é uma árvore binária em que cada nó contém uma chave
e, para todo nó, todas as chaves na subárvore esquerda são menores que
e todas as chaves na subárvore direita são maiores que
. Essa propriedade de ordenação permite realizar busca, inserção e remoção de forma eficiente, em tempo proporcional à altura da árvore.