MO417 - QUESTÃO PARA A PROVA ORAL
Número:Enunciado: Um dicionário futebolístico é indexado através de uma árvore Vermelho-Preto, onde cada nó é um ponteiro para uma lista de palavras iniciadas com a mesma letra.
Antes de inserir uma palavra no dicionário, o sistema verifica se o nó com a chave correspondente já está na árvore, se não estiver ele usa o método RB-INSERT abaixo para incluí-lo.
Sabendo que foram inseridas apenas as seguintes palavras no dicionário (Na mesma ordem em que são apresentadas), responda: Qual das alternativas abaixo está correta?
Futebol - Liga - Atacante - Meia - Equipe - Número - Goleiro - Obstrução
RB-INSERT(T, z)
01 y = T.nil
02 x = T.root
03 while (x != T.nil) {
04 y = x
05 if (z.key < x.key)
06 x = x.left
07 else x = x.right
08 }
09 z.p = y
10 if (y == T.nil)
11 { T.root = z }
12 elseif (z.key < y.key)
13 { y.left = z }
14 else
15 { y.right = z }
16 z.left = T.nil
17 z.right = T.nil
18 z.color = RED
19 RB-INSERT-FIXUP(T, z)
RB-INSERT-FIXUP(T, z)
01 while (z.p.color == RED) {
02 if (z.p == z.p.p.left) {
03 y = z.p.p.right
04 if (y.color == RED) {
05 z.p.color = BLACK
06 y.color = BLACK
07 z.p.p.color = RED
08 z = z.p.p
09 } else {
10 if (z == z.p.right) {
11 z = z.p
12 LEFT-ROTATE(T, z) }
13 z.p.color = BLACK
14 z.p.p.color = RED
15 RIGHT-ROTATE(T, z.p.p) }
16 } else {
17 /* Código igual a cláusula "then"
18 com "right" e "left" trocados.*/ }
19 }
20 T.root.color = BLACK
a. A altura de preto dessa árvore é 3.
b. O número de nós internos na cor preta é superior aos de cor vermelha.
c. Os nós com as chaves "G", "O" e "L" possuem a mesma cor.
d. Os nós com as chaves "F", "L" e "A" ficaram em níveis diferentes.
e. NDA
Ideia original de: Anderson Coelho Weller
