Binary Trees

O que é uma Binary Tree

Uma binary tree é uma tree onde todo node tem no máximo dois children. Essa é a adição inteira ao artigo anterior — um número, mudado de "qualquer" para "dois".

Ela compra mais do que parece. Os dois children ganham nome, left e right, e porque têm nome deixam de ser intercambiáveis: um node só com child da esquerda é uma tree diferente de um node só com child da direita, mesmo os dois tendo um child. Essa assimetria é sobre o que todo artigo seguinte desta série constrói.

O problema que uma Tree genérica não resolvia

A tree genérica do artigo anterior guarda qualquer hierarquia, e essa flexibilidade lhe custa duas coisas.

Você não consegue raciocinar sobre a height dela. Uma tree com 100 nodes pode ter height 1 — uma root com 99 children — ou height 99. Saber a contagem de nodes não te diz nada sobre o quão longe você pode ter que caminhar, e a height é o custo de toda operação. Limite os children a dois e os dois números ficam ligados: n nodes numa binary tree arrumada significa height por volta de log₂ n, e essa relação é a razão inteira de o resto desta série existir.

Você não consegue colocá-la num array. Um node com número variável de children precisa de um slice por node, o que significa uma alocação separada no heap por node e pointer chasing para alcançar qualquer um deles. Fixe a contagem em dois e as posições ficam calculáveis — o índice de um child é aritmética sobre o do seu parent, então a tree inteira colapsa num único bloco plano de memória, sem pointer nenhum. Esse truque é o que faz o heap do último artigo desta série ser rápido, e ele só funciona por causa do dois.

Então o limite de dois children não é uma restrição que a estrutura sofre. É o que transforma uma tree de um container em algo que você consegue prever.

As formas que uma Binary Tree pode ter

A maior parte do vocabulário em volta de binary trees descreve a forma delas, e vale ser preciso porque os termos se sobrepõem de um jeito que confunde. Toda definição abaixo é sobre a mesma pergunta — onde os nodes podem estar faltando.

Full

Uma binary tree full é uma onde todo node tem zero ou dois children. Nunca exatamente um.

Note que isso não diz nada sobre onde os leaves ficam. Uma tree full pode ser absurdamente torta; ela só não pode ter um node com um único child solitário.

Complete

Uma binary tree complete tem todo level cheio exceto possivelmente o último, e o último level enche a partir da esquerda, sem buracos.

Essa é a forma que mais importa na prática, porque é exatamente a forma que cabe num array sem nenhum slot desperdiçado. Guarde esse pensamento até a representação em array mais abaixo.

Perfect

Uma binary tree perfect tem todo level completamente cheio. Não existe buraco em lugar nenhum, o que força uma contagem de nodes bem específica: uma tree perfect de height h tem exatamente 2^(h+1) − 1 nodes.

Perfect é a mais forte das três: uma tree perfect é automaticamente complete e automaticamente full. O contrário falha nas duas direções, o que a próxima seção deixa concreto.

Balanced, e unbalanced

Balanced é a diferente, porque é uma condição sobre height, não sobre onde os nodes ficam. Uma tree é balanced quando, para todo node, suas duas subtrees diferem em height por no máximo um.

Essa figura merece um segundo olhar, porque ela mata a intuição errada mais comum sobre esse vocabulário: full não significa balanced. Cada node ali tem zero children ou dois, e a tree continua visivelmente torta. Regras de forma e regras de height medem coisas diferentes.

Unbalanced não é um tipo de tree que você constrói. É o que você obtém quando a condição de balanced falha — e, como os próximos dois artigos mostram, é o que acontece com uma search tree por acidente quando os dados chegam em ordem.

Degenerate

Uma binary tree degenerate tem exatamente um child por internal node. Todo level guarda um node.

Este é o pior caso, e não é hipotético. Tem height n − 1 em vez de log₂ n, então toda operação que devia ser logarítmica é linear, e os campos left/right são overhead puro sobre uma linked list comum.

Como as formas se sobrepõem

Os cinco termos não são uma escada, e desenhá-los como uma é onde a maioria das explicações erra. As relações de verdade:

• Perfect implica complete, full e balanced. As três, sempre. É a forma mais estrita.
• Complete implica balanced, mas não diz nada sobre full — a figura complete acima tem um node com um child.
• Full não diz nada sobre complete, e nada sobre balanced. A figura full acima tem um buraco no meio; a figura unbalanced acima é full e torta.
• Full e complete são independentes nas duas direções. Existem trees que são full e não complete, e trees que são complete e não full. Nenhuma implica a outra.
• Degenerate implica unbalanced, assim que a tree fica alta o suficiente para ter uma subtree torta.

Height contra número de nodes

Tudo acima é andaime para um número só. A height de uma binary tree é o que toda operação custa, porque o caminho root-até-leaf mais longo é o máximo de trabalho que uma busca pode ser forçada a fazer.

Para uma contagem n de nodes, a height depende inteiramente da forma, e a diferença entre o melhor e o pior caso é enorme:

É o mesmo milhão de nodes, e uma caminhada de 19 passos contra uma de um milhão. Não é fator constante — é diferença na forma do crescimento.

A razão de o caso bom ser logarítmico vale ser dita direto, porque aparece em todo artigo restante. Cada level de uma binary tree guarda no máximo o dobro do level acima: 1, 2, 4, 8, 16. Então uma tree de height h guarda no máximo 2^(h+1) − 1 nodes, e lendo isso ao contrário, n nodes precisam de height pelo menos log₂ n. Dobrar seus dados adiciona um level.

Representando uma Binary Tree em memória

Dois children, duas representações.

Nodes encadeados

A direta: um struct com um valor e dois pointers. Este é o node de linked list de antes na série com um segundo pointer parafusado, e tudo nele deve parecer familiar.

O truque que vale roubar ali é o receiver nil. Em Go um método pode ser chamado num pointer nil, então definir Height() para retornar -1 na tree vazia significa que nenhum caller verifica nil — o caso base mora num lugar só, em vez de em cada ponto de chamada. É a coisa mais próxima de almoço grátis que código de tree tem.

A representação em array

A outra representação descarta os pointers inteiramente. Numere os nodes level por level, esquerda para direita, começando em 0, e guarde-os num slice plano nesses índices. As relações viram aritmética:

É o esquema inteiro. Sem campo Left, sem campo Right, sem alocação por node — um bloco contíguo, e o endereço de um child calculado a partir do do seu parent com um shift e uma soma.

O ganho é real: sem pointer chasing, sem alocação por node, e siblings ficam lado a lado na memória, então percorrer um level é uma leitura sequencial para a qual o cache da CPU foi feito. Isso é o oposto do pointer chasing hostil ao cache sobre o qual o artigo de linked lists avisou.

O porém é que os índices são atribuídos por posição, não por ordem de inserção — então um node ausente ainda consome seu slot. Isso faz o custo desta representação depender inteiramente da forma:

• Numa tree complete é grátis. Os slots preenchidos são exatamente 0 .. n−1, contíguos, sem nada desperdiçado. Isso não é coincidência, e é por isso que "complete" ganhou nome próprio.
• Numa tree degenerate é catastrófico. Height n − 1 significa que o índice do node mais profundo fica por volta de 2^n, então 21 nodes numa cadeia inclinada à direita precisam de mais de dois milhões de slots.

Teste você mesmo

As cinco formas são mais fáceis de sentir do que de memorizar. Monte uma tree clicando, e observe as classificações se redecidirem — depois clique em qualquer forma que ela não satisfaz para ver exatamente qual node a descartou.

Duas coisas que valem tentar: carregue full e então verifique se ela é complete, e carregue complete e verifique se ela é full. Nenhuma implica a outra, e fazer isso na mão convence mais que o parágrafo acima.

Operações comuns e seus custos

As mesmas operações, na mesma contagem de nodes, na melhor e na pior forma — que é o artigo inteiro numa tabela:

Leia a primeira linha e a última juntas. Forma não muda o que uma binary tree consegue fazer — muda o que ela custa, por um fator sem limite.

E note o que continua O(n) nas duas colunas: achar um valor. Nada neste artigo te diz para que lado ir num node, então uma busca ainda tem que considerar tudo. Esse buraco é exatamente o que o próximo artigo fecha.

Binary Trees no mundo real

Expression trees e parse trees

