O que é uma árvore: raiz, nós e folhas

Sair da linha reta

Pilha, fila e lista têm algo em comum: são lineares. Cada elemento tem no máximo um antes e um depois, como pessoas numa fila de banco. Isso resolve muita coisa, mas não representa bem uma hierarquia. Pense na estrutura de pastas do seu computador. Uma pasta pode conter várias outras, e cada uma dessas pode conter mais. Isso não é uma fila, é uma ramificação: de um ponto saem vários caminhos, e de cada um saem mais. A estrutura que captura essa forma é a árvore, a primeira estrutura não linear do curso.

A árvore da computação é desenhada de cabeça para baixo em relação à da natureza: a raiz fica no topo e os ramos descem. No topo está a raiz, o único nó sem pai, o ponto de partida de tudo. Dela saem ligações para os filhos, que são outros nós. Cada filho pode ter os seus próprios filhos, e assim a árvore desce nível a nível. Os nós que ficam nas pontas, sem nenhum filho, são as folhas. Um mesmo nó, no meio do caminho, é filho de quem está acima e pai de quem está abaixo. Essa relação de pai e filho, repetida, é o que forma a hierarquia.

Árvores que você já usa

O melhor jeito de fixar o conceito é ver as árvores escondidas na sua rotina. O sistema de pastas é o exemplo mais direto: a pasta principal é a raiz, cada pasta dentro dela é um filho, e os arquivos soltos, que não guardam nada dentro, são folhas. O organograma de uma empresa é outra árvore: o cargo do topo é a raiz, cada pessoa responde a um único superior (o pai) e pode ter várias pessoas sob sua responsabilidade (os filhos). A árvore genealógica, o índice de um livro com capítulos e seções, o cardápio de um site com categorias e subcategorias, todos têm a mesma forma. Onde houver uma relação de contém ou de reporta a, provavelmente há uma árvore.

Por que a forma da árvore importa

A altura de uma árvore não é um detalhe estético; ela decide a velocidade de muitas operações. Imagine guardar mil nomes. Se a árvore for alta e fina, com cada nó tendo um filho só, ela vira praticamente uma lista, e achar um nome exige descer nó por nó. Se for baixa e larga, bem distribuída, o caminho da raiz até qualquer folha é curto, e chegar a qualquer nome leva poucos passos. Por isso, quando se usa árvore para busca, o objetivo é mantê-la equilibrada, ou seja, com a menor altura possível para a quantidade de nós. Guarde essa ideia: quanto mais rasa a árvore, mais rápido o acesso. As próximas aulas mostram como uma árvore bem organizada transforma a busca.