Árvores Rubro-Negras

Olá pessoal
Alguém pode me tirar uma dúvida de estruturas de dados… se um nó de uma árvore rubro negra é negro e só tem um filho, esse filho necessariamente é rubro?
Obrigado

Nossa Senhora, é a primeira vez que vejo a tradução desse tipo de árvores binárias (red-black trees). Ficou parecido com time de futebol, e pela época de Natal estava achando que era alguma brincadeira (uma árvore de Natal flamenguista…)

Huehueueh, foi assim q meu professor me ensinou… e pra ser sincero é bem melhor que árvores vermelho-preto (não, não sou flamenguista).
Voltando ao assunto, alguém sabe?

(Se não me falha a memória…)
Hum… um nó preto, por ter filhos pretos e vermelhos.
um nó vermelho, só pode ter filhos pretos.
todas as folhas da árvore, são pretas.
a raiz sempre é preta.
A distancia de nós pretos da folha até a raiz, é igual para todos os nós.

Essa árvore é muito show!!!

Bons Estudos, e se divirta! :wink:

Hmmm… Sim, exceto pelo fato d todas as folhas serem negras. Elas podem ser rubras tb.
Ei galera, já tirei minha dúvida. Se um nó só possui um filho e é negro, com certeza esse filho é rubro.

teste você mesmo:

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

Applet muito legal!

[quote]Basic red-black tree with the sentinel nodes added. Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node.
They are the NULL black nodes.
[/quote] :wink:

abre o código fonte do TreeSet, é um implementacao quase fiel do Cormen.

[quote=New__Radical][quote]Basic red-black tree with the sentinel nodes added. Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node.
They are the NULL black nodes.
[/quote] :wink: [/quote]
Creio q vc esteja falando das terminações nulas das árvores. De fato, os algoritmos de inserção, remoção, etc. em ARN consideram o nó nulo como tendo cor negra. Mas uma folha é um nó não-nulo de uma ARN, cujos ponteiros para a esquerda e para a direita são nulos. Esses podem ser negros ou rubros.