Lista8_ArvPV

Prévia do material em texto

Universidade Federal de Campina Grande
Centro de Engenharia Eletrica e Informática
Departamento de Sistemas e Computação
Graduação em Ciência da Computação
Lista de Exercícios
Árvores PV
1. Insira os seguintes valores em uma árvore PV inicialmente vazia e mostre a
árvore (incluindo a cor dos nós) após cada operação: 41, 38, 31, 12, 19, 8.
2. Cite as propriedades das arvores PV.
3. Considere a árvore resultante do exercício 1 após todas as operações de
inserção. É possível recolorir os nós da árvore de forma a gerar árvores PV de
diferentes black-heights? Mostre 2 exemplos.
4. Suponha que uma chave x é inserida em uma árvore PV e logo em seguida é
removido. A árvore resultante é a mesma antes da inserção de x? Justifique sua
resposta.
5. Implemente um algoritmo recursivo que retorna a quantidade de nós pretos
em uma árvore PV.