Esse é o segundo artigo de uma série do qual o nosso objetivo será implementar uma tabela hash usando lista ligada ou busca binária. Mas não se preocupe, cada artigo será independente uma da outra. O artigo será baseado no livro Data Structures & Algorithms In Java de Robert Lafore (2003).

---

A árvore binária é uma das estruturas de dados mais utilizadas na computação, pois ela consegue adicionar e deletar itens de forma eficiente, além de conseguir buscar um item em tempo O(log n). As duas estruturas de dados que geralmente a árvore binária possui vantagem é o vetor ordenado e a lista ligada.

Em uma árvore binária, os elementos são organizados em nós que possuem no máximo dois filhos e, a ordem dos nós que compõe a árvore são determinados de acordo com algumas regras, vamos falar sobre isso mais adiante. Dessa forma, a inserção e a exclusão em uma árvore binária se torna mais eficiente do que em um vetor ordenado, dado que em um vetor ordenado essas duas operações requerem um esforço extra de realocação dos elementos sempre que um novo valor é adicionado ou removido. Em termos de processamento, quando não temos uma ordem fixa pré-determinada dos elementos, como acontece na maioria dos casos, a árvore binária é uma escolha melhor em relação ao vetor ordenado. Porém, em termos de alocação de memória, o vetor ordenado necessita de menos memória para armazenar as mesmas informações se comparado com uma árvore binária, dado que em uma árvore binária é necessário, para cada nó: Alocar espaço de memória para as informações do seu próprio nó, como o seu valor, bem como os ponteiros para os seus nós filhos.

A busca de um valor em uma árvore binária geralmente é mais rápida do que em diversas estruturas de dados, como por exemplo, a lista ligada (ou lista encadeada). Em uma árvore binária, a busca de um elemento pode ser feita em tempo logarítmico O(log n), em que n é o número de elementos na árvore. Essa eficiência se deve pelo fato da árvore binária ser organizada em níveis, de modo que cada nível representa um subconjunto do total de elementos, fazendo com que seja percorrido somente caminhos necessários na árvore. Enquanto isso, a lista ligada não possui essa mesma estrutura de níveis, ou seja, ela possui uma estrutura mais linear, fazendo com que a busca seja menos eficiente em relação à busca na árvore binária. No pior caso, uma lista ligada precisará varrer todos os elementos da lista para encontrar o elemento desejado, isto significa que a busca em uma lista ligada pode ser feito em tempo O(n), o que pode causar problemas de performance em listas muito grandes. A vantagem das listas ligadas em relação à árvore binária é a facilidade na sua implementação.

O que é uma árvore binária?

Antes de definirmos uma árvore binária, é importante sabermos da utilidade das árvores no geral:

Uso de Árvores

Na ciência da computação, uma árvore é uma estrutura de dados que consiste de nós e arestas. Os nós de uma árvore são interligados por meio de arestas. Essa estrutura de dados é uma analogia com a árvore biológica que conhecemos, com raiz, ramificações e folhas. Vamos explicar os conceitos no tópico abaixo.

As árvores são utilizadas em muitos locais da computação, por exemplo:

• Estruturas que formam os sistemas de diretórios nos sistemas operacionais;

• As linguagens de marcação HTML e XML;

• O formato como geralmente enviamos e recebemos dados por meio da arquitetura cliente e servidor com o JSON;

• Otimizações em banco de dados usando B-tree e entre outras;

Estrutura de uma Árvore Binária

Uma árvore binária é representada por um conjunto de nós e arestas, a imagem abaixo mostra um exemplo da estrutura uma árvore binária:

A definição de uma árvore binária é de que cada nó pode ter no máximo dois filhos. Seus filhos são representados pelo nome de filho esquerdo e filho direito. Por exemplo, na imagem acima, o nó C possui dois filhos, que são os nós E e F, em que E é filho esquerdo de C e F é filho direito de C.

