Estrutura de dados de Árvore

Uma árvore é um modelo abstrato de uma estrutura hierárquica

O exemplo mais comum de uma árvore na vida real seria o de uma árvore genealógica ou o organograma de uma empresa, ou até mesmo o próprio documento HTML

Terminologia de árvores

Uma árvore é constituída de nós (ou nodos) com um relacionamento pai-filho

Todo nó tem um pai (exceto o primeiro nó no topo) e zero ou mais filhos

O nó no topo de uma árvore é chamado de raiz, é o nó que não tem pai

Cada elemento da árvore é chamado de nó. Há nós internos e nós externos

Um nó interno é um nó que tem pelo menos um filho

Um nó que não tem filhos é chamado de nó externo ou folha

Um nó pode ter ancestrais e descendentes

Os ancestrais de um nó (exceto a raiz) são o pai, avô, o bisavô, e assim sucessivamente

Os descendentes de um nó são os filhos (filho), os netos (neto), os bisnetos (bisneto), e assim por diante

Outra terminologia usada em árvores é o termo subárvore

Uma subárvore é composta de um nó e seus descendentes

A profundidade de um nó corresponde ao número de ancestrais

A altura de uma árvore corresponde à profundidade máxima dos nós, a raiz está no nível 0, seus filhos estão no nível 1, e assim sucessivamente

Agora que vimos os termos mais importantes relacionados às árvores, podemos conhecê-las melhor

Árvore Binária e Árvore Binária de Busca

Um nó em uma árvore binária tem no máximo dois filhos; um filho à esquerda e um filho à direita

Essa definição nos permite escrever algoritmos mais eficazes para inserir, pesquisar e remover nós na árvore

As árvores binárias são muito usadas em ciência da computação

Uma BST (Binary Search Tree), ou Árvore Binária de Busca) é uma árvore binária, mas permite armazenar somente nós com valores menores do lado esquerdo e nós com valores maiores do lado direito

Essa é a estrutura de dados com a qual vamos trabalhar nesse artigo

Criando as classes Node e BinarySearchTree

Antes de começar a implementar nossa classe, vamos começar com alguns métodos auxiliares

Vamos criar Compare e defaultCompare

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}

Vamos agora criar a nossa clase NodeTree que representará cada nó de nossa árvore binária de busca, usando o código a seguir:

class NodeTree {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

Assim como funciona nas listas ligadas (Linked List), vamos trabalhar com ponteiros (referências) para representar a conexão entre os nós, chamadas de edges na terminologia de árvore

Quando utilizamos com uma lista duplamente ligada, cada nó tem dois ponterios: um para indicar o próximo nó e outro para indicar o nó anterior

Ao trabalhar com árvores, usaremos a mesma abordagem, isto é, trabalharemos também com dois ponteiros

No entanto, um ponteiro referenciará o filho à esquerda, enquanto o outro apontará para o filho à direita

Por esse motivo, precisaremos de uma classe NodeTree que representará cada nó da árvore

Um pequeno detalhe que vale a pena mencionar é que, em vez de chamar o nó propriamente dito de nó ou de item, nós o chamaremos de key

Uma chave (key) é o termo pelo qual um nó é conhecido na terminologia de árvores

A seguir, vamos declararemos a estrutura básica de nossa classe BinarySearchTree:

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn
    this.root = null
  }
}

Nos vamos utilizar uma variável para que possamos controlar o primeiro nó da estrutura de dados

No caso de uma árvore, temos root

A seguir, os métodos que criaremos em nossa clase BinarySearchTree:

- insert(key): esse método insere uma nova chave na árvore

- search(key): esse método busca a chave na árvore e devolve true se ela existir, e false se o nó não existir

- inOrderTraverse(): esse método visita todos os nós da árvore usando um percurso em-order (in-order)

- preOrderTraverse(): esse método visita todos os nós da árvore usando um percurso pré-ordem (pre-order)

- postOrderTraverse(): esse método visita todos os nós da árvore usando um percurso pós-ordem (post-order)

