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

Exercícios relacionados