Nesse artigo implementaremos uma árvore binária de busca. A diferença entre a árvore binária busca (ABB) e a árvore binária (AB) é que na ABB o filho esquerdo de um nó pai precisa ter uma chave identificadora menor do que ele, e o filho direito de um nó pai precisa ter uma chave identificadora maior do que ele.

Em uma árvore binária, é possível ter apenas um nó raiz. No exemplo da imagem acima, o nó raiz é representado pelo nó A. É esse nó que dá início à árvore T, ou seja, a busca de um nó na árvore geralmente se inicia pelo nó raiz.

Em uma árvore (ou grafo), uma aresta é uma linha que conecta dois nós. Por exemplo, se você tem uma árvore com quatro nós: N1, N2, N3 e N4, e há uma linha que conecta N1 e N2, isso significa que temos uma aresta N1N2. Já um caminho é uma sequência de arestas que conectam dois nós. Por exemplo, se há uma aresta entre N1 e N2 e outra entre N2 e N3, então você pode formar um caminho de N1 para N3 indo de N1 para N2 e depois de N2 para N3. Trazendo esses conceitos para o exemplo da imagem, é possível visualizar uma aresta entre os nós A e C. Um caminho que se inicia no nó A e vai até o nó C é a própria aresta AC. No entanto, um caminho de A até F pode ser representado por {AC, CF}, em que AC e CF são arestas.

Dois outros conceitos importantes em uma árvore são o nó folha e a subárvore. Um nó folha é um nó que não possui filhos, como é o caso do nó I. Enquanto isso, uma subárvore é uma árvore menor que faz parte de uma árvore maior. Em outras palavras, uma subárvore é criada a partir da seleção de um nó, chamado de nó raiz da subárvore, e de todos os seus descendentes, ou seja, seus filhos, netos, bisnetos e assim por diante. No exemplo da figura, apesar de houver outras subárvores na árvore T, a subárvore está sendo representada pelos nós H, J e K, de modo que H é a raiz dessa subárvore.

Uma árvore possui níveis, esses níveis indicam qual é a distância que um determinado nó está da raiz da árvore. Por exemplo, o nível 0 possui apenas o nó raiz A. Já o nível 1, que está a 1 nível da raiz, possui os nós B e C. O nível 2, que está a 2 níveis da raiz, possui os nós C, D, E e F, e assim por diante.

Por fim e não menos importante, existem as árvore balanceadas e desbalanceadas. As árvores se tornam desbalanceadas por causa da ordem em que os elementos são inseridos na árvore. Uma árvore é considerada balanceada quando a distribuição dos seus nós é uniforme. Dependendo da ordem que são inseridos os elementos na árvore, esta árvore pode acabar virando uma lista ligada comum, ou seja, acaba-se perdendo os benefícios que uma árvore binária traz. Existem soluções conhecidas para esse problema, por exemplo, árvore AVL e árvore rubro-negra. Como não é o objetivo deste artigo, não iremos nos aprofundar neste tópico.

Implementação

A implementação da árvore binária será na linguagem Typescript, utilizando conceitos de programação orientada a objetos. Duas classes serão importantes para construção da árvore binária: Tree e Node. A classe Tree representará a árvore como um todo, ou seja, é nela que ficará armazenada a raiz da árvore, as operações de busca, inserção, deleção e assim por diante. Enquanto isso, a classe Node será uma classe relativamente simples porém importante, e o seu papel será representar um nó da árvore. Vamos iniciar por ela.

A classe Node pode ser escrita da seguinte forma:

class Node<T> {
  data: T;
  leftChild?: Node<T>;
  rightChild?: Node<T>;

  constructor(node: Partial<Node<T>>) {
    this.data = node.data as T;
    this.leftChild = node.leftChild;
    this.rightChild = node.rightChild;
  }
}

Ela armazenará um dado genérico do tipo T e seus filhos esquerdo e direito, se houverem. Seus atributos podem ser preenchidos ao instanciar a classe por meio do método construtor.

