Mais sobre o poder das árvores: Uma introdução conceitual

Ok… este artigo é básico e apenas conceitual, mas ai vai: Árvores binárias são mecanismos excelentes para diminuir o esforço computacional na resolução de certos problemas… Isso acontece porque, através de árvores, um grande conjunto dos dados contidos na árvore são ignorados numa pesquisa. Eis um exemplo:

tree

Cada “bolinha” é um nó na estrutura de uma árvore. O nó ‘F’ é o nó raiz que, estranhamente, está no topo da árvore (a raiz de uma planta geralmente está voltada em direção ao solo, para baixo, mas essa notação é feita assim apenas para facilitar o entendimento!). Os nós à esquerda de ‘F’ são “menores” que ele, e os à direita, “maiores”… Assim é montada nossa árvore.

Suponha que você queira verificar se o dado ‘C’ está na “lista” (na árvore!)… A primeira coisa que você perceberá é que todos os nós “menores” que ‘F’ estão à esquerda… Isso significa que você não precisa se preocupar com os nós ‘G’, ‘I’ e ‘H’, do lado direito, ignorando-os… Para fazer isso, seu foco sai do nó ‘F’ e concentra-se na “sub árvore” onde o novo nó raiz é o ‘B’. A coisa continua, porque com toda certeza, o nó ‘C’ deverá estar à direita do nó ‘B’, fazendo-nos ignorar o nó à esquerda ‘A’ e tornando o nó ‘D’ o novo nó raiz da nossa pesquisa. Continuamos procurando à esquerda de ‘D’ pelo nó ‘C’ e, finalmente, o encontramos, ignorando o nó à direita de ‘D’.

Não é difícil perceber que a quantidade de comparações é proporcional a n_{steps} \approx lg N . Se tivéssemos uma árvore com 1000 nós, para achar um deles precisaríamos pesquisar, aproximadamente, apenas 10!

Árvores têm filhotes de árvores (sub árvores):

Reparou que falei sobre “sub árvores” antes? Cada nó é raiz de uma árvore menor, que compõe a árvore maior. Mesmo os nós no nível mais inferior… Esses são os nós “folha”, que não possuem nós filhos.

A estrutura de cada um desses nós, em C, poderia ser definida como:

struct node_s {
  char key;
  struct node_s *left, *right;
};

Uma maneira de determinar se um nó é “folha” de uma árvore é verificar se os ponteiros leftright são ou não nulos. Outra, que pode ser mais conveniente, é usar um nó “batente” fictício [Sedgewick: Algorithms in C].

Procurando um nó numa árvore:

Para a árvore funcionar, temos que adotar critérios para criação de novos nós e para pesquisá-los… Para inserir um nó, procuramos por ele e, se não o encontrarmos, o colocamos à esquerda do nó raiz mais recente (da sub árvore mais perto das “folhas” da árvore, na pesquisa) se a “chave” for menor que a deste nó raiz, ou à direita, em caso contrário… Na pesquisa, temos que “andar” pela árvore numa ordem conhecida, de acordo com o que queremos obter… Se quisermos obter uma listagem ordenada, devemos “caminhar em-ordem”, ou seja, visita-se o nó do lado esquerdo da sub árvore, depois o nó raiz e depois o nó do lado direito. Justamente porque todos os nós do lado esquerdo são “menores” que o nó raiz e todos os do lado direito, maiores.

Existem outras formas de pesquisar, mas vou me ater apenas a esse, já que é o mais usado.

Note também que “esquerda e direita”, “maior e menor” são critérios arbitrários que dependem do problema… Numa árvore binária de particionamento espacial (BSP), usada em computação gráfica, os nós à esquerda e à direita podem ser chamados de “à frente” e “atrás” de um plano que recorta o espaço tridimensional em dois sub espaços:

struct bsp_node_s {
  struct plane_s plane;
  struct bsp_node_s *front, *back;
  /* ... Outros dados aqui ... */
};

Outros problemas podem adotar outros critérios para “esquerda” e “direita” ou “maior” e “menor”.

É claro que árvores também precisam acomodar a comparação por igualdade em seus nós e isso depende de sua aplicação… podemos escolher colocar à esquerda apenas os nós “menores” que os nós raízes e à direita, os que caem no critério de “maior ou igual”, mas podemos fazer o contrário, se for mais conveniente também… Podemos ainda acomodar “listas” em cada nó, e por ai vai.

Árvores capengas:

O problema desse tipo de árvore binária é que ela pode se “degenerar” para uma lista encadeada simples. Por exemplo:

fig33

Se inserirmos cada nó na ordem (4, depois 7, depois 16, …) obteremos uma lista. Achar o item 43, usando o algoritmo de pesquisa “em ordem” terá uma performance parecida do que fazer uma pesquisa numa lista de encadeamento simples!

Este é um caso extremo e alguns autores alegam que seja raro, mas árvores mais levemente degeneradas causam problemas semelhantes. Ao invés de termos um tempo de busca proporcional a \lg N, o tempo aumentará, tornando a árvore menos que ótima…

Note que a “lista” acima faz com que a árvore fique mais “pesada” do lado direito do que do lado esquerdo. Ela está, então “desbalanceada” (como num balanço no parquinho do playground). Têm que haver um jeito de fazer com que o lado direito tenha um peso semelhante ao lado esquerdo em todas as circunstâncias!

Algoritmos de balanceamento de árvores binárias:

Existem vários métodos para garantir o “balanceamento” de uma árvore binária. O mais conhecido é a chamada árvore de busca AVL. “AVL” é uma homenagem aos criadores do algoritmo, dois russos chamados Gregory Maximovich Adelson-Velsky (Гео́ргий Макси́мович Адельсо́н-Ве́льский) e Evgenii Mikhailovich Landis (Евге́ний Миха́йлович Ла́ндис). O algoritmo consiste em manter, em cada nó, uma contagem da diferença do “peso” de cada lado e, toda vez que esse peso for maior que +1 ou menor que -1, alguma coisa deve ser feita para “balancear” a subárvore.

O balanceamento, neste caso, admite que um lado pode ter apenas um nível a mais que o outro, não mais que isso. Assim, numa árvore perfeitamente balanceada, todos os seus nós terão peso zero. Mas isso só é possível se todos os nós do último nível forem preenchidos. O que nem sempre é o caso. Assim, pesos +1 e -1 são também aceitáveis.

Sempre que um item for colocado na árvore, os pesos são recalculados e, para aqueles que ultrapassarem os valores +1 ou -1 (se o “peso” das sub árvores fizerem a árvore pender para a direita ou esquerda, respectivamente), então operações de “rotação” devem ser feitas para reordenar os nós. A rotação aqui significa que um outro nó, que não o nó raiz original, será emancipado para ser o novo nó raiz de uma sub árvore (ou da árvore toda). Por exemplo, se na figura anterior, onde o nó ‘4’ é o nó raiz original, se “rotacionamos” a árvore, colocando o nó ’20’ como raiz, os nós ‘4’, ‘7’ e ’16’ ficarão no lado esquerdo do nó ’20’ e os demais, do lado direito, tornando a árvore mais “equilibrada”.

A animação abaixo ilustra:

Tree_rotation_animation_250x250
Exemplo de rotação de árvore.

Aqui, α, β e ϒ são sub árvores, cujos nós raízes são A e B. Ambas as árvores, se percorridas “em ordem” são essencialmente as mesmas… Com essa simples operação podemos balancear uma árvore inteira, usando como critério os “pesos” contidos nos nós, vide algoritmo AVL…

Aliás, pelo critério de balanceamento que descrevi, a primeira árvore mostrada neste texto também não é balanceada! Precisaríamos rotacionar a sub árvore com nó raiz em ‘G’ para obtermos um balancearmos melhor (‘I’ seria a nova raiz dessa sub árvore)… Como está, a sub árvore do lado esquerdo (raiz em ‘B’) está balanceada (tem apenas um nível de diferença), mas a do lado direito tem 2!

Nem sempre queremos árvores balanceadas!

Vimos, no artigo sobre o algoritmo de Huffman (aqui), que o balanceamento de árvores binárias nem sempre é desejável… No caso de Huffman, o desbalanceamento é o que mais desejamos, para obtermos um caminho menor para os itens de maior frequência. O balanceamento só é vantajoso se o que queremos fazer é usarmos uma árvore binária como mecanismo de acelerar inserções e buscas ordenadas…

Se seu programa precisa lidar com listas ordenadas, prefira o uso de árvores balanceadas. Usar funções como qsort() em arrays grandes toda vez que inserir um item pode tornar seu código bem lento. Como vimos, para buscar um item numa árvore leva-se o tempo proporcional a \lg N, mais ou menos o que acontece com uma busca binária.

Árvores 2,3,4:

Além do algoritmo AVL, existem outros interessantes… A árvore “vermelha-e-preta” (red-black tree) é um deles, mas o entendimento desse algoritmo depende do entendimento de um tipo de árvore que não é binária. As árvores 2,3,4. Elas têm esse nome porque cada nó da árvore suporta 2, 3 ou 4 nós filhos, ou seja, cada nó suporta 1, 2 ou 3 chaves… Quanto a árvore vermelha-e-preta, deixarei para explicá-la em outra oportunidade, porque isso aqui já tá ficando grande!! :)

Numa árvore binária cada nó tem apenas uma chave usada como critério para colocamos os nós filhos do lado esquerdo ou direito. Para termos nós com mais que dois filhos temos que ter dois critérios de comparação… Para 4 filhos, 3 critérios. Numa árvore 2,3,4 temos, consequentemente, 1, 2 ou 3 chaves, de acordo com o número de filhos que o nó terá. Num nó com uma chave a escolha pelo lado direito ou esquerdo é simples, como vimos lá em cima… Num nó com duas chaves (k1 e k2), assumindo que elas estão em ordem crescente de valor, temos 3 nós filhos (n1, n2 e n3). Ao inserir um item filho desse nó temos que decidir pelo nó filho n1 se a chave k do novo nó for menor que k1, pelo nó n2 se k estiver entre k1 e k2; ou pelo nó n3 se k for maior que k2. O mesmo vale para nós com 3 chaves, só que adicionamos um critério intermediário.

Efetivamente, teremos uma lista de chaves em cada nó. Para criarmos uma árvore com 3 chaves só precisamos de um único nó (porque os nós filhos podem ser nulos!). Ao inserir uma 4ª chave, ela será colocado num dos nós filhos, de acordo com a regra acima… Mas, para fazer essa árvore ficar balanceada a coisa não pode ser tão simples assim…

Ao inserir uma nova chave na árvore precisamos percorrê-la e a cada vez que virmos um nó cheio temos que desmembrá-lo. Isso é feito fazendo com que a chave central “suba” um nível. Se o nó raiz também estiver cheio a chave central sobe e fica isolado na raiz, desmembrando o antigo nó raiz em dois nós filhos. Eis um exemplo onde queremos inserir uma nova chave (por exemplo, ‘e’):

RB-Split4under2-3

Ainda não inserimos ‘e’, mas note que o nó contendo as chaves ‘b’, ‘c’ e ‘d’ está cheio (não cabem mais chaves), mas o nó pai está praticamente vazio (só tem a chave ‘a’). Para abrir espaço para uma chave ‘e’ transferimos a chave central, ‘c’, do nó filho para o pai, desmembrando o nó filho em dois filhos. Agora, se quisermos, podemos colocar a chave ‘e’ no nó onde só temos a chave ‘d’…

Essa complicação tem o objetivo de manter os nós paternos o mais livres possível para que os filhos possam crescer sem que novos níveis tenham que ser, necessariamente, criados e a transferência de chaves entre pais e filhos mais ou menos garante o balanceamento da árvore, ou seja, a busca em tempo proporcional conhecido.

O conceito do funcionamento das árvores 2,3,4 é, mais ou menos, o princípio de outro tipo de árvore não binária chamada B-Tree, muito usada em alguns filesystems (como o BTRFS, por exemplo) e em armazenamento de bancos de dados. A diferença é que B-Trees não são binárias, terciárias ou quaternárias, elas têm mais chaves (7, 9 ou tantas quantas você quiser) e umas regras um cadinho diferentes… Mas, também lá, a transferência de chaves entre pais e filhos e a criação de novos nós só acontece quando não tem jeito. Funciona igual…

Como veremos num outro artigo as árvores vermelha-e-preta usam o mesmo artifício das árvores 2,3,4, mas são árvores binárias.

Anúncios