Trees

O que é uma Tree

Uma tree é um conjunto de nodes onde todo node tem exatamente um parent — exceto um, a root, que não tem nenhum. Essa única restrição é a definição inteira. Toda outra palavra deste artigo é consequência dela.

Vale notar o que isso exclui. Nenhum node pode ter dois parents, então nada é alcançável por dois caminhos diferentes. Nenhum node pode ser ancestral de si mesmo, então seguir a estrutura para baixo sempre termina. Uma tree é o que você obtém quando pega a ideia de nodes apontando para nodes e proíbe que ela volte para trás.

Trees são desenhadas de cabeça para baixo, root no topo, e ninguém nunca corrigiu isso. Leia "para baixo" como "se afastando da root" e o vocabulário para de brigar com a figura.

O problema que estruturas anteriores não resolviam

Toda estrutura até aqui armazena valores em algum arranjo. O que nenhuma delas consegue armazenar é hierarquia — o fato de que uma coisa contém, possui ou precede várias outras.

Arrays te dão posição. Posição é uma relação, mas plana: o elemento 4 fica ao lado do elemento 5 e isso é tudo que pode significar. Não existe forma de o elemento 4 conter os elementos 7 a 12.

Linked lists te dão sucessão — um node apontando para o node seguinte. Essa é genuinamente uma relação entre nodes, e é a forma certa para este artigo construir em cima. Mas é exatamente um next por node, então uma linked list só consegue expressar uma linha.

Hash tables te dão key → value em O(1). Rápido, e cego a hierarquia: o propósito inteiro de uma hash function é espalhar keys, o que destrói qualquer relação entre elas.

O que falta nas três é one-to-many. Um diretório guarda muitos arquivos. Um elemento HTML envolve muitos elementos. Um gerente tem vários subordinados, cada um podendo ter subordinados próprios. Troque o único next da linked list por uma lista de children e você tem uma tree — que é por que este é o artigo que vem depois daquele.

O vocabulário

Trees carregam mais terminologia que qualquer estrutura até aqui, e a maioria dos leitores encontra isso como um muro de definições. É menor do que parece: todo termo abaixo nomeia uma posição na mesma figura, então é mais fácil manter uma tree na tela e apontar para ela.

Root, parent, child, sibling, leaf

• Root — o único node sem parent. Uma tree tem exatamente uma, e ela é sua única entrada.
• Parent e child — as duas pontas de um edge. Todo node exceto a root tem exatamente um parent, e qualquer número de children.
• Siblings — nodes que compartilham um parent. Note que não existe edge entre eles; siblings são relacionados por onde estão, não por um pointer.
• Leaf — um node sem children. É onde a estrutura para.
• Internal node — um node com pelo menos um child. Todo node é leaf ou internal, nunca os dois.
• Ancestor e descendant — as versões transitivas. O parent do seu parent é um ancestor; todo node abaixo de você é um descendant.

Subtree

Uma subtree é qualquer node junto com todos os seus descendants. A tree da figura acima tem uma subtree com root em b contendo b, e e f.

Essa é a ideia mais útil do vocabulário, porque é o que faz a recursão funcionar. "Some todos os valores desta tree" não é um problema que você resolve com um loop; é valor + soma da subtree de cada child, e cada uma dessas é o mesmo problema em algo menor. Uma vez que você vê subtrees, a maior parte do código de tree se escreve sozinha.

Uma forest é um conjunto de trees sem uma root as unindo — o que sobra se você deletar uma root e manter seus children.

Depth e height

Esses dois são confundidos constantemente, e a confusão vale uma figura. Ambos contam edges; eles contam de pontas opostas.

Depth é uma propriedade de um node: quantos edges existem entre ele e a root. A root tem depth 0.

Height é uma propriedade de uma subtree: o número de edges no caminho mais longo daquele node até um leaf. Todo leaf tem height 0, e a height de uma tree significa a height da sua root.

Um level é o conjunto de todos os nodes num mesmo depth. O level 0 é a root sozinha.