A próxima etapa é definir uma interface para construir a árvore. A interface não é uma obrigação durante a implementação, porém é uma boa prática de programação. Por exemplo, apesar de serem artigos diferentes, o nosso objetivo é implementar uma tabela hash que faça uso da árvore binária ou da lista ligada. Para que a tabela hash não precise se preocupar com cada estrutura de dados especificamente, o ideal é que ambas estruturas de dados compartilhem a mesma interface, dessa forma as operações da tabela hash não precisam se preocupar com qual tipo de estrutura de dados ela está lidando, ou seja, estaríamos trabalhando diretamente com uma interface (alguns autores chamam de contrato) e não com a implementação específica de cada estrutura. De qualquer forma, vamos focar apenas na árvore binária, no próximo artigo dessa série detalharemos melhor esse ponto. A interface Tree está descrita logo abaixo:

// tree.interface.ts

interface ITree<T> {
  find(value: number | string): Node<T> | undefined;

  insert(data: T): void;

  minimum(): T | undefined;

  maximum(): T | undefined;

  displayInOrder(): void;

  delete(value: number | string): boolean;
}

Inserindo Elementos

O primeiro método a ser desenvolvido será o método insert. Ele consegue inserir um nó por vez. Este nó pode ser o nó raiz para quando a árvore estiver vazia, ou então o nó folha, isto é, um nó que não possui filhos. Na inserção, precisamos encontrar em qual posição o nó deverá ficar, pois como dito anteriormente, em uma árvore binária de busca os nós da subárvore esquerda possuem uma chave (geralmente representado por um valor numérico) inferior ao nó raiz, enquanto que os nós da subárvore direita possuem uma chave superior ao nó raiz. O código abaixo representa o método insert:

class Tree<T> implements ITree<T> {
  private root?: Node<T>;

  constructor(private readonly key: keyof T) {}

  insert(data: T): void {
    const node: Node<T> = new Node({ data });

    if (!this.root) {
      this.root = node;
      return;
    }

    let current: Node<T> | undefined = this.root;
    let parent: Node<T>;

    while (true) {
      parent = current;
      if (data[this.key] < current.data[this.key]) {
        current = current.leftChild;
        if (!current) {
          parent.leftChild = node;
          return;
        }
      } else {
        current = current.rightChild;
        if (!current) {
          parent.rightChild = node;
          return;
        }
      }
    }
  }

  /** os outros métodos vão aqui */
}

Antes de explicar os detalhes do método insert, precisamos entender como está estruturado a classe Tree. A classe Tree espera que seja passado um tipo para ela, é para isso que serve o T em Tree<T>, e além disso ela implementa a interface que criamos no tópico anterior. Outro detalhe relevante é o atributo chamado root, que representa o nó raiz da árvore. O atributo root precisa ser do mesmo tipo da árvore, pois queremos que todos os nós da árvore sejam do mesmo tipo, e por conta disso, ele é do tipo Node<T>. Para construir a árvore da forma correta, precisamos de uma chave identificadora para gerenciar a posição de cada nó na árvore, por isso, o construtor da árvore espera que seja passado uma chave para ela, esta chave precisa ser algum atributo do tipo T.

Para que o entendimento fique mais simples, vamos supor a interface Person:

interface Person {
 id: number;
 name: string;
 lastName: string;
}

os atributos da interface Person são id, name e lastName. Dessa forma, para instânciar a classe Tree poderíamos fazer da seguinte forma:

/** uma árvore de Person em que a chave identificadora é o id  */
const tree = new Tree<Person>('id')

Agora que a estrutura básica da classe Tree<T> está detalhada, conseguimos entender o que o método insert está fazendo. Primeiro, transformamos o objeto que será inserido em um nó do tipo Node. Após isso, precisamos validar se a árvore está vazia. Se a árvore estiver vazia (sem raiz), então o nó que está sendo inserido será a própria raiz da árvore. Caso a condição seja falsa, o método seguirá para as próximas instruções.

A sequência do método se consiste em percorrer a árvore a fim de encontrar a posição ideal para o novo nó. Dentro do loop while, é executado algumas instruções e a validação das chaves do novo nó e do nó atual:

1. atualiza parent recebendo o nó atual. A variável parent funciona como um auxiliar para não perdemos a referência do nó que está sendo percorrido no momento;
2. se a chave do nó a ser inserido for menor do que o nó atual, então:
3. o nó atual será o filho esquerdo desse mesmo nó (nessa etapa não teríamos mais a referência inicial da variável current se não fosse pela variável parent);
4. Se não existir filho esquerdo no nó atual, então o nó a ser inserido será o filho esquerdo de parent - Se existir filho esquerdo no nó atual, o loop continuará sendo executado até que seja encontrado um nó atual de valor nulo;

Essas etapas são as mesmas para caso o nó a ser inserido for maior do que o nó atual, porém nesse caso o percurso será pelo lado direito da árvore (ou subárvore), e não pelo lado esquerdo, como foi o caso acima.

A imagem abaixo mostra um exemplo da posição em que um nó de chave 82 seria inserido em uma determinada árvore:

Repare na imagem acima que o momento atual da árvore é quando a inserção do elemento já está próxima do fim, ou seja, é quando a variável current acessa o seu filho esquerdo, porém o seu filho esquerdo é o valor null. Nesse momento, basta atribuir o novo nó como sendo o filho esquerdo de parent.

Buscando Elementos

O método find procura um nó na árvore por meio do valor da chave do nó, por exemplo, buscar o nó de valor 1 da chave id de Person. Se ele encontrar o nó, ele retorna o próprio nó, caso contrário, ele retorna undefined.

find(value: number | string): Node<T> | undefined {
  let current: Node<T> | undefined = this.root;

  while (current && current.data[this.key] !== value) {
    if (value < current.data[this.key]) {
      current = current.leftChild;
    } else {
      current = current.rightChild;
    }

    if (!current) {
      return;
    }
  }

  return current;
}

O método inicia-se com uma variável chamada current, que será utilizada para percorrer a árvore. A cada iteração é validada se o valor da chave atual se coincide com o valor que estamos buscando. Em caso verdadeiro, basta retornar o nó encontrado, isto é, o valor atual da variável current. Caso contrário, ocorre a mesma validação do método insert explicado nos parágrafos anteriores, ou seja, se o valor que estamos buscando for menor do que o nó atual, percorre-se o filho esquerdo, caso contrário, percorre-se o filho direito. Esse loop acontece até que seja encontrado o nó, ou então, até que o valor de current seja null.

Buscando Valor Máximo e Mínimo

Por conta das características de uma árvore binária de busca, é muito simples escrever um algoritmo para encontrar os valores de máximo e mínimo de toda a árvore. Para encontrar o valor mínimo, basta acessar o filho esquerdo da raiz da árvore, e depois novamente o filho esquerdo, ...e assim por diante, até que o filho esquerdo seja o valor nulo. Para encontrar o valor máximo, basta fazer o mesmo procedimento, porém para lado direto da árvore. O algoritmo abaixo mostra como encontrar o valor mínimo ou máximo da árvore:

minimum(): T | undefined {
  return this.findMinMax('leftChild');
}

maximum(): T | undefined {
  return this.findMinMax('rightChild');
}

private findMinMax(key: 'leftChild' | 'rightChild'): T | undefined {
  let current: Node<T> | undefined,
    last: Node<T> | undefined = undefined;
  current = this.root;

  while (current) {
    last = current;
    current = current[key];
  }

  return last?.data;
}

Percorrendo a Árvore

De acordo com Lafore(2003), existem três formas simples de percorrer a árvore: preorder, inorder e postorder. A implementação será usando o método inorder.

displayInOrder() {
  if (this.root) {
    this.inOrder(this.root);
  }
}

private inOrder(localRoot?: Node<T>) {
  if (localRoot) {
    this.inOrder(localRoot.leftChild);
    console.log(localRoot.data);
    this.inOrder(localRoot.rightChild);
  }
}

