Dificuldade ★☆☆
4 minutos de Leitura 🕒
Uma Árvore Binária de Busca (BST - Binary Search Tree) é uma estrutura de dados não linear em forma de árvore e na qual seus elementos são organizados de forma hierárquica. Nessa estrutura, cada nó possui no máximo dois filhos (esquerda e direta) e respeita a propriedade fundamental de hierarquia: para um dado no v, todos os elementos na subárvore da esquerda são menores que o elemento armazenado em v, e todos os elementos na subárvore da direita são maiores.
Bancos de Dados - Árvores Binárias de Busca podem usadas na implementação de índices em bancos de dados, permitindo uma busca rápida e eficiente pelos registros.
Sistemas de Busca - Árvores Binárias de Busca podem ser usadas para organizar e buscar informações de maneira eficiente, em motores de busca e sistemas de indexação.
Sistemas de Arquivos - Árvores Binárias de Busca podem ser usadas para indexar e localizar arquivos de maneira eficiente, em sistemas de arquivos que exigem rápida busca e recuperação de informações.
Uma Árvore Binária de Busca t pode ser construída recursivamente com os seguintes componentes:
t.elemento: uma célula que armazena o elemento em um nó da árvore.t.esquerda: um ponteiro para a subárvore da esquerda.t.direita: um ponteiro para a subárvore da direita.inserir() insere um novo elemento em uma Árvore Binária de Busca.remover() remove um elemento de uma Árvore Binária de Busca.buscar() procura um elemento específico em uma Árvore Binária de Busca.Comece pela raiz da árvore. Se a árvore estiver vazia, o novo nó será inserido como raiz.
Compare o valor do nó que está sendo inserido com o valor do nó atual.
Se o valor do nó que está sendo inserido for menor que o valor do nó atual, vá para a subárvore esquerda. Se a subárvore esquerda estiver vazia, insira o novo nó como filho esquerdo do nó atual. Caso contrário, continue percorrendo a subárvore esquerda recursivamente, repetindo os passos 2 e 3 até encontrar um local adequado para a inserção.
Se o valor do nó que está sendo inserido for maior que o valor do nó atual, vá para a subárvore direita. Se a subárvore direita estiver vazia, insira o novo nó como filho direito do nó atual. Caso contrário, continue percorrendo a subárvore direita recursivamente, repetindo os passos 2 e 4 até encontrar um local adequado para a inserção.
Uma vez encontrado o local adequado, insira o novo nó na posição correta como filho esquerdo ou direito do nó atual, dependendo da comparação dos valores.
Comece pela raiz da árvore e encontre o nó que deseja remover. Se a árvore estiver vazia ou o nó não existir na árvore, a remoção não é possível.
Se o nó que deseja remover for uma folha (nó sem filhos), basta removê-lo diretamente da árvore, ajustando os ponteiros dos nós adjacentes.
Se o nó que deseja remover tiver apenas um filho, substitua o nó a ser removido pelo seu filho. Ajuste os ponteiros dos nós adjacentes para que o nó seja removido corretamente da árvore.
Se o nó que deseja remover tiver dois filhos, encontre o sucessor do nó a ser removido. O sucessor é o nó com o menor valor na subárvore direita do nó a ser removido ou o predecessor, que é o nó com o maior valor na subárvore esquerda. O sucessor (ou predecessor) será um nó que pode ter, no máximo, um filho.
Mova o valor do sucessor (ou predecessor) para o nó que deseja remover.
Veja o código completo no GitHub.