- min(): esse método devolve a chave/valor mínimo da árvore

- max(): esse método devolve a chave/valor máximo da árvore

- remove(key): esse método remove a chave da árvore

Vamos implementar cada um desses métodos

Inserindo uma chave na BST

Os métodos que vamos implementar irão utilizar recursão, se você ainda não tem familiaridade com esse assunto dê uma olhada em meu outro artigo que falo sobre recursão com Javascript

O código a seguir é a primeira parte do algoritmo usado para inserir uma nova key em uma árvore:

insert(key) {
  if (this.root === null) { // {1}
    this.root = new NodeTree(key) // {2}
  } else {
    this.insertNode(this.root, key) // {3}
  }
}

Para inserir um novo nó (ou key) em uma árvore, há dois passos que devemos seguir

O primeiro é verificar se a inserção constitui um caso especial

O caso especial para a BST é o cenário em que o nó que estamos tentando adicionar é o primeiro nó da árvore

Se for, tudo que temos a fazer é apontar root para esse novo nó criando uma instância da classe NodeTree e atribuindo-a à propriedade root

Por causa das propriedades do construtor de NodeTree, basta passar o valor que queremos adicionar na árvore (key), e seus ponteiros left e right terão automaticamente o valor null

O segundo passo consiste na adição do nó em uma posição que não seja o root

Nesse caso, precisaremos de um método auxiliar para nos ajudar a fazer isso, esse método deve ser declarado dessa maneira:

insertNode(node, key) {
  if (this.compareFn(key, node.key) === Compare.LESS_THAN) { // {4}
    if (node.left === null) { // {5}
      node.left = new NodeTree(key) // {6}
    } else {
      this.insertNode(node.left, key) // {7}
    }
  } else {
    if (node.right === null) { // {8}
      node.right = new NodeTree(key) // {9}
    } else {
      this.insertNode(node.right, key) // {10}
    }
  }
}

A função insertNode node ajudará a encontrar o lugar correto para inserir um novo nó

A lista a seguir descreve o que esse método faz:

Se a árvore não estiver vazia, devemos encontrar um local para adicionar o novo nó. Por esse motivo, chamaremos o método insertNode passando o nó raiz e a chave que queremos inserir como parâmetros
Se a chave do nó for menor que a chave do nó atual (nesse caso, é a raiz), devemos verificar o filho à esquerda do nó. Observe que estamos usando aqui a função compareFn, que pode ser passado no construtor da classe BST para comparar os valores, pois key pode não ser um número, mas um objeto complexo. Se não houver um nó à esquerda, a nova key será inserida nesse local. Caso contrário, devemos descer um nível na árvore chamando insertNode recursivamente. Nesse caso, o nó com o qual faremos a comparação na próxima vez será o filho à esquerda do nó atual (subárvore do nó à esquerda)
Se a chave do nó for maior que a chave do nó atual e não houver nenhum filho à direita, a nova chave será inserida nesse local. Caso contrário, também chamaremos o método insertNode recursivamente, porém o novo nó a ser comparado será o filho à direita - a subárvore do nó à direita

Vamos aplicar essa lógica em um exemplo para que possamos compreender melhor esse processo

Considere o seguinte cenário: temos uma nova árvore e estamos tentando inserir a sua primeira chave. Nesse caso, executaremos este código:

const tree = new BinarySearchTree()
tree.insert(11)

Nesse cenário, teremos um único nó em nossa árvore e a propriedade root apontará para ele

Agora vamos popular nossa árvore com os seguintes valores:

tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

Gostaríamos de inserir uma nova chave cujo valor é 6, portanto executaremos o código a seguir também:

tree.insert(6)

Eis os passos que serão executados:

A árvore não está vazia, portanto o código da linha {3} será executado. O código chamará o método insertNode(root, key[6])
O algoritmo verificará a linha {4} (key[6] < root[11] é true), depois verificará a linha {5} (node.left[7] não é null) e, por fim, passará para a linha {7} chamando insertNode(node.left[7], key[6])
Entraremos no método insertNode novamente, porém com parâmetros diferentes. O código verificará a linha {4} de novo (key[6] < node[7] é true), depois verificará a linha {5} (node.left[5] não é null) e, por fim, passará para a linha {7} chamando insertNode(node.left[5], key[6])
Executaremos o método insertNode mais uma vez. O código verificará a linha {4} novamente (key[6] < node[5] é false), depois passará para a linha {8} (node.right é null -- o nó 5 não tem nenhum filho à direita como descendente) e, por fim, a linha {9} será executada, inserindo a chave 6 como filho à direita do nó 5
Depois disso, as chamadas dos métodos serão desempilhadas e a execução terminará

Percorrendo uma árvore

Percorrer uma árvore (ou caminhar por ela) é o processo de visitar todos os seus nós e executar uma operação em cada um deles

Entretanto, como devemos fazer isso? Devemos começar do topo da árvore ou da parte inferior? Do lado esquerdo ou do lado direito? Há três abordagens distintas que pode ser usadas para visitar todos os nós de uma árvore: em-order (in-order), pré-ordem (pre-order) e pós-ordem (post-order)

Vamos explorar melhor as implementações desses três tipos de percurso em árvores

Percurso em-ordem

Um percurso em-ordem (in-order) visita todos os nós de uma BST em ordem crescente, o que significa que todos os nós serão visitados, do menor para o maior

Uma aplicação do percurso em-ordem seria ordenar uma árvore. Vamos dar uma olhada na sua implementação:

inOrderTraverse(callback) {
  this.inOrderTraverseNode(this.root, callback) // {1}
}

O método inOrderTraverse recebe uma função callback como parâmetro, a qual pode ser usada para executar a ação desejada quando visitamos o nó

Como a maior parte dos algoritmos que estamos implementando para a BST é recursiva, usaremos um método auxiliar que receberá o nó root da árvore (ou subárvore) e a função callback {1}

O método auxiliar está listado a seguir:

inOrderTraverseNode(node, callback) {
  if (node !== null) { // {2}
    this.inOrderTraverseNode(node.left, callback) // {3}
    callback(node.key) // {4}
    this.inOrderTraverseNode(node.right, callback) // {5}
  }
}

Para percorrer uma árvore usando o método em-ordem, devemos inicialmente verificar se o node da árvore passado como parâmetro é null ({2} -- esse é o ponto em que a recursão é interrompida, ou seja, é o caso de base do algoritmo de recursão)

Em seguida, visitamos o nó à esquerda {3} chamando a mesma função recursivamente

Então visitamos o nó raiz {4} executando uma ação nesse nó (callback) e depois visitamos o nó à direita {5}

Vamos tentar executar esse método usando a àrvore que criamos mais acima na explicação, assim:

const printNode = (value) => console.log(value) // {6}
tree.inOrderTraverse(printNode) // {7}

Em primeiro lugar, devemos criar uma função de callback {6}

Tudo que faremos é exibir o valor do nó no console do navegador

Então podemos chamar o método inOrderTraverse passando a nossa função de callback como parâmetro {7}

Quando esse código for executado, a saída a seguir será exibida no console (cada número será mostrado em uma linha diferente)

3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

Percurso pré-ordem

Um percurso pré-ordem (pre-order) visita o nó antes de visitar seus descendentes

Uma aplicação do percurso pré-ordem seria exibir um documento estruturado

Vamos analisar a sua implementação:

preOrderTraverse(callback) {
  this.preOrderTraverseNode(this.root, callback)
}

Aqui está a implementação do método preOrderTraverseNode:

preOrderTraverseNode(node, callback) {
  if (node !== null) {
    callback(node.key) // {1}
    this.preOrderTraverseNode(node.left, callback) // {2}
    this.preOrderTraverseNode(node.right, callback) // {3}
  }
}

A diferença entre os percursos em-ordem e pré-ordem é que o percurso pré-ordem visita o nó raiz antes {1}, depois o nó à esquerda {2} e, por fim, o nó à direita {3}, enquanto o percurso em-ordem executa as linhas na seguinte ordem: {2}, {1} e {3}

