Considere a árvore rubro-negra caida para a esquerda cujo percurso em nível (em largura) é: 675187235382901731526016 21. Liste as chaves em nós rubros em ordem crescente.
Passo 1
Estamos recebendo em sequência de inserção os valores 67, 51, 87, 23, 53, 82, 90, 17, 31, 52, 60, 16 e 21 e queremos montar uma árvore rubro-negra com regras de inclinamento à esquerda (LLRB). Vamos usar o algoritmo de inserção em LLRB: inserir como em BST, colorir o nó recém-criado de vermelho e depois, subindo na recursão, aplicar três ajustes: rotação à esquerda se a aresta direita for vermelha (e aresta esquerda preta), rotação à direita se tivermos dois enlaces vermelhos à esquerda, e inversão de cores se ambos os filhos forem vermelhos.
Passo 2
O algoritmo de LLRB garante que à cada inserção mantemos as propriedades de balanço e coloração da rubro-negra. Após inserir todos os elementos na ordem dada (67, 51, 87, 23, 53, 82, 90, 17, 31, 52, 60, 16, 21) e aplicar as rotações e flip de cores necessárias, obtemos a configuração final dos nós e suas cores.
Passo 3
Na árvore final, o único nó vermelho na subárvore esquerda do raiz 67 (preto) é 51 e, dentro da subárvore de 23, o único nó vermelho é 17. Todos os outros nós ficaram pretos.
Passo 4
Ordenando as chaves dos nós vermelhos em ordem crescente, temos os valores abaixo.
Resposta
17, 51