Artigo original: Data Structures 101: Binary Search Tree

Escrito por: Kevin Turney

Como combinar a eficiência de inserção de uma lista vinculada e a busca rápida de um array ordenado.

O que é uma árvore binária de busca?

Vamos começar com a terminologia básica para que possamos falar a mesma língua e investigar conceitos relativos. Primeiramente, quais princípios definem a árvore binária de busca (em inglês, Binary Search Tree ou BST)?

Observação: a partir daqui, usarei somente "BST" para facilitar.

Uma BST é considerada uma estrutura de dados feita a partir de nós (em inglês nodes), assim como as listas encadeadas (em inglês, linked lists – leia mais no artigo em inglês). Esses nós podem ser nulos ou ter referências (encadear) para outros nós. Esses "outros" nós são nós filhos, chamados de nó esquerdo e nó direito. Nós tem valores e esses valores determinam quando eles serão alocados dentro da BST.

Da mesma maneira que ocorre com uma lista vinculada, cada nó é referenciado somente por um outro nó, seu próprio pai, exceto o nó originário ou raiz. Podemos dizer, então, que cada nó em uma BST é uma BST própria, pois ao seguirmos a árvore, logo abaixo, nós alcançamos outro nó que tem outros dois filhos, um esquerdo e um direito. Independentemente de onde formos, esse nó vai ter um nó direito e um esquerdo como filhos e assim por diante.

1. O nó esquerdo é sempre menor que seu pai.

2. O nó direito é sempre maior que seu pai.

3. Uma BST é considerada balanceada se cada nível da árvore está completamente preenchido com exceção do último nível. Nele, a árvore é preenchida da esquerda pra direita.

4. Uma BST perfeita é aquela que é tanto cheia como completa (todos os nós filhos estão no mesmo nível e cada nó tem um nó esquerdo e um direito)

2rTqYlcrnWtICedt131tDft0CmkzZaViExJX

Aplicações úteis da BST

Quais são os exemplos reais das BSTs? Árvores são comumente usadas em buscas, lógicas de jogos, tarefas de preenchimento automático e gráficos.

Velocidade. Como mencionado anteriormente, a BST é uma estrutura ordenada de dados. Após a inserção, os nós são colocados de maneira ordenada. Essa ordem herdada faz as buscas serem mais rápidas. Similarmente a busca binária (com um array que é ordenado), cortamos pela metade o número de dados para ordenar a cada iteração. Por exemplo, suponha que estamos buscando por um nó com um pequeno valor. A cada iteração, continuamos movendo à esquerda em direção ao nó buscado. Isso elimina a metade dos valores maiores automaticamente!

Assim como um array, o dado é guardado por referência. Ao adicionar para a estrutura de dados, criamos um grupo na memória e o conectamos a ele. Fazer isso é mais rápido que criar um array com mais espaços e só então inserir o dado do menor array para o novo e maior.

Para resumir, inserção, exclusão e busca são habilidades de destaque para as BSTs.

Agora que entendemos os princípios, os benefícios e os componentes básicos de uma BST, vamos implementar uma em javascript.

A API para BST contém o seguinte: Insert, Contains, Get Min, Get Max, Remove Node, Check if Full, Is Balanced e os tipos de Busca — Depth First (preOrder, inOrder, postOrder), Breadth First Search e, por fim, Get Height. Essa é uma API bem grande, vamos olhar uma seção de cada vez.

Implementação

O construtor

A BST é feita de nós – e cada nó tem um valor.

function Node(value){  
	this.value = value;
    this.left = null;
    this.right = null;
}

O construtor da BST é criado a partir de um nó raiz.

function BinarySearchTree() {
	this.root = null;
}
let bst = new BST();
let node = new Node();
console.log(node, bst); // Node { value: undefined, left: null, right: null } BST { root: null }

Até agora, tudo vai bem.

Inserção (Insert)

