Exercício 2

Considere o TAD rbt e a implementação dada na teórica (ficheiros: tadrbt.h, tadrbt.c e rbtmain.c):
(Atenção que o código do ano passado tinha os filhos direito e esquerdo trocados...)

1. (para fazer numa folha de papel)
   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. (O sucessor é o nó com o valor mais baixo, de entre os nós com valores superiores ao nó com o valor em causa)

   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 crescente ou decrescente, de acordo com um parâmetro booleano passado à função.

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.