O método displayInOrder executa um método chamado inOrder. Esse método percorre toda a árvore de forma ascendente, ou seja, para a ABB que estamos implementando aqui, será da menor chave para a maior chave da árvore. De forma geral, é um método recursivo que visita nó por nó exibindo o dado contido em cada nó visitado. No entanto, durante cada visita, ele pode fazer qualquer outra operação que seja diferente de apenas uma exibição de dado.

Vale ressaltar que percorrer toda a árvore pode ser um problema a depender dos recursos de hardware do computador e/ou por conta do tamanho da árvore.

Como dito anteriormente, existem três formas de percorrer uma árvore: preorder, inorder e postorder e cada uma delas possui uma especificidade:

• Preorder: Visita-se primeiro a raiz, em seguida a subárvore esquerda e, por fim, a subárvore direita;
• Inorder: Visita-se primeiro a subárvore esquerda, a raiz e por fim, a subárvore direita;
• Postorder: visita-se as subárvores esquerda e direita, e por fim, a raiz;

Removendo Um Nó

Remover um nó de uma ABB envolve diversos cenários que precisam ser levados em consideração, pois:

• O nó pode ser folha, isto é, sem filhos;
• O nó pode ter um único filho, esquerdo ou direito;
• O nó pode ter dois filhos, esquerdo e direito;

A primeira parte para deletar um nó é encontrá-lo na árvore, veja o código abaixo:

delete(value: number | string): boolean {
  let current = this.root;
  let parent = this.root;
  let isLeftChild = true;

  while (current && current.data[this.key] != value) {
    parent = current;
    if (value < current.data[this.key]) {
      isLeftChild = true;
      current = current.leftChild;
    } else {
      isLeftChild = false;
      current = current.rightChild;
    }

    if (!current) {
      return false;
    }
  }

  /** ...o restante da implementação */
}

A primeira parte desse algoritmo consiste em encontrar o nó por meio do valor da sua chave (lembre que a chave foi definida no construtor da classe Tree) e armazená-lo na variável current. A variável parent armazena o nó pai de current, e a variável isLeftChild indica se o nó current é o filho esquerdo ou direito em relação ao nó pai. Caso o nó não seja encontrado, basta retornar falso, indicando falha na remoção do nó.

Removendo Um Nó Folha

Para remover um nó folha é bem simples, basta que o nó pai do nó current pare de apontar para o próprio nó current. O único detalhe de atenção é que esse nó pode ser o nó raiz, o código abaixo representa a remoção de um nó folha:

private deleteNoChildNode({ current, isLeftChild, parent }: DeleteNode<T>) {
  if (current?.data[this.key] === this.root?.data[this.key]) {
    this.root = undefined;
  } else if (isLeftChild) {
    if (parent) parent.leftChild = undefined;
  } else {
    if (parent) parent.rightChild = undefined;
  }
}

Criamos um método específico para esse caso e para usar o método deleteNoChildNode no método delete, basta inserir as seguintes validações:

delete(value: number | string): boolean {
  /** ...o início do método */

  const params: DeleteNode<T> = { current, parent, isLeftChild };
  if (!current?.leftChild && !current?.rightChild) {
    this.deleteNoChildNode(params);
  }

  return true;
}

É possível notar um tipo chamado DeleteNode<T>, essa interface será comum para os outros métodos de remoção do nó, ela está definida da seguinte forma:

export interface DeleteNode<T> {
  current?: Node<T>;
  parent?: Node<T>;
  isLeftChild: boolean;
}

Removendo Um Nó Com Apenas Um Filho

A remoção para quando o nó possui apenas um filho, direito ou esquerdo, pode ser desenvolvido da seguinte forma:

private deleteNoRightChildNode({
  current,
  isLeftChild,
  parent,
}: DeleteNode<T>) {
  if (current?.data[this.key] === this.root?.data[this.key]) {
    this.root = current?.leftChild;
  } else if (isLeftChild) {
    if (parent) parent.leftChild = current?.leftChild;
  } else {
    if (parent) parent.rightChild = current?.leftChild;
  }
}