BinarySearchTree.prototype.insert = function(value){
	let node = new Node(value);
	if(!this.root) this.root = node;
	else{    
    	let current = this.root;
        while(!!current){
        	if(node.value < current.value){
           		if(!current.left){
               		current.left = node;
                   	break;
               	}
        	   	current = current.left;
            }
            else if(node.value > current.value){
            	if(!current.right){
                	current.right = node;
                   	break;
               	}
                current = current.right;
            } 
            else {
            	break;
            }
     	}
     }
     return this;
};
let bst = new BST();
bst.insert(25); // BST { root: Node { value: 25, left: null, right: null } }

Vamos adicionar mais valores. 

bst.insert(40).insert(20).insert(9).insert(32).insert(15).insert(8).insert(27);
BST { root:  Node { value: 25, left: Node { value: 20, left: [Object], right: null }, right: Node { value: 40, left: [Object], right: null } } }

Para uma visualização melhor, basta só clicar aqui!

Vamos decifrar isso.

  1. Primeiramente, passamos um valor e criamos um nó
  2. Observar se tem um nó raiz. Senão, configurar esse nó recém-criado para apontar para o nó raiz
  3. Se existir um nó raiz, criamos uma variável declarada como "current" e configuramos esse valor para o nó raiz
  4. Se o nó for recém-criado, node.value, for menor que o nó raiz, movemos o nó para a esquerda
  5. Continuamos comparando esse node.value para os valores da esquerda.
  6. Se o valor for bem menor e alcançarmos um ponto onde não existirem mais nós esquerdos, colocaremos esse item aqui.
  7. Se o node.value é maior, repetiremos os mesmos passos acima exceto que em direção à direita.
  8. Precisamos inserir um break, porque não há um contador de passos para terminar o laço.

Contém (contains)

Essa abordagem é bem direta.

BinarySearchTree.prototype.contains = function(value){
	let current = this.root;
    while(current){
    	if(value === current.value) return true;
        if(value < current.value) current = current.left;
        if(value > current.value) current = current.right;
    }
    return false;
};

Obter o mínimo e o máximo (Get Min e Get Max).

Siga para a esquerda para achar o menor valor e para a direita para o maior valor.

BinarySearchTree.prototype.getMin = function(node){
	if(!node) node = this.root;
    while(node.left) {
    	node = node.left;
    }
    return node.value
};
BinarySearchTree.prototype.getMax = function(node){
	if(!node) node = this.root;
    while(node.right) {
    	node = node.right;
    }
    return node.value;
};

Remoção (removal)

Remover um nó é uma operação mais complicada, pois os nós tem que ser reordenados para que as propriedades da BST sejam mantidas. Existe um caso onde um nó tem apenas um filho e um caso onde o nó tem tanto o filho da direita como da esquerda. Usaremos a uma função para nos ajudar a fazer o trabalho pesado. 

BinarySearchTree.prototype.removeNode = function(node, value){
	if(!node){
    	return null;
    }
    if(value === node.value){ // sem filhos
    if(!node.left && !node.right) return null; // um filho e é o da direita
    if(!node.left) node.right;// um filho e é o da esquerda
    if(!node.right) node.left;  // dois filhos
    const temp = this.getMin(node.right);
    node.value = temp;
    node.right = this.removeNode(node.right, temp);
    return node;
    } else if(value < node.value) {
    	node.left = this.removeNode(node.left, value);
        return node;
   } else  {
      	node.right = this.removeNode(node.right, value);
        return node;
   }
};
BinarySearchTree.prototype.remove = function(value){
	this.root = this.removeNode(this.root, value);
};

Funciona assim…

Diferente de deleteMin e deleteMax, onde apenas cruzamos todo o caminho para a direita ou esquerda e pegamos o último valor, aqui, temos que retirar o nó e substituí-lo por algo. Essa solução foi desenvolvida em 1962 por T. Hibbard. Contamos com o caso onde podemos excluir um nó filho ou nenhum, esse é o caso mais fácil. Sem filhos, sem problemas. Se o filho estiver presente é só movê-lo para cima.

Entretanto, quando temos um nó para ser removido que tem dois filhos, qual deles fará a substituição? Certamente, não podemos mover o filho maior para baixo, então o que fazemos é trocá-lo pelo seu sucessor. Temos que buscar o menor filho à direita que é maior que o filho esquerdo.

  1. Crie uma variável temporária e guarde o menor nó na sua direita. Isso cumprirá o requisito de que a propriedade que tem o valor da esquerda, ainda assim, é menor e os valores da esquerda que ainda são maiores;
  2. Reinicialize o valor do nó essa variável temporária;
  3. Exclua o nó direito;
  4. Compare os valores na esquerda e na direita e determine qual será o valor atribuído.

