Wanna laugh? Ou criptografia no refúgio dos elfos?

Neste artigo vou tentar debulhar, de leve, sem detalhes profundos, o padrão AES (Advanced Encryption Standard, que pode ser obtido aqui), mas acho necessário (e inconveniente, me desculpem) explicar as duas piadinhas contidas no título:

No ano em que escrevo esse texto houve um “ataque massivo”, no mundo tudo, de um ramsonware chamado Wanna Crypt0r, que ficou conhecido como “Wanna Cry?” (Quer chorar?). Daí o quase click bait “Wanna Laugh?” (Quer rir?)… A outra piadinha é com o nome do algoritmo original do AES, chamado de “Rijndael” (junção dos nomes de seus inventores) e o refúgio dos elfos no Senhor dos Anéis, “Rivendell”. Embora a pronúncia seja diferente, a grafia é bem parecida, não?

Criptografia simétrica de blocos

O objetivo de um algoritmo de criptografia de blocos, do qual o AES faz parte, é transformar um bloco de dados original (que é chamado de plain text ou, aqui, chamarei de “texto”) em um bloco de dados criptografado (chamado de cipher — e não estou falando do sacana que traiu Neo e a turma do Morpheus em Matrix — ou “texto cifrado”, que chamarei de “cifra”), mediante uma chave. O algoritmo, é claro, “embaralha” o texto e obtém uma cifra que não seja facilmente transformada de volta em texto, a não ser que a chave correta seja fornecida.

A maioria dos algoritmos de criptografia de blocos usa blocos de tamanho fixo, tanto para o texto, quando para a cifra e a chave. É o caso do AES que vem em 3 sabores: AES-128, AES-192 e AES-256. Os valores referem-se ao tamanho da chave. Tanto o texto quanto a cifra têm tamanhos fixos de 128 bits (ou 16 bytes). Neste ponto você pode estar um pouco confuso, afinal de contas, tanto o texto quanto a chave deveriam ter tamanhos arbitrários. Acontece que o algoritmo só lida com esses tamanhos fixos e deve ser usado diversas vezes para criptografar blocos maiores. Mais adiante digo como isso pode ser feito.

Quanto à chave, se ela tiver tamanho diferente do padrão, deve-se adequá-la e existem diversos métodos para fazer isso. Um deles é usar um hash ou um valor único correspondente ao texto da chave, ao invés da própria.

Como o AES-128 funciona?

A justificativa matemática por trás do AES (ou Rijndael) é complicada. É baseada num troço chamado “campo de Galois” e não é interessante explorar isso aqui neste pequeno artigo (que, provavelmente ficará grande demais para o meu gosto), mas como ele funciona, do ponto de vista do que ele faz, é simples: Consiste em executar uma sequência de passos n vezes, de acordo com o tamanho da chave. São 10 passos para chaves de 128 bits, 12 para chaves de 192 bits e 14 para 256. Daqui por diante, o meu foco estará restrito à chaves de 128 bits. Porque é o caso mais simples e porque o meu exemplo usará as instruções AES disponíveis nos mais recentes processadores Intel.

Tanto para o texto quanto para a cifra, o bloco de 128 bits é encarado como uma matriz de 4×4 bytes onde a orientação é feita por coluna. Ou seja, o byte 0 está na posição (0,0), o byte 1 na posição (0,1), o byte 2 em (0,2) e assim por diante. AES-128 realiza um conjunto de operações tomando as matrizes do texto e chave como entrada e obtém uma matriz cifra. Na realidade a especificação chama as matrizes intermediárias de estado (state), mas prefiro encará-las como se fossem matrizes crifra intermediárias ou texto intermediárias, de acordo com o ponto de vista.

Eis, em pseudo código, o conjunto de operações que o AES-128 usa para criptografar um texto:

AddRoundKey();
for (i = 0; i < 9; i++)
{
  SubBytes();
  ShiftRows();
  MixColumns();
  AddRoundKey();
}
SubBytes();
ShiftRows();
AddRoundKey();

A operação AddRoundKey efetua a adição de cada byte do texto com cada byte da chave e obtém uma matriz intermediária. Essa “adição” é, na verdade, um “ou exclusivo” (XOR) entre os bytes (por isso o símbolo usado é ⨁). É bom notar que a primeira chamada apenas “adiciona” a chave ao texto.

Antes que a rotina acima possa ser usada outras 9 chaves são criadas com base na chave inicial, com o objetivo de adicionar entropia ao processo criptográfico. Cada chave “derivada” é usada em uma das 8 chamadas, dentro do loop, a AddRoundKey e na chamada final da mesma rotina. Esse processo de derivar novas chaves chama-se key expansion, ou expansão de chave.

Depois da primeira “adição”, a operação SubBytes efetua uma substituição dos bytes da matriz intermediária de acordo com a seguinte transformação:

\displaystyle\begin{bmatrix} y_0\\ y_1\\ y_2\\ y_3\\ y_4\\ y_5\\ y_6\\ y_7 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}\cdot\begin{bmatrix} x_0\\ x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7 \end{bmatrix}+\begin{bmatrix} 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end{bmatrix}

Onde x_n corresponde ao bit n do texto e y_n ao bit n do byte “substituído”. Essa substituição não precisa ser feita com cálculo matricial, podemos usar uma tabela de substituição, chamada de Reijndael subtitution box ou “S-Box”:

unsigned char sbox[] = {
// 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
  0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, //0n
  0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, //1n
  0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, //2n
  0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, //3n
  0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, //4n
  0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, //5n
  0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, //6n
  0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, //7n
  0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, //8n
  0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, //9n
  0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, //An
  0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, //Bn
  0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, //Cn
  0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, //Dn
  0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, //En
  0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16  //Fn
};

Agora temos uma matriz intermediária que não lembra em nada o texto, mas AES faz mais: A operação ShiftRows embaralha as linhas fazendo a rotação de cada uma para a esquerda. A primeira linha é deixada como está, a segunda é rotacionada em 1 byte a terceira em 2 e a quarta em 3 (veja a figura abaixo)

A operação MixColumns é a parte complicada de explicar e é a parte mais intimamente ligada aos “campos de Galois”. Trata-se de multiplicação polinomial que ocorre entre as colunas da matriz intermediária (veja a especificação para entender o “atalho” usado na multiplicação matricial).

As operações do AES

No fim das contas, o bloco de 16 bytes final está criptografado. Depois dessa complicação toda, é muito difícil obter o texto a partir da cifra sem a chave e, mesmo assim, precisaremos realizar todas essas operações de forma inversa:

AddRoundKey();
for (i = 0; i < 9; i++)
{
  InvShiftRows();
  InvSubBytes();
  AddRoundKey();
  InvMixColumns();
}
InvShiftRows();
InvSubBytes();
AddRoundKey();

Onde a chave é também expandida, mas informada na ordem inversa, ou seja, o último AddRoundKey é o XOR com a chave original. As operações InvShiftRows, InvSubBytes e InvMixColumns faz a operação inversa de suas irmãs… InvShiftRows é óbvia: O que foi rotacionado para a direita será rotacionado para a esquerda. Já InvSubBytes e InvMixColumns usam as funções inversas daquelas especificadas na criptografia. Assim como SubBytes, InvSubBytes pode ser implementado por uma consulta em tabela, chamada de “Inverse Subtitution Box” ou InvS-Box:

unsigned char invsbox[] = {
// 0     1     2     3     4     5     6     7     8     9     A     B     C     D     E     F
  0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, //0n
  0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, //1n
  0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, //2n
  0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, //3n
  0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, //4n
  0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, //5n
  0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, //6n
  0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, //7n
  0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, //8n
  0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, //9n
  0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, //An
  0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, //Bn
  0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, //Cn
  0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, //Dn
  0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, //En
  0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d  //Fn
};

As instruções AES

A Intel disponibiliza, em algumas arquiteturas (Haswell em diante), algumas instruções que efetuam os passos necessários para criptografar ou descriptografar blocos de 128 bits usando AES aproveitando-se do fato de que um registrador usado em SSE tem exatamente 128 bits de tamanho! A instrução AESENC  é usada para os primeiros 9 passos e AESENCLAST para o último (onde falta o MixColumns). Existe também a instrução AESKEYGENASSIST, que auxilia na expansão da chave.

Já para a de-criptografia, existem as instruções AESDEC e AESDECLAST. O único problema é que a expansão da chave é diferente para esse processo por causa da maneira como a Intel implementou essas instruções! Para facilitar o processo a instrução AESIMC (que é a mesma InvMixColumns de antes) é usada para derivar a expansão reversa da chave.

Eis um exemplo de código usando essas instruções, sob a forma de funções intrínsecas:

// Compilar usando as chaves -maes e -msse2 (se no modo i386).

#include <string.h>
#include <x86intrin.h>

// Criptografa um bloco.
#define DO_ENC_BLOCK(m,k) \
  do{ \
    m = _mm_xor_si128    (m, k[0]); \
    m = _mm_aesenc_si128 (m, k[1]); \
    m = _mm_aesenc_si128 (m, k[2]); \
    m = _mm_aesenc_si128 (m, k[3]); \
    m = _mm_aesenc_si128 (m, k[4]); \
    m = _mm_aesenc_si128 (m, k[5]); \
    m = _mm_aesenc_si128 (m, k[6]); \
    m = _mm_aesenc_si128 (m, k[7]); \
    m = _mm_aesenc_si128 (m, k[8]); \
    m = _mm_aesenc_si128 (m, k[9]); \
    m = _mm_aesenclast_si128(m, k[10]); \
  } while(0)

// Decriptografa um bloco.
#define DO_DEC_BLOCK(m,k) \
  do{ \
    m = _mm_xor_si128 (m, k[10]); \
    m = _mm_aesdec_si128 (m, k[11]); \
    m = _mm_aesdec_si128 (m, k[12]); \
    m = _mm_aesdec_si128 (m, k[13]); \
    m = _mm_aesdec_si128 (m, k[14]); \
    m = _mm_aesdec_si128 (m, k[15]); \
    m = _mm_aesdec_si128 (m, k[16]); \
    m = _mm_aesdec_si128 (m, k[17]); \
    m = _mm_aesdec_si128 (m, k[18]); \
    m = _mm_aesdec_si128 (m, k[19]); \
    m = _mm_aesdeclast_si128(m, k[0]);  \
  } while(0)

// Conterá a chave expandida e a inversa.
static __m128i key_schedule[20];

static __m128i aes_128_key_expansion(__m128i key,
                                     __m128i keygened)
{
  keygened = _mm_shuffle_epi32(keygened,
               _MM_SHUFFLE(3, 3, 3, 3));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  key = _mm_xor_si128(key, _mm_slli_si128(key, 4));
  return _mm_xor_si128(key, keygened);
}

#define AES_128_key_exp(k, rcon) \
  aes_128_key_expansion(k, \
    _mm_aeskeygenassist_si128(k, rcon))

// Carrega a chave e a expande.
void aes128_load_key(char *key)
{
  key_schedule[0] = _mm_loadu_si128((const __m128i *) key);

  key_schedule[1] = AES_128_key_exp(key_schedule[0], 1);
  key_schedule[2] = AES_128_key_exp(key_schedule[1], 2);
  key_schedule[3] = AES_128_key_exp(key_schedule[2], 4);
  key_schedule[4] = AES_128_key_exp(key_schedule[3], 8);
  key_schedule[5] = AES_128_key_exp(key_schedule[4], 16);
  key_schedule[6] = AES_128_key_exp(key_schedule[5], 32);
  key_schedule[7] = AES_128_key_exp(key_schedule[6], 64);
  key_schedule[8] = AES_128_key_exp(key_schedule[7], 128);
  key_schedule[9] = AES_128_key_exp(key_schedule[8], 27);
  key_schedule[10] = AES_128_key_exp(key_schedule[9], 54);

  // A expansão inversa!
  key_schedule[11] = _mm_aesimc_si128(key_schedule[9]);
  key_schedule[12] = _mm_aesimc_si128(key_schedule[8]);
  key_schedule[13] = _mm_aesimc_si128(key_schedule[7]);
  key_schedule[14] = _mm_aesimc_si128(key_schedule[6]);
  key_schedule[15] = _mm_aesimc_si128(key_schedule[5]);
  key_schedule[16] = _mm_aesimc_si128(key_schedule[4]);
  key_schedule[17] = _mm_aesimc_si128(key_schedule[3]);
  key_schedule[18] = _mm_aesimc_si128(key_schedule[2]);
  key_schedule[19] = _mm_aesimc_si128(key_schedule[1]);
}

// Faz a criptografia de um texto e obtém a cifra.
void aes128_enc(char *cipherText, char *plainText)
{
  __m128i m = _mm_loadu_si128((__m128i *) plainText);
  DO_ENC_BLOCK(m, key_schedule);
  _mm_storeu_si128((__m128i *) cipherText, m);
}

// Faz a decriptografia de uma cifra e obtém o texto.
void aes128_dec(char *plainText, char *cipherText)
{
  __m128i m = _mm_loadu_si128((__m128i *) cipherText);
  DO_DEC_BLOCK(m, key_schedule);
  _mm_storeu_si128((__m128i *) plainText, m);
}

As instruções AES da Intel são úteis em dois sentidos: As tabelas sbox e invsbox não estão visíveis porque estão dentro de seu processador e, portanto, não podem ser modificadas por um atacante. Além disso, as instruções usam SIMD, o que aceleram as coisas um cadinho.

Criptografando diversos blocos

Obviamente temos que dividir os dados que serão criptografados em blocos de 16 bytes. Cuidados devem ser tomados para o caso em que o tamanho de algum bloco seja menor que 16 bytes e algum esquema de padding deve ser feito. Fora isso, assumindo que todos os sub blocos tenham exatamente 16 bytes de tamanho, o método mais ingênuo é usar a mesma chave para todos. Esse método é chamado de ECB (Electronic CodeBook). Ele é “ingênuo” porque, com blocos diferentes do texto sendo criptografados pela mesma chave, usando o mesmo algoritmo, é possível (porém improvável) que um atacante consiga uma “dica” de qual seja a chave.

Para evitar isso, outro método bastante usado é o CBC (Cipher Block Chaining), onde o bloco cifrado anterior é usado como chave para criptografar o próximo. Junte esse encadeamento (chaining) e a complexidade do AES e fica muito difícil alguém obter alguma “dica” sobre a chave original.

O modo CBC exige, também, uma chave extra, não necessariamente secreta, e totalmente aleatória para garantir um melhor embaralhamento… chama-se IV (de Initialization Vector) e, geralmente, é criado por algum gerador de valores aleatórios criptográficos (como a instrução RDRAND, por exemplo). Daí a necessidade de usar um RNG confiável em processos de criptografia.

Existem outros esquemas, como CFB e CTR (dê uma olhada neste artigo para ver a diferença).

B-Trees

Lembram-se das árvores 2,3,4? Já falei delas aqui antes (aqui). Essas árvores tem a capacidade de acumular uma, duas ou três chaves num único nó. Os nome “2,3,4” refere-se à quantidade de links para os nós filhos de cada nó…

Bem… as B-Trees são parecidas. A diferença está na possibilidade de usarmos n chaves em cada nó, onde n é um valor ímpar maior ou igual a 3. Quero dizer, que nós podem ter duas ou mais chaves, mas o limite superior da quantidade deve ser 3 ou mais… Não há limites matemáticos para a quantidade de chaves num nó. Podemos ter nós com 1001 chaves, por exemplo… Na prática, a quantidade de nós é limitada para que não tenhamos que manter listas ordenadas muito grandes. Usarei exemplos com 5 chaves por nó neste texto.

Características das B-Trees e a inserção de chaves:

Cada chave num único nó deve ser arranjada de maneira que a lista esteja em ordem (usarei a ordem crescente aqui, para facilitar o entendimento). Isso quer dizer que:

K_1\leqslant K_2\leqslant\dots\leqslant K_{n-1}\leqslant K_{n}

Enquanto inserimos novas chaves no nó raiz, elas vão sendo colocadas na lista de forma ordenada até a lista ficar cheia (com 5 chaves), a próxima chave inserida, K_6 faz com que o nó sofra uma “divisão” (split). Num split retiramos a chave central e fazemos com que ela “suba” para o nó pai… Quando só temos o nó raiz, essa chave selecionada torna-se o novo nó raiz com dois nós filhos com duas chaves cada:

01-split

Só depois do split a chave K_6 é inserido no nó folha… Todas as inserções sempre são feitas em nós folhas:

02-insert

Outra características menos óbvia é que os nós intermediários e folhas sempre terão \left\lfloor\frac{n}{2}\right\rfloor chaves, no mínimo. Isso fica evidente quando pensamos no processo de split… Apenas nós cheios sofrem split e retirando a chave central (que “sobe”), sobram a quantidade de chaves citada acima para cada lado… A única exceção é o nó raiz, que pode ter apenas uma chave!

Vejamos agora o que acontece se tivermos um nó folha cheio e queremos inserir um item K_9:

03-insert-new-on-full-leaf

Ao percorrer a árvore, determinamos que a chave K_9 deve ser inserida no nó folha mais a direita, que está cheio. Por isso, este nó deve sofrer um split, fazendo com que a chave K_6 “suba” para o nó pai (raiz), dividindo o nó folha em dois e liberando espaço para a inserção de K_9, como mostrado acima.

A regra aqui é: Se formos inserir um item, a cada vez que encontrarmos um nó cheio ao “caminhar” pela árvore (de acordo com o critério da chave), devemos fazer um split. Se ambos o nó raiz e o nó folha estivessem cheios, deveríamos fazer o split do nó raiz e, ao pularmos para o nó folha, fazer o split dele também, subindo a chave central para o nó intermediário… Vejamos como isso funciona neste exemplo mais complexo, ao tentarmos inserir K_9:

04-insert-raiz-e-folha-cheios

Assim, a inserção sempre segue duas regras simples:

  1. Ao “caminhar” pela árvore, ao encontrar um nó cheio, faça um split;
  2. Ao encontrar o nó folha correspondente, insira a chave lá.

Outra característica que não é evidente (embora você possa percebê-la dando uma olhada nos exemplos acima) é que todos os nós folha sempre estarão no mesmo nível. Ou seja, uma B-Tree é “auto balanceada”.

Apagar chaves sempre é mais complicado, né?

Inserir chaves é moleza. As duas regras simples, acima, garantem que a inserção sempre será feita apenas nos nós folha. Não temos esse luxo no caso de apagamento de chaves. Quer dizer, qualquer chave deve poder ser apagada, certo?

O algoritmo de deleção é dividido em duas possibilidades: Uma para chaves contidas em nós folhas e outra para chaves contidas em nós intermediários ou raiz. Ainda assim, cada uma dessas possibilidades tem 5 regras simples.

  1. Se o nó onde a chave se encontra for folha e este nó tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens (ou seja: n_{itens}>\left\lfloor\frac{n}{2}\right\rfloor), então basta apagar a chave da lista. No exemplo com nós de 5 chaves, se o nó folha tiver 3 chaves ou mais essa regra se aplica, caso contrário, teremos que lidar com a segunda possibilidade;
  2. Se o nó for folha e tiver \left\lfloor\frac{n}{2}\right\rfloor itens, uma das sub regras abaixo se aplica (lembre-se: exceto pelo nó raiz, nenhum outro nó pode ter menos que \left\lfloor\frac{n}{2}\right\rfloor chaves!):
    • Se um dos nós folha irmãos do nó contendo a chave a ser apagada tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens, apaga-se a chave desejada e realiza-se uma rotação de chaves, onde a chave do nó pai “desce” para o nó folha e uma chave do nó irmão “sobe” para o nó pai. Eis um exemplo ao apagarmos a chave K_6 da árvore abaixo:
      delete2a
      Note que, neste exemplo, tanto faz se escolhermos o nó irmão da direita ou esquerda. O que vai mudar é o sentido da rotação. No caso da árvore resultante, se quiséssemos apagar a chave K_7, por exemplo, teríamos que realizar uma rotação o sentido horário à partir do nó irmão do lado direito (K_3) e a chave K_4 do nó pai;
    • Se os nós folha irmãos do nó contendo a chave a ser apagada tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, então a chave deve ser apagada do nó folha atual e ele deve ser “juntado” com um nó irmão e a chave do nó pai que os divide “desce”, formando um nó cheio. Isso criará um nó “semi-cheio” e diminuirá o nó pai em um item. Eis um exemplo, apagando a chave K_5:delete2b
      De novo, tanto faz usarmos o nó irmão da direita ou da esquerda.A diminuição do nó pai pode ser problemática se ele não for o nó raiz e tiver \left\lfloor\frac{n}{2}\right\rfloor itens. Este caso é discutido abaixo…;
  3. Se o nó não for folha, mas for um nó interno (entre um nó folha e o nó raiz):
    • Se o um dos nós filhos da chave em questão tiver mais que \left\lfloor\frac{n}{2}\right\rfloor, basta apagar a chave desejada, substituíndo-a por uma das chaves de um extremo de um nó filho. Por exemplo, apagando K_6 da subárvore abaixo:
      delee3a
    • Se os nós filhos tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, basta juntá-los e deletar a chave no nó pai (exemplo, deletando K_8):
      delete3b
      Este é o mesmo segundo sub caso do caso 2, lá em cima.

Neste ponto vale a pena especificar o que seria “juntar” dois nós filhos com \left\lfloor\frac{n}{2}\right\rfloor itens… Trata-se do inverso de um split (chamarei de unsplit)… A chave do nó pai é apagada deste nó, trazida para o centro do nó filho “juntado” e, recursivamente, deletada do novo nó filho… Dessa forma ela pode propagar-se até um nó folha, onde será apagada de acordo com as regras propostas acima. Essa “propagação” não é importante, já que apenas ocorrerá n-1 vezes, onde n é o número de níveis da árvore.

Determinando o tamanho máximo de uma B-Tree:

Como cada nó tem tamanho máximo, podemos calcular, no caso extremo, onde temos todos os nós completamente preenchidos, o tamanho máximo da árvore:

\displaystyle n=1+\left(\sum_{x=1}^k K^x\right)

Onde k é o número máximo de níveis, excluindo o nó raiz (nível 0) e K é o número de chaves por nó. Uma árvore com nós de 5 chaves e 4 níveis tem 781 nós, uma de 5 níveis terá 3901, no máximo. A equação acima poderia ser simplificada para n=\sum_{x=0}^k K^x, mas preferi deixar o “1 +” evidente para explicitar a existência incondicional do nó raiz.

Considere agora como um nó estaria codificado na memória: Em primeiro lugar, precisamos manter registro de quantas chaves existem no nó. Depois, precisamos manter as chaves e os links. Ajuda também manter um “bit” extra, indicando se o nó é folha o não (esse bit pode ser codificado junto com o byte contendo a quantidade de chaves). Por exemplo:

#define MAX_KEYS 5
#define MIN_KEYS ((int)MAX_KEYS / 2)

struct node_s {
  uint8_t type:2;  // 0=root, 1=intermediário, 2=folha
  uint8_t num_keys:6;
  key_t keys[MAX_KEYS];
  struct node_s *children[MAX_KEYS+1];
};

A estrutura acima permite que tenhamos um máximo de 64 chaves num único nó (se num_keys começar a contagem de 1). O tamanho do nó depende do tipo da chave e do número delas. Vamos supor que nossas chaves sejam do tipo uint32_t. A estrutura node_s terá 69 bytes, para as 5 chaves por nó. Parece demasiado, mas considere uma árvore AVL, por exemplo… Cada nó dessa árvore tem dois bits com o valor do balanceamento, a chave e dois nós. Ou seja, nas mesmas condições, 21 bytes. Mas, para guardamos 5 chaves precisaríamos de 5 nós ou 105 bytes… No caso extremo, com 64 chaves por nó, a B-Tree teria nós com 777 bytes. Uma árvore AVL com a mesma quantidade de nós consumiria 1344 bytes… A B-Tree é mais econômica!

Revisando as vantagens das B-Trees sobre as árvores AVL e Red-Black

Vimos que as B-Trees tendem a ser mais econômicas… Outra vantagem é que a rotina de inserção é mais rápida, eventualmente exigindo splits de alguns nós. A rotina de deleção, embora pareça mais complicada, geralmente é tão veloz quanto as das suas irmãs…

No caso das árvores red-black, algumas vezes elas ficam “capengas” ou “desbalanceadas”. As B-Trees não ficam e ainda têm a vantagem de que todos os nós folha sempre ficam no mesmo nível.

Outra vantagem é a alocação de nós… No caso das B-Trees, uma razoável quantidade de chaves é alocada de uma tacada só… Mas, é claro, a taxa de aproveitamento desses nós inicia-se em pouco menos de 50% da alocação. Considerando a economia que as B-Trees nos dão, mesmo assim, é um bom negócio.

Uma coisa que pode ser vista como desvantagem é a necessidade de manter as chaves num nó em ordem. Ao invés de lidarmos apenas com os algoritmos de inserção e deleção, teremos que lidar com ordenação linear também. Considerando que um nó tem tamanho limitado de chaves, esses algoritmos são bem simples e, mesmo que nós grandes fossem usados, alguma variação de qsort poderia ser usado… Da mesma forma, uma vez que as chaves são ordenadas, para encontrar uma chave dentro de um nó, podemos usar algoritmos como binary search, o que acelera bastante a busca.

Mesmo que a pesquisa por nó seja linear, a quantidade de níveis de uma B-Tree é menor que a de uma árvore AVL equivalente, tendendo a torná-la mais rápida.

Num outro artigo mostrarei formas de otimizar as B-Trees. Existem variações desse tipo de árvore de multinível, como as B+Trees e B*Trees.

O que diabos é um “heap”?

É comum que o desenvolvedor em linguagens como C chame a área de alocação dinâmica da memória de “heap”. Segundo Donald E. Knuth em seu The Art of Computer Programming, Volume I, a área de alocação dinâmica começou a ser chamada de heap por alguns autores à partir de 1975. O motivo é linguístico: Um “heap”, no inglês coloquial, é somente um conjunto desordenado de itens, numa gaveta, por exemplo… Nesse sentido, a área de alocação dinâmica é tudo menos um “heap”. Não é à toa que em C++ essa área é chamada de free store ou “armazenamento livre”, relegando o termo tradicional ao esquecimento.

Mas o fato permanece… Essa área continua, tradicionalmente, sendo chamada de “heap”.

O que diabos é um heap, afinal de contas? É uma estrutura baseada em árvore binária com características especiais. Nessa estrutura, todo nó pai tem uma chave “maior” que as chaves dos nós filhos, como mostrado na figura abaixo:

Heap
Eis um heap!

Essa estrutura permite a implementação, por exemplo, de uma “fila de prioridades”, e permite a estruturação da árvore num simples array… Cada nível da árvore é colocado em posições específicas do array… Por exemplo, esse heap da figura pode ser codificado como:

int heap[] = {
  100, 19, 36, 17, 3, 25, 1, 2, 7
};

Aqui, heap[0] sempre conterá a chave do nó raiz. Os dois nós que seguem, heap[1] e heap[2], são os nós filhos do raiz. Os nós heap[3] e heap[4] são filhos de heap[1], da mesma forma, heap[5] e heap[6] são filhos de heap[2]. E é lógico que as duas últimas posições são filhos da posição 3.

As duas próximas posições, que faltam no array, seriam então filhas da posição 4. Se quiséssemos inserir uma chave “4” ela entraria logo depois da chave 7 (o último item do array), tornando-se filha da posição da chave “3”, o que viola o heap. Teríamos que fazer um swap dessas posições para manter a estrutura correta. Note: Inserir novos itens é colocá-los no final da lista, mas é necessário que o array seja percorrido e reordenado… Se um nó filho for maior que o nó pai (do nó raiz aos nós folhas) temos que trocá-los de lugar (experimente inserir, ao invés de “4” uma chave “40”).

Ao percorrer a árvore teremos sempre os nós folha com as menores chaves e podemos usar isso como um critério de prioridade para “desenfileirar” os nós a partir da mais alta prioridade, que estará sempre no nó raiz, desde que reordenemos os nós filhos. No caso da árvore da figura anterior, depois de retirarmos o item 100, o item 19 passa a ser o nó raiz:

Heap2

De novo, tivemos que reordenar os nós para que o heap continue válido. Basta percorrer cada nó, verificando se existe um filho com chave maior. Se houver, faz a troca. A rotina de reordenação é bem simples:

#define swap(a,b) { int t; t = (a); (a) = (b); (b) = t; }

/* Rotina NÂO otimizada. Dá pra melhorar um cadinho,
   deixo como exercício pra você! */
void sort_heap(int *p, size_t size)
{
  size_t i, j;

  for (i = 0; i < size - 1; i++)
  {
    j = 2*i+1;

    if (j < size)
      if (p[i] < p[j])
        swap(p[i], p[j]);

    if (++j < size)
      if (p[i] < p[j])
        swap(p[i], p[j]);
  }
}

Obviamente, se quiséssemos poderíamos alterar a lógica colocando os nós com chaves menores como pais das chaves maiores, tornando o nó raiz o portador da menor chave, sempre…

Inserimos o novo item no final do array e retiramos do começo. O que constitui uma fila (queue), mas os itens inseridos serão ordenados, com base na chave de seu nó pai… Ao retirar, do início da fila, retiraremos o item com a chave de maior valor… O que caracteriza uma fila de prioridade!

Mais uma estrutura básica, mas é básica mesmo!

Neste artigo aqui dei uma palinha sobre como deve-se lidar com listas de encadeamento simples. Mas, se nem só de listas e árvores vive o desenvolvedor, como seria uma fila?

Fila é uma lista onde você enfia um “registro” por um lado e resgata do outro. “O primeiro que entra é o primeiro que sai” ou FIFO (First In, First Out). E como estou interessado em filas com “registros” ou nós alocados dinamicamente, a implementação mais simples é usando listas de encadeamento duplo.

Relembrando as filas de encadeamento simples, a figura abaixo mostra que temos dois nós usados como “batentes”, que chamei de head (cabeça) e tail (rabo) — o que pode gerar uma piadinha suja do tipo: “enfiar pela cabeça e tirar do rabo”… ha ha ha — e é uma estrutura semelhante que usaremos na fila:

slist2

De novo, para lembrar, os “batentes” estão ai para facilitar a manipulação da lista, por exemplo, quando esta estiver vazia. Uma lista vazia possui apenas os batentes e nenhum dos nós intermediários. E, assim, se tivermos estruturas como:

struct node_s {
  struct node_s *next;
  /* os dados entram aqui... */
};

struct list_s {
  struct node_s *head;
  struct node_s *tail;
};

Determinar se a lista está vazia é apenas questão de verificar se o ponteiro next em head aponta para o mesmo lugar que o ponteiro tail. A mesma coisa pode ser usada para determinar se uma fila está vazia ou não, como veremos adiante…

Na fila precisamos saber tanto qual é o primeiro item da lista quanto o último. A estrutura node_s fica um cadinho diferente. Precisamos adicionar um link para o nó anterior. Mas a estrutura queue_s será idêntica a list_s, acima:

struct node_s {
  struct node_s *next;
  struct node_s *prev;
  /* os dados entram aqui... */
};

struct queue_s {
  struct node_s *head;
  struct node_s *tail;
};

Já que temos agora nós que apontam para o próximo item e para o anterior, este tipo de estrutura só pode ser chamada de lista de encadeamento duplo. Uma fila pode ser implementada com esse tipo de lista e, se ela estiver vazia, ficará assim:

empty_queue
Uma fila vazia.

Inicializar uma lista de encadeamento duplo desse jeito é quase a mesma coisa que fizemos com uma lista de encadeamento simples:

struct queue_s *queue_new(void)
{
  struct queue_s *q;
  struct node_s *h, *t;

  if ((q = (struct queue_s *)
           malloc(sizeof(struct queue_s))) != NULL)
  {
    if ((h = (struct node_s *)
             malloc(sizeof(struct node_s))) == NULL)
    { free(q); return NULL; }

    if ((t = (struct node_s *)
             malloc(sizeof(struct node_s))) == NULL)
    { free(h); free(q); return NULL; }

    h->prev = t->prev = h;
    h->next = t->next = t;
    q->head = h;
    q->tail = t;
  }

  return q;
}

Para determinar se essa lista está vazia basta verificar se head->next aponte para o mesmo lugar que tail (do mesmo jeito que fizemos com a lista de encadeamento simples) ou, se quiser, se tail->prev aponte para o mesmo lugar que head:

int queue_isempty(struct queue_s *q)
{ return q->head->next == q->tail; }

A coisa começa a ficar boa quando usarmos essa lista de encadeamento duplo como uma fila. Se tivermos que enfileirar (enqueue) e desenfileirar (dequeue) nós, de posse dos batentes e dos ponteiros “para frente” e “para trás”, podemos inserir facilmente um novo nó logo depois de head e retirá-lo logo antes de tail:

struct node_s *queue_enqueue(struct queue_s *q, ...)
{
  struct node_s *n;

  if ((n = (struct node_s *)
           malloc(sizeof(struct node_s))) != NULL)
  {
    n->prev = q->head;
    n->next = q->head->next;
    q->head->next = n;

    /* Coloca os dados do nó 'n' aqui... */
    ...
  }

  return n;
}

struct node_s *queue_dequeue(struct queue_s *q)
{
  if (!queue_isempty(q))
  {
    struct node_s *n;

    /* Obtém o último nó. */
    n = q->tail->prev;

    /* Desatarracha o nó da fila... */
    q->tail->prev = n->prev;
    n->prev->next = q->tail;

    /* Obs: Se quiser, coloque NULL em
            next e prev do nó n aqui. */
    #if 0
      n->next = n->prev = NULL;
    #endif

    return n;
  }

  return NULL;
}

É claro que depois de chamar queue_dequeue o nó obtido como resultado terá que ser liberado da memória com free, mas ele não constará mais da fila.

Com essa rotina de desenfileiramento, podemos escrever a rotina de destruição da fila assim:

void queue_destroy(struct queue_s **qq)
{
  struct queue_s *q = *qq;
  struct node_s *n;

  while ((n = queue_dequeue(q)) != NULL)
  {
    /* coloque a destruição dos 
       dados do nó aqui... */

    /* Livra-se do nó. */
    free(n);
  }

  /* Livra-se da fila. */
  free(q->head);
  free(q->tail);
  free(*qq);
}

E zé fini! Temos nossa fila implementada.

PS: Notem que, a não ser pela rotina queue_isempty, uso os próprios ponteiros retornados como indicativo de sucesso ou falha (se retornar NULL) das rotinas.

𝅘𝅥𝅮 Uma vez flamengo… 𝅘𝅥𝅮

Chegamos, finalmente, na árvore red black! Para começar deixe-me mostrar as relações diretas entre um nó de uma árvore 2,3,4 e nós de uma árvore red black: Nós “simplex”, com apenas uma chave, são sempre pretos. Nós “duplex”, com duas chaves, contém uma chave “central”, raiz, e uma lateral e podem ser configurados de duas formas, como mostro abaixo. E os nós “triplex” (obviamente com três chaves) têm, necessariamente, uma chave raiz e duas laterais… Chaves “laterais” são sempre vermelhas.

Nós com 1, 2 ou 3 chaves e as equivalentes na red black
Nós com 1, 2 ou 3 chaves e as equivalentes na red black

O fato da chave raiz de um nó de uma árvore 2,3,4 ser preto, numa árvore red black, nos leva para a primeira regra:

  • O nó raiz é sempre preto!

Outra semelhança com árvores 2,3,4 é quanto à “promoção” de uma chave raiz de um nó triplex para um nó acima deste… Ao tentar inserir uma nova chave num triplex, temos que “subir” a chave raiz para o nó superior, abrindo espaço para a nova chave… Numa árvore red black é fácil observar que “subir” um nó preto (raiz do nó triplex) para um nó simplex ou duplex é questão de apenas mudar a cor de preto para vermelho e mudar os nós laterais para pretos. Eis um exemplo usando um duplex como nó superior:

up1

Diferente do artigo anterior (aqui), vou usar chaves vermelhas e pretas nos nós de árvores 2,3,4 da mesma maneira que numa árvore red black. Quer dizer, o nó preto é a raiz da sub árvore que compõe o nó e as vermelhas são as laterais…

O exemplo acima é simples, mas poderíamos ter algo um pouco diferente (repare a ordem nas chaves no nó duplex!):

up2

Se subirmos a chave 4, ela será uma chave lateral e teríamos duas chaves vermelhas no triplex superior… Isso não pode acontecer! Essa é a segunda regra para as árvores red black:

  • Não podemos ter nós vermelhos consecutivos.

Um nó vermelho não pode ser filho (ou pai) de outro nó vermelho…

Obviamente que se tivermos um nó pai simplex não precisamos nos preocupar com rotações, e basta mudar as cores do nó triplex, abaixo deste… Mas, e se o nó pai for triplex? Ora, dai teremos que fazer a “decomposição” do nó, como mostrei no artigo anterior… A decomposição de um nó triplex em três simplexes não poderia deixar de ser mais simples: Basta mudar as cores dos nós filhos do nó raiz do nó triplex para pretos!

Outra regra fundamental das árvores red black:

  • O número de nós pretos em quaisquer “caminhos” da árvore têm que ser igual!

Ou seja, do lado esquerdo de uma sub árvore qualquer temos que ter o mesmo número de nós pretos que têm no lado direito. contando com o nó raiz…  Surpreendentemente essa regra é seguida “automaticamente” pelo algoritmo de inserção nas árvores red black, como veremos…

Inserindo chaves em nós 2,3,4, ao estilo red black:

Para exemplificar a construção desse tipo de árvore (2,3,4), vou inserir itens em sequência (1,2,3,4,5,6…).

Numa árvore binária não balanceada isso nos daria uma configuração de lista de encadeamento simples (como mostrei aqui). É esperado que, numa árvore “balanceada”, isso não aconteça… A técnica para emular uma árvore 2,3,4 com uma árvore binária do tipo red black vai ser inserir sempre nós vermelhos e mudar a cor dos outros nós seguindo algumas regras básicas.

Numa árvore vazia vamos, primeiro, inserir 1, 2 e depois 3… a coisa fica assim:

red-black - adding 1, 2 and 3

Claramente que o nó 1 terá que ser transformado de vermelho para preto para respeitar a primeira regra das árvores red black.

Inserir uma chave nova num nó simplex também é simples… Ele vai do lado esquerdo (se seu valor for \leqslant que o nó preto) ou direito (se for menor)… Nada demais… Mas para transformar um nó duplex num triplex podemos ter que realizar uma rotação, seguindo a nossa última regra (dois nós vermelhos juntos não pode!)…

O que acontece se tentarmos inserir o nó 4 nesse nó triplex é que teremos que decompô-lo, mudando a cor das chaves laterais:

red-black - decomposing

Dai, só precisaremos adicionar o nó 4 onde está o nó 3:

red-black - adding 4

Adicionar o nó 5 também é simples. Basta colocá-lo no nó “duplex” contendo 3 e 4, rotacionando-o (já que a chave 4 é vermelha!). Para inserir a chave 6 precisaremos “subir” a chave 4, dividindo o nó triplex e adicionar ao nó simplex contendo a chave 5 a nova chave 6:

red-black - adding 6

Repare nas cores das chaves do nó raiz… A operação acima, equivalente, esboçada numa árvore red black, é mostrada abaixo. Node que, essencialmente, fizemos uma rotação:

red-black - adding 6 (rb)

Guarde essa operação, a retomaremos quando virmos o algoritmo implementado…

O algoritmo é um pouco mais simples…

As árvores red black reais são um pouco mais fáceis de implementar: Sempre que toparmos com dois nós vermelhos em sequência, temos que realizar uma rotação semelhante a uma dessas:

small-rotation

A primeira é uma rotação corriqueira: O nó pivot é o pai do novo nó (2). Este será transformado no novo nó raiz da sub árvore… O nó avô (pai do pai, o nó 1) será colocado mais à esquerda, ou melhor, na posição onde o menor dos itens entraria na sub árvore. E já que o nó pivot tornou-se o nó raiz, ele é pintado de preto. O nó que “desceu” (1) é pintado de vermelho.

A outra rotação é chamada de zig-zag. Isso porque os nós 2 e 3 são rotacionados para a direita (zig), o que nos fornece exatamente a sub árvore anterior, que é rotacionada para a esquerda (zag).

Mas, repare: A rotação só é necessária se tivermos dois nós vermelhos consecutivos ou quando queremos “subir” uma chave para um nó duplex! O código para inserção de uma chave k numa árvore T é este:

struct node_s { 
  int key; 
  int red; /* 0=preto, 1=vermelho. */ 
  struct node_s *left, *right; 
};

void RedBlackInsert(struct rbtree_s *T, int k)
{
  struct node_s *n,      /* nó atual. */
                *p, *pp; /* nós pai e avô. */

  /* Insere nó vermelho na árvore. */
  n = TreeInsert(T,k);
  n->red = 1;

  /* Obtém o nó pai e avô do novo nó */
  p = parent(n);
  pp = parent(p);

  /* Se o nó não é raiz da árvore T e
     o nó pai for vermelho, transformações
     são necessárias! */
  while (pp && p->red)
  {
    /* Se o nó pai está à direita do avô... */
    if (p == pp->right)
    {
      struct node_s *tmp;

      /* ... e se o nó à esquerda do nó avô for vermelho... */
      tmp = pp->left;
      if (tmp && tmp->red)
      {
        /* "sobe" o nó avô. */
        p->red = 0;
        tmp->red = 0;
        pp->red = 1;

        /* Acabamos aqui. "Sobe" um nível na árvore. */
        n = p;
      }
      else /* ... mas, se o nó à esquerda do avô for preto... */
      {
        /* Se o novo nó estiver à esquerda do nó pai,
           faz "zig"... */
        if (n == p->left)
          RotateRight(T,p);
        
        /* "sobe" o nó avô. */        
        p->red = 0;
        pp->red = 1;

        /* Faz 'zag'... */
        RotateLeft(T, pp);

        /* Acabamos aqui. "Sobe" um nível na árvore. */
        n = p;
      }
    }
    else
    {
      /* Mesma coisa que o bloco acima, mas
         'left' e 'right' são trocados por
         causa da simetria. Ou seja, o nó pai
         estará à esquerda do avô. */
      if (p == pp->left)
      {
        struct node_s *tmp;

        tmp = pp->right;
        if (tmp && tmp->red)
        {
          p->red = 0;
          tmp->red = 0;
          pp->red = 1;

          n = p;
        }
        else
        {
          if (n == p->right)
            RotateLeft(T,p);
        
          p->red = 0;
          pp->red = 1;

          RotateRight(T, pp);

          n = p;
        }
      }
    }

    /* Já que 'n' subiu, pega os nós
       pai e avô, de novo. */
    p = parent(n);
    pp = parent(p);
  }

  /* Certifica-se que o nó raiz seja sempre preto. */
  T->root->red = 0;
}

A rotina insere, com sucesso, até três nós sem fazer quaisquer tratamentos especiais. Somente quando vamos inserir o quarto nó é que os ponteiros p e pp tornam-se válidos (pp será diferente de NULL).

As rotinas auxiliares TreeInsert e parent são triviais. A rotina TreeInsert simplesmente insere um item (vermelho) numa árvore binária comum, não balanceada. Já parent devolve o ponteiro para o nó pai de um nó dado ou NULL se o nó não tem um parente (se for o nó raiz). Ela pode ser implementada de duas maneiras: Podemos percorrer a árvore desde o nó raiz até achar um nó comum dos links (left ou right) apontando para o nosso nó n; ou podemos manter um ponteiro parent em cada um dos nós apontando para o nó imediatamente acima… Essa segunda implementação dificulta um pouco as coisas quando as rotações forem necessárias, mas pode ser uma boa idéia.

E, falando em rotações, elas são simples e fazem o que a figura abaixo sugere, onde o pivot é o nosso nó pai (p) e o root é o nosso nó avô (pp):

Tree_rotation_animation_250x250

As rotinas de rotação devem levar em conta se estamos tentando rotações à partir do nó raiz e atualizar o ponteiro root da estrutura rbtree_s, se for o caso…

Voltando ao exemplo da inserção do nó 6, seguindo o algoritmo acima temos:

algorithm

No primeiro passo, inserimos o nó n e achamos o nó pai (p) e avô (pp). O nó p é vermelho e o nó à esquerda de pp é vermelho também, então vamos “subir” a chave 4 mudando a cor para vermelha e mudando suas filhas para pretas… Daí. subimos n em um nível e repetimos o processo. Agora temos uma nó p vermelho e o nó à esquerda de pp preto. Precisamos rotacionar esses dois nós à esquerda e, voilà! Acabamos com uma árvore exatamente como queríamos.

A criação da árvore está ai, bem como a explicação de como ela funciona… Resta-nos ver como apagar um nó da árvore, mantendo a estrutura de controle coerente (as cores dos nós)… Deixo isso para outra oportunidade…