Árvore de busca binária

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

Árvores de busca binária são árvores binárias 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.

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

  2
 / \
1   3

Conceitos

Á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.
Árvore Binária de Busca Balanceada: Árvore binária de busca onde a altura das subárvores esquerda e direita de cada nó difere no máximo em uma unidade.
Árvore Binária de Busca Balanceada Completa: Árvore binária de busca balanceada onde todos os níveis estão

ADT Árvore Binária de Busca

O ADT é o mesmo da árvore binária. Com a diferneça de que na inserção precisamos garantir que a árvore continue sendo uma árvore de busca binária. Ou seja, ao inserir um novo valor, devemos garantir que ele seja inserido na posição correta de acordo com a propriedade da árvore de busca binária.

Árvore de Busca Binária vs Array ordenado

A busca tem mesmo custo O(log n) em ambos. A diferença é que a inserção e remoção são O(log n) na árvore de busca binária, enquanto no array ordenado são O(n).