Como remover um nó em uma árvore binária de busca

Escrito por david weinberg | Traduzido por victor rodrigues
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como remover um nó em uma árvore binária de busca
As árvores binárias de busca são boas para rápidas requisições e informações de dados (Jason Reed/Ryan McVay/Photodisc/Getty Images)

As árvores binárias de busca são usadas ​​para organizar dados sequenciais para uma fácil busca. Cada nó em uma árvore binária de busca possui nenhum, um ou dois filhos. O filho esquerdo de um nó é sempre menor que o pai e o direito, sempre maior. Assim, quando buscamos um nó específico, podemos comparar o alvo com o nó atual. Se o objeto de busca for maior que o nó atual, continua-se buscando a partir do ramo direito, se for menor, buscamos a partir do ramo esquerdo. Isso proporciona um grande benefício na busca e comparação ao percorrer uma lista ordenada com esses valores. Excluir os nós de uma árvore binária é um pouco mais complicado que adicionar novos ou busca de antigos. Dependendo da situação, podemos ter de reorganizar a árvore para garantir que os filhos de cada nó continuem devidamente equilibrados.

Nível de dificuldade:
Moderado

Outras pessoas estão lendo

Instruções

    Eliminando um nó folha

  1. 1

    Veja se o nó não tem filhos.

  2. 2

    Encontre o pai desse nó e configure a referência "filho" desse nó pai para nulo.

  3. 3

    Remova o nó de seu vetor de armazenamento.

    Removendo um nó com um filho

  1. 1

    Verifique se o nó tem apenas um filho.

  2. 2

    Encontre pai desse nó e configure a referência "filho" do pai para fazer referência ao filho do nó que você estiver excluindo.

  3. 3

    Remova o nó de seu vetor de armazenamento.

    Removendo um nó com dois filhos

  1. 1

    Verifique se o nó possui dois filhos.

  2. 2

    Encontre o maior nó da árvore à esquerda dele (nó antecessor). Isso pode ser feito seguindo um nó para a esquerda e, em seguida, andar na árvore para a direita, até que não existam mais nós.

  3. 3

    Configure a referência do filho da direita do nó antecessor para referenciar o filho da direita do nó que você estiver excluindo.

  4. 4

    Substitua a referência do nó pai para o antecessor.

  5. 5

    Remova o nó de seu vetor de armazenamento.

Dicas & Advertências

  • Exclusões múltiplas podem fazer sua árvore tornar-se desequilibrada. Se você notar que seu programa está sendo executado lentamente, depois de muitas exclusões, você deve fazê-lo balancear a árvore nessa ocasião.

Não perca

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível