Exercício 2

Considere o TAD rbt e a implementação dada na teórica (ficheiros: tadrbt.h, tadrbt.c e rbtmain.c):

1. insira os seguintes valores numa rbt: 12 14 15 17 3 4 6 9 1 11; pela ordem indicada. indique para cada inserção qual a rbt obtida.

2. implemente a operação altura_preta de uma rbt.

   teste a sua função para diferentes rbts.

3. Implemente a operação sucessor valor, que deve devolver o sucessor do valor.

   teste a sua função para diferentes rbts.

4. Implemente a operação pesquisa_rbt valor, que deve retornar o nó com chave valor.

5. Implemente a operação maximo_rbt, que deve retornar a maior chave.

6. Implemente a operação minimo_rbt, que deve retornar a menor chave.

7. Implemente a operação lista_ord_rbt, que deve listar os elementos por ordem decrescente.

8. Implemente a operação é_rbt que dada uma struct rbt verifica se as 4 propriedades se verificam.
   1. Um nó ou é preto ou vermelho
   2. Uma folha (NIL) é preta.
   3. Se um nó é vermelho então os seus dois filhos são pretos
   4. Qualquer caminho de um nó a uma folha tem sempre o mesmo número de nós pretos.

9. A resolução deste exercício deve ser enviada por email para o docente das práticas [ pp@di.uevora.pt ] até 25/03/2003 às 23.59 (hora do servidor de mail). O email deve conter ainda os números de aluno e os nomes dos elementos do grupo. Por cada dia de atraso serão descontados 2^n-1 valores na nota do trabalho (n = número de dias em atraso).