A saída a seguir será: 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

Percurso pós-ordem

Um percurso pós-ordem (post-order) visita o nó depois de visitar os seus descendentes

Uma aplicação do percurso pós-ordem poderia ser calcular o espaço usado por um arquivo em um diretório e em seus subdiretórios

Vamos dar uma olhada na sua implementação:

postOrderTraverse(callback) {
  this.postOrderTraverseNode(this.root, callback)
}

Agora a implementação de postOrderTraverseNode:

postOrderTraverseNode(node, callback) {
  if (node !== null) {
    this.postOrderTraverseNode(node.left, callback) // {1}
    this.postOrderTraverseNode(node.right, callback) // {2}
    callback(node.key) // {3}
  }
}

Nesse caso, o percurso pós-ordem visitará o nó à esquerda {1}, depois o nó à direita {2} e, por último, o nó raiz {3}

Os algoritmos para as abordagens em-ordem, pré-ordem e pós-ordem são muito parecidos; a única diferença está na ordem em que as linhas {1}, {2} e {3} são executadas em cada método

Essa será a saída exibida no console:

3 6 5 8 10 9 7 12 14 13 18 25 29 15 11

Pesquisando valores em uma árvore

Há três tipos de pesquisa geralmente executados em árvores:

pesquisa de valores mínimos
pesquisa de valores máximos
Vamos analisar cada uma dessas pesquisas

Pesquisando valores mínimos e máximos

Inicialmente vamos analisar o método que encontrará a chave mínima da árvore:

min(node) {
  return this.minNode(this.root) // {1}
}

O método min será o método exposto ao usuário, o qual chama o método minNode {1}, declarado a seguir:

minNode(node) {
  let current = node
  while(current !== null && current.left !== null) { // {2}
    current = current.left // {3}
  }
  return current // {4}
}

O método minNode nos permite encontrar a chave mínima, a partir de qualquer nó da árvore

Podemos usá-lo para encontrar a chave mínima de uma subárvore ou da própria árvore

Por esse motivo, chamaremos o método minNode passando o nó root da árvore {1}, pois queremos encontrar a chave mínima de toda a árvore

No método minNode, percorremos a aresta esquerda da árvore (linhas {2} e {3}) até encontrar o nó no nível mais alto dela (na extremidade esquerda)

De modo semelhante, também temos o método max, cujo código apresenta o aspecto a seguir:

max() {
  return this.maxNode(this.root)
}

maxNode(node) {
  let current = node
  while (current !== && current.right !== null) { // {5}
    current = current.right
  }
  return current
}

Para encontrar a chave máxima, percorremos a aresta direita da árvore {5} até encontrar o último nó na extremidade direita dela

Assim, para o valor mínimo, sempre percorreremos o lado esquerdo da árvore; para o valor máximo, sempre navegaremos para o lado direito dela

Pesquisando um valor específico

Vamos implementar o método search para a BST, o código do método será implementado da seguinte forma:

search(key) {
  return this.searchNode(this.root, key) // {1}
}

searchNode(node, key) {
  if (node === null) { // {2}
    return false
  }
  if (this.compareFn(key, node.key) === Compare.LESS_THAN) { // {3}
    return this.searchNode(node.left, key) // {4}
  } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { // {5}
    return this.searchNode(node.right, key) // {6}
  } else {
    return true // {7}
  }
}

Nossa primeira tarefa deve ser declarar o método search

Seguindo o padrão dos demais métodos declarados para a BST, usaremos um método auxiliar para nos ajudar na lógica de recursão {1}

O método searchNode pode ser usado para encontrar uma chave específica na árvore ou em qualquer uma de suas subárvores

Esse é o motivo pelo qual chamaremos esse método na linha {1} passando o nó root da árvore como parâmetro

Antes de iniciar o algoritmo, validaremos se o node passado como parâmetro é válido (não é null ou undefined)

