INF1010 3WB – Lista 3: Árvores Rubro-Negras (RBTree).

Exercícios

1. Inserir as chaves 9, 8, 7, 6, 1, 2, 3, 4, 5 (nesta ordem) em uma árvore rubro-negra, desenhando a árvore após cada inserção. Exclua as chaves 6 e 8, desenhando a árvore após cada exclusão.
2. Inserir as chaves 4, 7, 12, 15, 3, 5, 14, 18 (nesta ordem) em uma árvore rubro-negra, desenhando a árvore resultante de uma inserção, sendo que uma nova árvore deve ser desnhada quando houver uma rotação ou troca de cores.
3. Considere uma árvore rubro-negra formada pela inserção de n nós com a operação Inserir. Argumente que se n > 1, a árvore terá pelo menos um nó VERMELHO.
4. Prove com um contra-exemplo:
   1. toda árvore AVL é uma árvore rubro-negra.
   2. toda árvore rubro-negra é uma árvore AVL.
5. Escreva o procedimento de remoção de um nó em árvores rubro-negras.
6. Mostre que o caminho mais longo a partir de um nó x em uma árvore rubro-negra até uma folha descendente tem comprimento no máximo de duas vezes o comprimento do caminho mais curto a partir do nó x até uma folha descendente.
7. Observe as árvores abaixo. Sabendo-se que em cada árvore as figuras geométricas representam cores diferentes, marque "V", caso a árvore possa ser red-black, ou "F", caso não haja essa possibilidade. Quando marcar "F", circule pelo menos um nó que indique essa impossibilidade.
   
8. Desenvolva um método que retorne a quantidade de nós pretos de uma dada árvore rubro-negra.
9. Desenvolva um método que retorne a quantidade de nós vermelhos de uma dada árvore rubro-negra.
10. Considerando a árvore rubro-negra a seguir, responda:
    
    1. Faça a inserção do nó 55 e desenhe a árvore resultante.
    2. Considerando a árvore resultante de (a), faça a retirada dos nós 50, 40, 70 e 80, nesta sequência.