Height é o número que importa para performance, e é o número sobre o qual todo artigo seguinte desta série realmente fala. Depth te diz onde um node está. Height te diz o pior caso para alcançar um — porque o caminho root-até-leaf mais longo é quanto trabalho uma busca pode ser forçada a fazer.

Uma tree tem exatamente V − 1 edges

Conte os nodes de qualquer tree, subtraia um, e você tem o número de edges. A figura acima tem sete nodes e seis edges.

A razão é a definição, reescrita: todo node tem exatamente um parent exceto a root, e todo edge é precisamente o link de um node com seu parent. Então edges e nodes não-root são a mesma coleção contada de dois jeitos.

Essa é uma invariante genuinamente útil, não curiosidade. Ela significa que uma tree é a estrutura mais sparse que ainda consegue conectar tudo — remova qualquer edge e ela cai em duas partes, adicione qualquer edge e você cria um cycle e ela deixa de ser uma tree.

Representando uma Tree em memória

A definição diz que cada node tem um valor e alguns children. A única decisão real é como armazenar "alguns children".

A abordagem direta dá a todo node um slice de pointers para children. Ela lê exatamente como a definição, e é o que você deve usar por padrão.

Note que Height retorna 0 para um leaf sem nenhum caso especial para isso: o loop simplesmente não roda. Código de tree é cheio de casos base que chegam de graça assim, que é a maior parte da razão de ele ficar curto.

First child, next sibling

Existe uma segunda representação que vale conhecer, por aparecer em sistemas reais e pelo que ela é feita.

Em vez de um slice por node, dê a todo node dois pointers: um para seu first child, e um para seu next sibling.

Isso é uma linked list escondida dentro de uma tree. Os children de um node não são armazenados como coleção nenhuma — são uma cadeia, e o parent guarda só a head dela. Percorrê-los é o loop de traversal do artigo de linked lists, sem mudança:

O ganho é um tamanho de node fixo. Todo node tem exatamente a largura de dois pointers, não importa quantos children tenha, sem header de slice e sem realocação quando um child é anexado — que é por que isso aparece em lugares com memória restrita e em compiladores, onde a contagem de nodes é enorme e a tree é construída uma vez e depois só lida.

O custo é que as operações baratas da representação com slice se tornam lineares. "Quantos children este node tem" é uma caminhada. "Me dê o terceiro child" é uma caminhada. Você trocou acesso indexado por um node menor e mais estável — o mesmo trade que o artigo de linked lists fez, aparecendo um nível acima.

Teste você mesmo

Você viu o vocabulário e as duas representações — agora monte algumas trees e observe duas coisas se mantendo, não importa o que você faça. Toda tree tem exatamente um edge menos do que tem nodes, e nenhum node consegue aparecer sem seu parent, porque não haveria onde prendê-lo.

Operações comuns e seus custos

Para a representação com slice, onde n é o número de nodes e h a height:

O padrão é que edições estruturais são O(1) e perguntas sobre conteúdo são O(n). Isso deve parecer familiar — é o perfil da linked list, porque uma tree é construída do mesmo jeito. E é a razão dos próximos artigos existirem: uma tree simples não te dá jeito nenhum de buscar mais rápido que verificando tudo. Todo artigo restante desta série é sobre adicionar uma regra à tree que transforma busca O(n) em O(h), e depois garantir que h fique pequeno.

Trees no mundo real

Filesystems

O exemplo que não precisa de tradução. Diretórios são internal nodes, arquivos são leaves, e / é a root. Note onde a realidade dobra as regras: um hard link dá a um arquivo dois parents, e um symlink pode apontar para qualquer lugar, inclusive para cima. Ambos são fugas deliberadas da condição de tree, e ambos são por que o find precisa se preocupar com loops.

O DOM

Um documento HTML é uma tree, e o browser te entrega ela como uma. parentNode, childNodes, firstChild — o vocabulário deste artigo é a API. Selectors CSS são queries sobre essa tree, e a razão de .a .b ser mais lento que .b é que ele precisa caminhar por ancestors.