Se for válido, é sinal de que a chave não foi encontrada, e devolveremos false

Se o nó não for null, devemos continuar a pesquisa

Se a key que estamos procurando for menor que o nó atual {3}, continuaremos a pesquisa usando a subárvore do filho à esquerda {4}

Se o valor que estamos procurando for maior que o nó atual {5}, continuaremos a pesquisa a partir do filho à direita do nó atual {6}

Caso contrário, significa que a chave que estamos procurando é igual à chave do nó atual, e devolveremos true para informar que ela foi encontrada {7}

Podemos testar esse método usando o código a seguir:

console.log(tree.search(1) ? 'Key 1 found' : 'Key 1 not found')
console.log(tree.search(8) ? 'Key 8 found' ? 'Key 8 not found')

Eis a saída exibida:

Value 1 not found
Value 8 found

Vamos descrever mais detalhes sobre como o método foi executado para encontrar a chave 1:

Chamamos o método searchNode passando o root da árvore como parâmetro {1}. node[root[11]] não é null {2}, portanto passamos para a linha {3}
key[1] < node[11] é true {3}, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando node[7], key[1] como parâmetros
node[7] não é null {2}, portanto passamos para a linha {3}
key[1] < node[7] é true, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando node[5], key[1] como parâmetros
node[5] não é null {2}, portanto passamos para a linha {3}
key[1] < node[5] é true, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando node[3], key[1] como parâmetros
node[3] não é null {2}, portanto passamos para a linha {3}
key[1] < node[3] é true {3}, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando null, key[1] como parâmetros. null foi passado como parâmetro porque node[3] é uma folha (ele não tem filhos, portanto o filho à esquerda será null)
node é null (linha {2}, o node a ser pesquisado nesse caso é null), portanto devolveremos false
Depois disso, as chamadas dos métodos serão desempilhadas e a execução terminará

Vamos fazer o mesmo exercício para pesquisar o valor 8, da seguinte maneira:

1. Chamamos o método searchNode passando root como parâmetro {1}. node[root[11]] não é null {2}, portanto passamos para a linha {3}

2. key[8] < node[11] é true {3}, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando node[7], key[8] como parâmetros

3. node[7] não é null {2}, portanto passamos para a linha {3}

4. key[8] < key[7] é false {3}, portanto passamos para a linha {5}

5. key[8] > node[7] é true {5}, portanto passamos para a linha {6} e chamamos o método searchNode novamente, passando node[9], key[8] como parâmetros

6. node[9] não é null {2}, portanto passamos para a linha {3}

7. key[8] < node[9] é true {3}, portanto passamos para a linha {4} e chamamos o método searchNode novamente, passando node[8], key[8] como parâmetros

8. node[8] não é null {2}, portanto passamos para a linha {3}

9. key[8] < node[8] é false {3}, portanto passamos para a linha {5}

10. key[8] > node[8] é false {5}, portanto passamos para a linha {7} de devolvemos true porque node[8] é a chave que estamos procurando

11. Depois disso, as chamadas dos métodos serão desempilhadas e a execução terminará

Removendo um nó

O próximo e último método que implementaremos para a nossa BST é o método remove

Esse é o método mais complexo da classe, vamos começar pelo método que estará disponível a partir de uma instância de uma árvore, assim:

remove(key) {
  this.root = this.removeNode(this.root, key) // {1}
}

Esse método recebe key que desejamos remover, e chama também removeNode, passando root e a key a ser removida como parâmetros {1}

Um aspecto muito importante a ser observado é que root recebe o valor devolvido pelo método removeNode, em breve vamos entender o porquê

A complexidade do método removeNode se deve aos diferentes cenários com os quais devemos lidar, além do fato de o método ser recursivo

Vamos observar a implementação de removeNode, exibida a seguir:

removeNode(node, key) {
  if (node === null) { // {2}
    return null
  }
  if (this.compareFn(key, node.key) === Compare.LESS_THAN) { // {3}
    node.left = this.removeNode(node.left, key) // {4}
    return node // {5}
  } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { // {6}
    node.right = this.removeNode(node.right, key) // {7}
    return node // {8}
  } else {
    // key é igual a node.item
    // caso 1
    if (node.left === null && node.right === null) { // {9}
      node = null // {10}
      return node // {11}
    }
    // caso 2
    if (node.left === null) { // {12}
      node = node.right // {13}
      return node // {14}
    } else if (node.right === null) { // {15}
      node = node.left // {16}
      return node // {17}
    }
    // caso 3
    const aux = this.minNode(node.right) // {18}
    node.key = aux.key // {19}
    node.right = this.removeNode(node.right, aux.key) // {20}
    return node // {21}
  }
}

Como ponto de parada, temos a linha {2}

Se o nó que estamos analisando for null, isso significa que key não está presente na árvore e, por esse movito, devolveremos null

Se o nó não for null, precisamos encontrar a key na árvore

Portanto, se a key que estamos procurando tiver um valor menor que o nó atual {3}, passaremos para o próximo nó da aresta à esquerda da árvore {4}

Se key for maior que o nó atual {6}, passaremos para o próximo nó na aresta à direta da árvore {7}, o que significa que analisaremos as subárvores

Se encontrarmos a chave que estamos procurando (key é igual a node.key), teremos três cenários distintos para tratar

Removendo uma folha

O primeiro cenário é aquele em que o nó é uma folha, sem filhos à esquerda nem à direita {9}

Nesse caso, tudo que temos a fazer é remover o nó atribuindo-lhe o valor null {9}

No entanto, sabemos que atribuir null ao nó não é suficiente, e devemos cuidar também das referências (ponteiros)

Nesse caso, o nó não tem nenhum filho, mas tem um nó pai

Devemos atribuir null em seu nó pai, e isso pode ser feito devolvendo null {11}

Como o nó já tem o valor null, a referência do pai ao nó receberá null também, e esse é o motivo pelo qual estamos devolvendo o valor de node no método removeNode

O nó pai sempre receberá o valor devolvido pelo método

Uma alternativa a essa abordagem seria passar o pai e o node como parâmetros do método

Se observarmos as primeiras linhas de código desse método, veremos que estamos atualizando as referências dos ponteiros da esquerda e da direita dos nós nas linhas {4} e {7}, e estamos também devolvendo o nó atualizado nas linhas {5} e {8}

Removendo um nó com um filho à esquerda ou à direita

Vamos agora analisar o segundo cenário, aquele em que um nó tem um filho à esquerda ou à direita

Nesse caso, devemos pular esse nó e fazer o ponteiro do pai apontar para o nó filho

Se o nó não tiver um filho à esquerda {12}, significa que ele tem um filho à direita, portanto modificaremos a referência do nó para o seu filho à direita {13} e devolveremos o nó atualizado {14}

Faremos o mesmo se o nó não tiver o filho à direita {15}; atualizaremos a referência do nó para o seu filho à esquerda {16} e devolveremos o valor atualizado {17}

Removendo um nó com dois filhos

Agora chegamos ao terceiro cenário, o mais complexo: aquele em que o nó que estamos tentando remover tem dois filhos: um à direita e outra à esquerda

Para remover um nó com dois filhos, há quatro passos que devem ser executados, da seguinte maneira:

1. Depois que o nó que queremos remover for encontrado, precisamos encontrar o nó mínimo da subárvore da aresta à sua direita (o seu sucessor, {18})

2. Em seguida, atualizamos o valor do nó com a chave do nó mínimo de sua subárvore à direita {19}. Com essa ação, estamos substituindo a chave do nó, o que significa que ele foi removido

3. No entanto, agora temos dois nós na árvore com a mesma chave, e isso não pode ocorrer. O que devemos fazer agora é remover o nó mínimo da subárvore à direita, pois ele foi transferido para o local em que estava o nó removido {20}

4. Por fim, devolvemos a referência ao nó atualizado para o seu pai {21}

E com isso, terminamos nossa implementação de uma Árvore Binária de Busca em Javascript :)