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!
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]
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] [/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.