Configuração e troca de dados

JSON, YAML e TOML são todos serializações de tree. Um objeto é um internal node, um escalar é um leaf, e o aninhamento é o edge parent-child. É por isso que todo formato de configuração tem uma sintaxe de caminho inequívoca — .spec.containers[0].image é uma rota descendo da root.

Compiladores

Código-fonte é parseado numa abstract syntax tree, onde o operador de uma expressão é o parent dos seus operandos. 2 * (3 + 4) se torna um node * cujos children são 2 e um node +. Avaliá-la é uma caminhada post-order, que o artigo de traversals cobre diretamente.

Hierarquias organizacionais e de categorias

Organogramas, taxonomias, categorias de produto, threads de comentários, tabelas de roteamento. Sempre que uma coisa pertence a exatamente uma coisa maior, o modelo natural é uma tree — e a representação natural em banco de dados é uma coluna parent_id, que é a representação por parent pointer armazenada numa tabela.

Quando Trees deixam a desejar

Um parent só é uma restrição real. É a fonte de tudo que é conveniente em trees, e é um limite de modelagem. Tags, conexões sociais, relações many-to-many de qualquer tipo — nenhuma se encaixa, e forçá-las numa tree significa duplicar nodes ou inventar uma segunda estrutura ao lado.

Height não tem garantia de ser pequena. Nada na definição diz que uma tree é frondosa. Uma tree onde todo node tem exatamente um child é uma linked list vestindo outro tipo, com height n − 1 em vez de log n, e toda operação que devia ser barata é linear. Esse modo de falha é a razão inteira do artigo de balanced trees existir.

Depth custa stack. Código recursivo de tree é curto porque a call stack faz a contabilidade, mas essa stack é finita. Uma tree profunda o suficiente vai transbordá-la, e "profunda o suficiente" chega mais cedo do que você gostaria em entrada degenerada — que é por que o artigo de traversals gasta tempo nas versões iterativas.

Pointer chasing é hostil ao cache. Nodes são alocações separadas no heap, então percorrer uma tree é uma sequência de possíveis cache misses, exatamente como numa linked list. É por isso que trees críticas em performance são achatadas em arrays, um truque que o próximo artigo introduz e que o artigo de heap nunca abandona.

Algo mais plano costuma servir. Se a única pergunta que você faz é "qual o parent deste node", uma hash table de child → parent responde em O(1) e não precisa de nada disso. Se você só itera tudo em ordem, um slice é mais rápido. Use uma tree quando a hierarquia em si é o que você precisa consultar — não meramente porque seus dados são aninhados.

Resumo

Trees são a primeira estrutura desta série que não é uma linha:

• Um parent por node, uma root, sem cycles — a definição inteira, e toda outra propriedade decorre dela
• Depth é onde um node está, height é o quão longe ele pode te forçar a caminhar — height é o número que governa performance
• V − 1 edges, sempre — a estrutura mais sparse que ainda conecta tudo
• Uma subtree é uma tree — que é por que quase todo código de tree é recursivo, e por que ele é tão curto
• Children como slice, ou first-child/next-sibling — acesso indexado contra tamanho de node fixo, o mesmo trade que linked lists fizeram
• Edições estruturais são O(1), perguntas de conteúdo são O(n) — uma tree simples não te dá jeito de buscar mais rápido que verificando tudo

O insight central é que trees adicionam hierarquia mas ainda não ordem. Nada aqui te diz onde procurar um valor, então achar um ainda significa visitar todo node — uma tree por si só te compra estrutura, não velocidade.

É sobre isso que o resto desta série trata. Restrinja uma tree a dois children e a forma se torna algo sobre o qual você pode raciocinar aritmeticamente; adicione uma regra sobre qual child um valor pertence e a busca cai para a height da tree; depois mantenha a height pequena e isso se torna uma garantia. O próximo artigo dá o primeiro desses passos.