Todo operador binário é um node com dois children — seus operandos. 2 * (3 + 4) é um node * cujos children são 2 e um node +. Compiladores e calculadoras constroem essas, e avaliar uma é questão de resolver os children antes dos parents. A forma de dois children não é escolha de design aqui; ela decorre de os operadores serem binários.

Codificação de Huffman

A compressão atrás do ZIP e do JPEG constrói uma binary tree onde todo galho da esquerda é um bit 0 e todo da direita um 1. O código de um caractere é seu caminho desde a root, então caracteres frequentes ficam rasos e ganham códigos curtos. A tree é a tabela de códigos.

Heaps e priority queues

A representação em array acima, usada em força total. Schedulers, event loops e timers são quase sempre apoiados num. Isso ganha artigo próprio no fim da série.

Binary space partitioning

Jogos e renderizadores dividem o espaço pela metade repetidamente — cada node é uma região, seus dois children as metades. O Doom notoriamente usou uma BSP tree para decidir ordem de desenho. Mesma ideia em detecção de colisão e ray tracing.

Merkle trees

Commits do git, blocos de blockchain e o rsync fazem hash de pares de nodes para cima, então um único hash de root certifica um dataset inteiro e uma divergência pode ser localizada em log n comparações. Aqui a tree codifica verificação em vez de ordem — um uso da forma que não tem nada a ver com busca.

Quando Binary Trees deixam a desejar

Dois children costuma ser o número errado. Um diretório de filesystem guarda muitas entradas, um elemento do DOM envolve muitos children. Forçar isso numa binary tree significa o truque de first-child/next-sibling do artigo anterior ou muito faz-de-conta. Use a forma que casa com seus dados, não a que tem a matemática mais bonita.

Nada mantém a tree baixa. Toda propriedade boa deste artigo assumiu uma forma arrumada, e a definição não garante nenhuma delas. Esse é o maior porém, e os próximos dois artigos são sobre ele: primeiro vendo uma search tree degenerar a partir de entrada banal, depois consertando.

A representação em array só compensa quando complete. É o layout mais rápido disponível e uma armadilha em qualquer outro lugar. Usá-la numa tree cuja forma você não controla transforma otimização de memória em desperdício exponencial.

Ainda sem ordenação. Uma binary tree restringe onde os nodes podem estar, não quais valores vão onde. Busca é O(n) na melhor forma e na pior. A estrutura agora é previsível, mas ainda não é útil para lookup.

Pointer chasing, a menos que você tenha achatado. Na representação encadeada cada node é sua própria alocação, então percorrer é uma sequência de possíveis cache misses — o mesmo custo que o artigo de linked lists descreveu, e a razão de a representação em array existir.

Resumo

Binary trees pegam a tree genérica e limitam os children a dois, o que transforma um container em algo previsível:

• No máximo dois children, e eles têm nome — left e right não são intercambiáveis, e essa assimetria é sobre o que os artigos seguintes constroem
• Full, complete, perfect, balanced, degenerate — full e complete restringem coisas diferentes e não implicam uma à outra; perfect implica as três
• Balanced é regra de height, não de forma — uma tree full pode ser muito unbalanced, que é a intuição que a maioria erra
• Height é o custo — log₂ n numa tree arrumada contra n − 1 numa degenerate, que são 19 passos contra um milhão na mesma contagem de nodes
• Uma tree complete cabe exatamente num array — 2i+1, 2i+2, (i−1)/2, sem pointers e sem desperdício, e desperdício exponencial em qualquer outra forma
• Busca ainda é O(n) — a forma está restringida, os valores não

O insight central é que o limite de dois children compra previsibilidade, não velocidade. Limitar os children é o que faz a height ser função da contagem de nodes e faz o endereço de um child ser calculável a partir do do parent — mas nenhuma dessas coisas te diz onde um valor mora. Uma binary tree é uma forma sobre a qual você consegue raciocinar, guardando dados que você ainda tem que buscar exaustivamente.

O próximo artigo adiciona a única regra que resolve isso. Decida que tudo na subtree esquerda de um node é menor que ele e tudo na direita é maior, e de repente cada comparação num node descarta metade da tree restante — o jogo de vinte perguntas do começo deste artigo, transformado em estrutura de dados.