Resolução da ordenação de árvore in-place implementado em JS

[Leandro Santiago]

Tá, eu tenho este pequeno problema de não me acalmar enquanto não conseguir resolver um problema... Mesmo que tenha 500 outras coisas pra fazer...

Implementei ontem a noite e hoje no começo da manhã o problema de ontem, da ordenação de árvore. Fiz em JS e o código encontra-se em:

https://gitorious.org/lssilva_random_code/dojo_arvore_js/

Creio que a implementação esteja funcionando, e nos poucos testes que fiz parece ter funcionado.

Ela é in-place, ou seja, não cria outra árvore para trabalhar. O algoritmo é bastante ineficaz, mas funciona.

E funciona da seguinte forma:

Todo nó (menos a raíz) possui um pai e pode ou não possuir os filhos.

Uma das propriedades da árvore que estávamos tentando criar é que o pai é sempre maior que o filho.

Imagine uma árvore onde o menor elemento, que deveria estar na folha, está na raíz e o maior elemento, que deveria estar na raíz, está numa folha.

O que fiz é, em cada nó da árvore (começando das folhas e subindo, via recursão) N, caso nó com maior valor abaixo de N seja menor nó acima (daí a necessidade de referenciar o pai) de N, então eu troco estes dois nós. Basicamente isso.

Isso faz os caras de baixo com valor alto serem jogados para o topo e os caras do topo com valor baixo serem jogados para baixo.

Dêem uma olhada no código. Ele especifica duas classes, Tree e Node, e os testes foram implementados via assert mesmo, pq não consegui achar uma suíte de testes rápida de usar.

Mas ao menos dormi bem :-)

--
Sent from my mind

[Leandro Santiago]

Ah sim, o código está pronto pra rodar no node.js. Se, ao executar tree_spec.js não aparecer nada na tela, é pq todos os testes passaram :-)

[Thiago Romão]

asihhiuahiahuah... tbm sou desses... fiz uma versão tbm hj...

mas eu fiz bem simplificada pq é o que eu sei de javascript tava rodando no console do chrome..

(function () {

    var No = function (valor, esquerda, direita) {

        this.valor = valor;

        this.esquerda = esquerda;

        this.direita = direita;

 

        this.ordenar = function () {

            this.esquerda && this.esquerda.ordenar();

            this.direita && this.direita.ordenar();

            this.despromover();

            return this;

        };

 

        this.despromover = function () {

            var promovido = this;

            if (this.esquerda && promovido.valor < this.esquerda.valor) promovido = this.esquerda;

            if (this.direita && promovido.valor < this.direita.valor) promovido = this.direita;

            if (promovido != this) {

                var valor = this.valor;

                this.valor = promovido.valor;

                promovido.valor = valor;

                promovido.despromover();

            }

        };

 

        this.representacao = function (nivel) {

            if (!nivel) nivel = 1;

            var rep = new Array(nivel).join(" ") + this.valor + "\n";

            if (this.esquerda) rep += this.esquerda && this.esquerda.representacao(nivel + 1);

            if (this.direita) rep += this.direita && this.direita.representacao(nivel + 1);

            return rep;

        };

    };

 

    function ArrayToArvore(a, indice) {

        if (!indice) indice = 0;

        if (!a[indice]) return;

        return new No(a[indice], ArrayToArvore(a, indice * 2 + 1), ArrayToArvore(a, indice * 2 + 2));

    }

 

    var no = ArrayToArvore([1, 2, 3, 4, 5, 6, 7, 8, 9]);

    console.log(no.representacao());

    no.ordenar();

    console.log(no.representacao());

})();

--
Você está recebendo esta mensagem porque se inscreveu no grupo "Dojo Maringá" dos Grupos do Google.
Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para dojo-maringa...@googlegroups.com.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.

[Leandro Santiago]

Ah, ficou bem melhor sua solução. Eu olhei tanto a parte inferior um nó quanto a superior, quando só era necessário usar a parte inferior, como vc fez, tendo um custo bem menor.

O pior é que a solução é bastante simples, mas na hora nem conseguimos pensar em como fazê-la. Eu mesmo sinto uma falta lascada de papel quando preciso pensar numa solução. Só consigo resolver as coisas com um lápis e papel na mão :-)

Uma coisa que poderíamos fazer nos próximos dojos é tentar ter à mão um quadro negro/lousa ou algo do tipo. Alguém mais acha útil?

[Fabricio Noda]

Boa ideia! Iremos providenciar pinceis, geralmente os locais já possuem quadros. 

Uma outra ideia, seria preparar e gerar um pdf com o resumo da sintaxe para ser impresso e entregue aos novatos na linguagem. Isto é permitido no Dojo?

Para os 2 próximos iremos tentar conseguir uma sala no DIN UEM, sugestões de linguagem?

Abraço!

Fabrício Noda

44 9870-1355   

[Thiago Romão]

apoiado... sugeriria scala, apesar de não ter a minimA NOÇÃO

[Leandro Santiago]

Acho que tem q ser uma linguagem que ao menos um dos integrantes domine, para não ficarmos muito tempo parados tentando descobrir coisas como sintaxe ou tentando achar o porque de erros de compilação/execução.

Se tiver alguém aí que conheça bem alguma linguagem ainda não usada nos dojos e esteja disposto a apresentá-la ao grupo, dê um passo a frente :-)