Olá não estou entendendo o enunciado do ex 3, será que alguém poderia me explicar melhor?
Obrigado pela ajuda!
Eduardo.
Se a pergunta fosse, qual a árvore rubro negra de altura máxima com 5 vértices, acho que a resposta seria uma árvore de altura 2: raiz preta, um filho preto e o outro vermelho, e o vermelho com dois filhos pretos. Não dá prá construir uma árvore de altura 3 com 5 nós.
Ajudou?
--
carlinhos
Ajudou?
--
carlinhos
Perfeito! Obrigado!
Na demonstração de que árvores Rubro-Negras são balanceadas vimos que a altura da árvore era O(2*lg(n+1)) = O(lg n). Dei uma olhada na internet e achei também O(2*lg(n + 1) − 1).
Teoricamente, se a altura é limitada pelas funções acimas eu deveria ser capaz de contruir um exemplo assim... certo?
Que seja. Fazendo as contas para o caso n = 5, temos:
h <= 2*lg(5+1) = 5,16 --> h =5
h <= 2*lg(5+1) - 1 = 4,16 --> h =4
Afinal, tem algo errado ou estou sendo chato demais e isso só serve para números relativamente grandes?
Aproveitando a oportunidade, para que servem (com relação ao modelo matemático mesmo... não faz parte das discussões a la "Física no BCC?", rs) as folhas artificiais pretas? Até agora fz tudo como se elas não existissem... =S
Obrigado, abraços.
Teoricamente, se a altura é limitada pelas funções acimas eu deveria ser capaz de contruir um exemplo assim... certo?
Que seja. Fazendo as contas para o caso n = 5, temos:
h <= 2*lg(5+1) = 5,16 --> h =5
h <= 2*lg(5+1) - 1 = 4,16 --> h =4
Afinal, tem algo errado ou estou sendo chato demais e isso só serve para números relativamente grandes?
Aproveitando a oportunidade, para que servem (com relação ao modelo matemático mesmo... não faz parte das discussões a la "Física no BCC?", rs) as folhas artificiais pretas? Até agora fz tudo como se elas não existissem... =S
Obrigado, abraços.
Não entendi o que pode estar de errado... Eu mostrei uma árvore com 5 nós e altura 2 você mostra que a altura é limitada por 4 (ou 5, dependendo da demonstração). O que há de errado? A sua prova não diz que existe uma árvore rubro negra de n nós e altura exatamente 2*log(n+1) - 1, né?
Quando a gente discutiu as rubro negras eu disse que elas estavam lá prá deixar a definição mais simples: todo caminho da raiz a uma folha tem o mesmo número de nós pretos. Se eu não tiver as folhinhas artificiais, com essa definição eu poderia ter uma árvore rubro-negra que é um caminho: raiz preta, um filho vermelho, este tem um filho preto, este um vermelho, e assim por diante. Como essa árvore só tem uma folha, ela seria rubro-negra, né? Aí eu teria de mudar a definição de rubro-negras para: todo caminho da raiz a um ponteiro null passa pelo mesmo número de vértices pretos.
COm relação à outra pergunta, tanto faz os números. Basta o formato da árvore.
abraços,
--
carlinhos
Quando a gente discutiu as rubro negras eu disse que elas estavam lá prá deixar a definição mais simples: todo caminho da raiz a uma folha tem o mesmo número de nós pretos. Se eu não tiver as folhinhas artificiais, com essa definição eu poderia ter uma árvore rubro-negra que é um caminho: raiz preta, um filho vermelho, este tem um filho preto, este um vermelho, e assim por diante. Como essa árvore só tem uma folha, ela seria rubro-negra, né? Aí eu teria de mudar a definição de rubro-negras para: todo caminho da raiz a um ponteiro null passa pelo mesmo número de vértices pretos.
COm relação à outra pergunta, tanto faz os números. Basta o formato da árvore.
abraços,
--
carlinhos
Entendi a necessidade das folhas artificias. Vlw!
Com relação a altura da rubro-negra, eu estava supondo (erroneamente) que se provamos que h <= 2*log(n+1) - 1 eu supostamente deveria ser capaz de construir uma com essa altura.
Tudo OK.
Agora... sobre a últma questão da lista, após preencher toda a matriz E[i][j] não sei o que fazer com os números para obter a configuração da árvore.
Segundo minhas anotações E(i, j) é "o valor esperado para a árvore ótima com os elementos de ki+1 até kj". Como assim valor esperado? Seria a esperança do número de comparações?
Abraços.
Com relação a altura da rubro-negra, eu estava supondo (erroneamente) que se provamos que h <= 2*log(n+1) - 1 eu supostamente deveria ser capaz de construir uma com essa altura.
Tudo OK.
Agora... sobre a últma questão da lista, após preencher toda a matriz E[i][j] não sei o que fazer com os números para obter a configuração da árvore.
Segundo minhas anotações E(i, j) é "o valor esperado para a árvore ótima com os elementos de ki+1 até kj". Como assim valor esperado? Seria a esperança do número de comparações?
Abraços.
Sim, esperança do número de comparações.
Com relação a obter a árvore, lembra que eu disse que tínhamos de guardar, além do mínimo, o "p" que gerou esse mínimo? Com isso você remonta aárvore.
abraços,
--
carlinhos
Com relação a obter a árvore, lembra que eu disse que tínhamos de guardar, além do mínimo, o "p" que gerou esse mínimo? Com isso você remonta aárvore.
abraços,
--
carlinhos
posso construir a arvore com os valores que eu quiser, contanto q mantenha as propriedades de arvore rubro-negra?