Acho que uma imagem ilustrará isso melhor:

cEcyXZpZvRln6p7jzJq08lOJsORH6yA7Rd0T

Busca (search)

Existem dois tipo de busca: Depth First e Breadth First. Breadth First (busca por largura, em português) é simplesmente quando você para a cada nível ao descer pela árvore. Seria algo parecido com isso: começamos na raiz, então filho esquerdo e depois filho direito. Passamos para o próximo nível, filhos esquerdos e filhos direitos. Pense nisso como se estivesse se movendo horizontalmente. Empregamos, até diria que simulamos, uma fila para ajudar a ordenar o processo. Passamos a função, porque, muitas vezes, queremos operar em um valor.

BinarySearchTree.prototype.traverseBreadthFirst = function(fn) {
	let queue = [];
    queue.push(this.root);
    while(!!queue.length) {
    	let node = queue.shift();
        fn(node);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
}

A busca Depth First (busca por profundidade, em português) envolve seguir para baixo da BST de uma maneira específica, ou seja: preOrder, inOrder, ou postOrder (pré-ordem, na ordem ou pós-ordem, respectivamente). Explicarei as diferenças em breve.

Em termos de código, temos uma função básica, traverseDepthFirst, e passamos uma função e um método. Outra vez, a função implica que queremos fazer algo com o valor no percurso, enquanto o método é o tipo de busca que estamos tentando realizar. Na traverseDepthFirst, temos uma alternativa, a busca preOrder, pré-selecionada.

Agora, qual a diferença entre elas? Primeiro, enviamos a função inOrder. Deveria ser autoexplicativo, mas não é. Estamos querendo dizer em ordem de inserção, em ordem do maior para o menor, ou do menor para o maior? Eu quero apenas que você tenha isso em mente de antemão. Nesse caso, sim, quer dizer do menor para o maior.

preOrder pode ser pensado como Pai, Filho Esquerdo, Filho Direito.

postOrder, por outro lado, seria como Filho Esquerdo, Filho Direito, Pai.

BinarySearchTree.prototype.traverseDFS = function(fn, method){
	let current = this.root;
    if(!!method) this[method](current, fn);
    else this._preOrder(current, fn);
};
BinarySearchTree.prototype._inOrder = function(node, fn){
	if(!!node){
    	this._inOrder(node.left, fn);
	    if(!!fn) fn(node);
    	this._inOrder(node.right, fn);
    }
};
BinarySearchTree.prototype._preOrder = function(node, fn){
	if(node){ 
    	if(fn) fn(node);
    	this._preOrder(node.left, fn);
    	this._preOrder(node.right, fn);
    }
};
BinarySearchTree.prototype._postOrder = function(node, fn){
	if(!!node){ 
    		this._postOrder(node.left, fn);
    		this._postOrder(node.right, fn);
        	if(!!fn) fn(node);
    }
};

Checar se a BST está cheia

Lembre-se do que comentamos antes: uma BST está cheia se cada nó existente na árvore tiver ou Zero ou dois filhos.

// uma BST está cheia se cada nó tiver ou zero ou dois filhos (nenhum nó pode ter apenas um filho)
BinarySearchTree.prototype.checkIfFull = function(fn){
	let result = true;
    this.traverseBFS = (node) => {
    	if(!node.left && !node.right) result = false;
        else if(node.left && !node.right) result = false;
    }
    return result;
};

Obter a altura da BST

O que significa obter a altura de uma árvore? Por que é importante? Aqui é onde a Complexidade de Tempo (também conhecida como Big O) aparece. Operações básicas são proporcionais ao tamanho da árvore. Então, se lembrarmos do que foi dito antes, ao buscar por um valor específico, o número de operações que temos a fazer é reduzido a metade a cada etapa.

Isso significa que temos um pão e vamos cortá-lo a metade, depois dividir essa metade em outros dois pedaços e continuamos fazendo isso até termos exatamente o pedaço de pão que queremos.

Em ciência da computação, chamamos isso de O(log n). Começamos com algum tipo de tamanho de entrada e, com o tempo, o tamanho fica melhor (mais achatado). Uma busca linear direta é denotada como O(n). Conforme o tamanho da entrada aumenta, também aumenta o tempo para executar as operações. O(n), conceitualmente, é uma linha de 45° começando da origem zero em um gráfico se movendo para a direita. A escala horizontal representa o tamanho de uma entrada e a escala vertical representa o tempo levado para completá-la.

Tempo constante é O(1). Não importa o tamanho da entrada, seja grande ou pequena, a operação leva exatamente o mesmo tempo. Por exemplo, push() e pop() de um array possuem tempo constante, assim como obter o valor em uma HashTable.

Eu vou explicar mais sobre isso em um artigo futuro, mas já quis adiantar um pouco as coisas agora.

De volta à altura.

Temos uma função recursiva. Nosso caso base é: "se não temos um nó, então começamos em this.root". Isso implica que podemos começar em valores menores na árvore e obter árvores com subalturas.

Então se passamos em this.root para começar, recursivamente movemos para baixo e adicionamos funções que chamarão a pilha de execução (em inglês execution stack). Quando alcançamos o fundo, a pilha é preenchida e, então, a chamada é executada e comparamos as alturas da esquerda e da direita e incrementamos um.

BinarySearchTree.prototype._getHeights = function(node){
	if(!node) return -1;
    let left = this._getHeights(node.left);
    let right = this._getHeights(node.right);
    return Math.max(left, right) + 1;
};
BinarySearchTree.prototype.getHeight = function(node){
	if(!node) node = this.root;
    return this._getHeights(node);
};

Por último, Is Balanced (está balanceada)

O que estamos fazendo aqui é observar se a árvore está preenchida em cada nível, e se  no último nível ela está preenchida da esquerda para a direita.

BinarySearchTree.prototype._isBalanced = function(node){
	if(!node) return true;
    let heightLeft = this._getHeights(node.left);
    let heightRight = this._getHeights(node.right);
    let diff = Math.abs(heightLeft — heightRight);
    if(diff > 1) return false;
    else return this._isBalanced(node.left) &&    this._isBalanced(node.right);
};
BinarySearchTree.prototype.isBalanced = function(node){
	if(!node) node = this.root;
    return this._isBalanced(node);
};

Imprimir a árvore (print)

Use isso para visualizar todos os métodos que você vê, especialmente travessias depth first e breadth first.

BinarySearchTree.prototype.print = function() {
	if(!this.root) {
    	return console.log('Nó raiz não encontrado');
    }
    let newline = new Node('|');
    let queue = [this.root, newline];
    let string = ''; 
    while(queue.length) {
    	let node = queue.shift();
        string += node.value.toString() + ' ';
        if(node === newline && queue.length) queue.push(newline);
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
     }
     console.log(string.slice(0, -2).trim());
};

Nosso amigo, o console.log! Sinta-se livre para brincar com ele e experimentar. 

const binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(5);
binarySearchTree.insert(3);
binarySearchTree.insert(7);
binarySearchTree.insert(2);
binarySearchTree.insert(4);
binarySearchTree.insert(4);
binarySearchTree.insert(6);
binarySearchTree.insert(8);
binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8
binarySearchTree.contains(4);
//binarySearchTree.printByLevel(); // => 5 \n 3 7 \n 2 4 6 8
console.log('--- DFS inOrder');
binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_inOrder'); // => 2 3 4 5 6 7 8
console.log('--- DFS preOrder');
binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_preOrder'); // => 5 3 2 4 7 6 8
console.log('--- DFS postOrder');
binarySearchTree.traverseDFS(function(node) {
	console.log(node.value);
}, '_postOrder'); // => 2 4 3 6 8 7 5
console.log('--- BFS');
binarySearchTree.traverseBFS(function(node) {
	console.log(node.value);
}); // => 5 3 7 2 4 6 8
console.log('min é 2:', binarySearchTree.getMin()); // => 2
console.log('máx é 8:', binarySearchTree.getMax()); // => 8
console.log('árvore contém 3 é true:', binarySearchTree.contains(3)); // => true
console.log('árvore contém 9 é false:', binarySearchTree.contains(9)); // => false
// console.log('altura da árvore é 2:', binarySearchTree.getHeight()); // => 2
console.log('árvore balanceada é true:', binarySearchTree.isBalanced(),'line 220'); // => true
binarySearchTree. remove(11); // remove o nó inexistente
binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8
binarySearchTree.remove(5); // remove 5 e 6 sobe
binarySearchTree.print(); // => 6 | 3 7 | 2 4 8
console.log(binarySearchTree.checkIfFull(), 'deve ser verdadeiro');
var fullBSTree = new BinarySearchTree(10);
fullBSTree.insert(5).insert(20).insert(15).insert(21).insert(16).insert(13);
console.log(fullBSTree.checkIfFull(), 'should be true');
binarySearchTree.remove(7); // remove 7 e 8 sobe
binarySearchTree.print(); // => 6 | 3 8 | 2 4
binarySearchTree.remove(8); // remove 8 e a árvore fica desbalanceada
binarySearchTree.print(); // => 6 | 3 | 2 4
console.log('árvore balanceada é false:', binarySearchTree.isBalanced()); // => true
console.log(binarySearchTree.getHeight(),'altura é 2')
binarySearchTree.remove(4);
binarySearchTree.remove(2);
binarySearchTree.remove(3);
binarySearchTree.remove(6);
binarySearchTree.print(); // => 'Não foi encontrado o nó raiz'
//binarySearchTree.printByLevel(); // => 'Não foi encontrado o nó raiz'
console.log('altura da árvore é -1:', binarySearchTree.getHeight()); // => -1
console.log('árvore balanceada é true:', binarySearchTree.isBalanced()); // => true
console.log('---');
binarySearchTree.insert(10);
console.log('altura da árvore é 0:', binarySearchTree.getHeight()); // => 0
console.log('ávroe balanceada é true:', binarySearchTree.isBalanced()); // => true
binarySearchTree.insert(6);
binarySearchTree.insert(14);
binarySearchTree.insert(4);
binarySearchTree.insert(8);
binarySearchTree.insert(12);
binarySearchTree.insert(16);
binarySearchTree.insert(3);
binarySearchTree.insert(5);
binarySearchTree.insert(7);
binarySearchTree.insert(9);
binarySearchTree.insert(11);
binarySearchTree.insert(13);
binarySearchTree.insert(15);
binarySearchTree.insert(17);
binarySearchTree.print(); // => 10 | 6 14 | 4 8 12 16 | 3 5 7 9 11 13 15 17
binarySearchTree.remove(10); // remove 10 e 11 sobe
binarySearchTree.print(); // => 11 | 6 14 | 4 8 12 16 | 3 5 7 9 x 13 15 17
binarySearchTree.remove(12); // remove 12 e 13 sobe
binarySearchTree.print(); // => 11 | 6 14 | 4 8 13 16 | 3 5 7 9 x x 15 17
console.log('árvore balanceada é true:', binarySearchTree.isBalanced()); // => true
//console.log('árvore balanceada otimizada é true:', binarySearchTree.isBalancedOptimized()); // => true
binarySearchTree.remove(13); // remove 13 e 13 não tem filhos - nada acontece
binarySearchTree.print(); // => 11 | 6 14 | 4 8 x 16 | 3 5 7 9 x x 15 17
console.log('árvore balanceada é false:', binarySearchTree.isBalanced()); // => false

Complexidade de tempo

1. Inserção O(log n)
2. Remoção O(log n)
3. Busca O(log n)

Uau, isso foi realmente muita informação. Espero que as explicações tenham sido claras e introdutórias o máximo possível. Outra vez, escrever me ajuda a solidificar conceitos e, como dizia Richard Feynman: "Quando uma pessoa ensina, duas pessoas aprendem."

Recursos

Estes são recursos ótimos para visualização (em inglês):

Versão da Wikipédia em português: Árvore binária de busca