private deleteNoLeftChildNode({
  current,
  isLeftChild,
  parent,
}: DeleteNode<T>) {
  if (current?.data[this.key] === this.root?.data[this.key]) {
    this.root = current?.rightChild;
  } else if (isLeftChild) {
    if (parent) parent.leftChild = current?.rightChild;
  } else {
    if (parent) parent.rightChild = current?.rightChild;
  }
}

Os dois métodos acima são usados no método principal:

delete(value: number | string): boolean {
  
  /** ...Código anterior */

  else if (!current?.rightChild) {
    this.deleteNoRightChildNode(params);
  } else if (!current?.leftChild) {
    this.deleteNoLeftChildNode(params);
  }
  
  /** ...Restante do método */
}

Agora precisamos entender o que esses trechos de código fazem. Sabemos que:

• current é o nó que será removido;
• isLeftChild é um booleano que indica se o nó current é filho esquerdo do nó pai ou não;
• parent é o nó pai de current;

Então, o método deleteNoRightChildNode verifica se o nó que será removido é o nó raiz - Em caso positivo, o novo nó raiz será o filho esquerdo desse nó, dado que nesse caso não temos filho direito - Em caso negativo, precisamos saber se o nó a ser removido é filho esquerdo ou não do seu nó pai. Caso a condição seja verdadeira, então o novo filho esquerdo do nó pai será o filho esquerdo do nó a ser removido. O último caso é quando o nó a ser removido não é um nó raiz e é filho direito do seu pai. Nesse caso, o filho esquerdo do nó a ser removido será o filho direito do seu nó pai. A imagem abaixo mostra como seria esse último caso:

No exemplo do método deleteNoRightChildNode mostrado acima, não precisamos verificar o filho direito do nó current, dado que já validamos ele nas condicionais dentro do método delete.

O método deleteNoLeftChildNode é análogo ao método apresentado acima, porém para o filho direito do nó a ser removido.

Removendo Um Nó Com Dois Filhos

Dos três tipos de remoções que uma ABB pode ter, essa é a que possui maior dificuldade. Devido a sua complexidade, existe um artifício que os autores usam para fazer a remoção de um nó que possui dois filhos, chamado de sucessor. A ideia por trás do nó sucessor é bem simples: O nó sucessor é o nó mais à esquerda da subárvore direita do nó que será removido, em outras palavras, ele é o menor nó da subárvore que é maior do que o nó original. A imagem abaixo mostra o funcionamento dessa estratégia:

O exemplo acima foi baseado no livro Data Structures & Algorithms In Java, 2ª edição, de Robert Lafore, especificamente da página 394 do Capítulo 8.

O algoritmo abaixo encontra o nó sucessor de um nó que será removido:

private findSuccessor(delNode: Node<T>): Node<T> {
  let successorParent = delNode;
  let successor = delNode;
  let current = delNode.rightChild;
  while (current) {
    successorParent = successor;
    successor = current;
    current = current.leftChild;
  }

  if (successor.data[this.key] !== delNode.rightChild?.data[this.key]) {
    successorParent.leftChild = successor.rightChild;
    successor.rightChild = delNode.rightChild;
  }

  return successor;
}

A variável current inicia-se como sendo o nó filho direito do nó que será removido, isto é, um nó maior do que o nó original, como foi explicado no parágrafo anterior. Após isso, ele percorre todos os filhos à esquerda desse nó, até que seja encontrado o final da subárvore. O nó sucessor do nó que será removido fica armazenado na variável successor. No entanto, existe uma condicional antes do retorno da variável succcessor, essa condição está lá pois existem dois cenários para levarmos em consideração ao encontrar o nó sucessor:

O nó sucessor é filho direito do nó a ser removido

Este é um caso mais simples, o código está abaixo:

delete(value: number | string): boolean {
  
  /** ...Código anterior */
  else {
    this.deleteNodeWithTwoChildren(params);
  }

  return true;
  
  /** ...Restante do método */
}

