MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Considerando uma árvore rubro-negra com n chaves, quais das afirmativas abaixo são verdadeiras ?

I. Uma busca no pior caso percorre   2*(lg n) nós.
II. Num percurso da raiz até uma das folhas,  metade dos nós devem ser vermelhos.
III. A árvore não pode ser constituída apenas por nós pretos. 

1. Apenas I
2. Apenas II
3. I e II
4. II e III
5. NDA