private deleteNodeWithTwoChildren({
  current,
  isLeftChild,
  parent,
}: DeleteNode<T>) {
  const successor = current && this.findSuccessor(current);

  if (!successor) {
    return;
  }

  if (current?.data[this.key] === this.root?.data[this.key]) {
    this.root = successor;
  } else if (isLeftChild) {
    if (parent) parent.leftChild = successor;
  } else {
    if (parent) parent.rightChild = successor;
  }
  successor.leftChild = current?.leftChild;
}

A ideia por trás do código é simples, encontrar o nó sucessor e validar alguns cenários:

• Se o nó a ser removido for o nó raiz, então o novo nó raiz será o nó sucessor.
• Se o nó a ser removido é filho direito do seu pai e o sucessor é o filho direito do nó a ser removido, então o sucessor entra no lugar do nó a ser removido, que nada mais é do que o filho direito de parent. Por fim, o filho esquerdo do nó sucessor será o filho esquerdo do nó removido.

A imagem abaixo mostra a remoção de um nó para quando o nó sucessor é filho direito do nó a ser removido:

Um detalhe importante é que o nó sucessor nunca terá o seu filho esquerdo, pois a ideia do algoritmo é encontrar o menor nó da subárvore direita do nó a ser deletado, ou seja, é um algoritmo que percorre um caminho sempre direcionado para o filho esquerdo do nó, até que o filho esquerdo desse nó seja nulo.

O nó sucessor é filho esquerdo da subárvore direita do nó a ser removido

Este cenário é um pouco mais complexo do que para quando o sucessor é o filho direito do nó a ser deletado. Para esse caso, são necessários alguns passos extras. Anteriormente, foi colocado uma condicional no final do método findSuccessor, especificamente esse trecho:

if (successor.data[this.key] !== delNode.rightChild?.data[this.key]) {
  successorParent.leftChild = successor.rightChild;
  successor.rightChild = delNode.rightChild;
}

Compilando a condicional acima junto o que já existe no final do método deleteNodeWithTwoChildren, quatro instruções precisam ser executadas (é o que precisamos para deletar um nó com dois filhos de forma que o sucessor desse nó seja filho esquerdo da subárvore direita dele):

1. successorParent.leftChild = successor.rightChild
2. successor.rightChild = delNode.rightChild
3. parent.rightChild = successor
4. successor.leftChild = current?.leftChild

As imagens abaixo mostram um exemplo dessas etapas sendo executadas:

Como dito no parágrafo anterior, as etapas 3 e 4 foram desenvolvidas anteriormente no método deleteNodeWithTwoChildren.

Uma outra abordagem para a remoção de um nó em uma ABB seria apenas inserir uma flag de nó removido, por exemplo, poderíamos criar um atributo delete_at na classe Node indicando que um nó foi removido. A vantagem de fazer dessa forma é que a implementação fica mais simples e também conseguimos ter um histórico de quais dados já foram inseridos na árvore. Porém, a desvantagem desse método é que poderíamos ter problemas de recursos de memória e em alguns casos de processamento, pois um nó deletado virtualmente sempre teria que ser revisitado e revalidado em todos os cenários que ocorrem uma busca.

Conclusão

A árvore binária de busca é uma estrutura de dados importante e amplamente utilizada na computação. Ela oferece uma forma eficiente de buscar, inserir e remover informações, na maioria dos casos em tempo logarítmico. No entanto, apesar de não termos nos aprofundado nesse tópico, é importante lembrar que a eficiência da árvore depende do seu balanceamento, o que pode ser um desafio em casos de inserções ou remoções frequentes. Considerando isso, é fundamental entender as características e propriedades de uma ABB para utilizá-la de forma adequada em diferentes aplicações.

O código fonte está disponível no github. Nesse repositório diversos testes unitários foram criados para garantir a verificidade do código desenvolvido.

Se você leu até aqui, quero te mandar um obrigado! E qualquer sugestão de melhoria é bem-vinda :D

Referências

• LAFORE, Robert. Data Structures & Algorithms In Java. 2. ed. Indianápolis: Sams, 2003. 776 p.