arvore binaria + php

[Francis Wecker]

Boa noite,

estou na faculdade, e estamos tendo aula de arvores binarias em c++.

somente por curiosidade, será q existe algo parecido para php?

pesquisei um pouco na net e nao encontrei nada.

[Rubens Takiguti Ribeiro]

Dê uma olhada nas estruturas oferecidas pela SPL em:
http://br2.php.net/manual/en/spl.datastructures.php

Tem MaxHeap e MinHeap.

Ou você pode implementar sua própria árvore com a classe stdClass definindo atributos como "valor", "direita" e "esquerda", depois implementar as funções para manipulação da árvore usando o operador de referência (&) para "apontar" os nós para os outros nós.

Rubens Takiguti Ribeiro
Bacharel em Ciência da Computação - UFLA
Zend Certified Engineer - PHP 5
http://rubsphp.blogspot.com/

2011/9/14 Francis Wecker <frwe...@gmail.com>

--
============================================================
LEIAM SEMPRE AS REGRAS DA LISTA:
http://groups.google.com.br/group/listaphp/web/regras-da-lista-php
--
JQUERY MAGAZINE > http://www.jquerymagazine.com.br
--
PHP MAGAZINE > http://www.phpmagazine.com.br
--
LISTA NODE.JS > https://groups.google.com/group/lista-nodejs?hl=pt-br
--
AJAX-BRASIL > http://groups.google.com/group/ajax-brasil
--
PYTHON-GOOGLE > http://groups.google.com.br/group/python-google
--
DOTNET-BRASIL > http://groups.google.com.br/group/dotnet_br
============================================================

[Davi Alexandre]

O operador de referência não seria inútil no PHP5? Todos os objetos já não são passados por referência?

[Rubens Takiguti Ribeiro]

Davi, o operador de referência não é usado apenas em parâmetro de funções, por isso ele ainda é útil no PHP 5.

Sugeri o operador de referência para ser usado para "apontar" os atributos "direita" e "esquerda" para outros objetos. Seria algo do tipo:

$node1 = new stdClass();
$node1->valor = 123;
$node1->esquerda = null;
$node1->direita = null;

Agora criando o $node2 e inserindo-o à esquerda do $node1:

$node2 = new stdClass();
$node2->valor = 12;
$node2->esquerda = null;
$node2->direita = null;

$node1->esquerda = &$node2;

Isso não seria obrigatório, mas seria útil caso precise mudar o valor do nó através de uma referência.

Rubens Takiguti Ribeiro
Bacharel em Ciência da Computação - UFLA
Zend Certified Engineer - PHP 5
http://rubsphp.blogspot.com/

2011/9/16 Davi Alexandre <bastar...@gmail.com>

[Davi Alexandre]

Sim, eu não estava pensando apenas em parâmetros para funções. Até onde eu sei, o operado =& é desnecessário em qualquer operação relacionada a objetos, uma vez que o operador new sempre retorna uma referência.

Dessa forma, ao realizar:

$node2 = new stdClass();

$node2 já é uma referência, tornando redundante a seguinte operação:

$node1->esquerda =& $node2;

Para verificar isso, fiz o seguinte teste:

<?php

$a = new stdClass;

$a->valor = 10;

$b = new stdClass;

$b->node = $a;

$c = new stdClass;

$c->node = $a;

$a2 = new stdClass;

$a2->valor = 10;

$b2 = new stdClass;

$b2->node =& $a2;

$c2 = new stdClass;

$c2->node =& $a2;

debug_zval_dump($a);

debug_zval_dump($a2);

?>

Para para $a, quanto para $a2 o refCount é o mesmo.

[Rubens Takiguti Ribeiro]

Oi Davi,

Aqui no meu PHP 5.4 (beta) o refcount deu diferente, e conforme era previsto:

object(stdClass)#1 (1) refcount(4){
  ["valor"]=>
  long(10) refcount(1)
}
object(stdClass)#4 (1) refcount(1){
  ["valor"]=>
  long(10) refcount(1)
}

$a teve 4 referências, enquanto $a2 teve apenas uma. Talvez você olhou errado o refcount do atributo "valor" destes objetos.

Imagine a situação: você tem um objeto $b e passa ele por parâmetro de uma função que insere o elemento na árvore $a. Após inserir o elemento na árvore, suponha que  você modifique o valor de alguma coisa em $b. Queremos que isso já propague a mudança para a árvore também. Para isso ocorrer, não precisaria usar a referência do parâmetro da função (como você mesmo disse, objetos são passados por referência), mas para apontar um nó da árvore para o novo nó, precisa usar a referência.

Sei que o new devolve a referência, mas neste caso não é no momento do new que estamos ligando um nó ao outro. Veja a linha:
$b->node = $a;

Neste momento não está sendo chamado o construtor, logo o objeto não é passado por referência se não utilizar =&.

Rubens Takiguti Ribeiro
Bacharel em Ciência da Computação - UFLA
Zend Certified Engineer - PHP 5
http://rubsphp.blogspot.com/

[Rubens Takiguti Ribeiro]

Davi,

  Fiz uns testes aqui e acho que entendi o que disse. O próprio operador de atribuição já devolve a referência, caso se esteja atribuindo um objeto a alguma coisa. Isso eu não sabia, e tem até no manual (http://www.php.net/manual/pt_BR/language.operators.assignment.php). Achei que a referência era passada apenas em parâmetros de funções e no construtor. Aprendi algo novo então, valeu.

Até,

Rubens Takiguti Ribeiro
Bacharel em Ciência da Computação - UFLA
Zend Certified Engineer - PHP 5
http://rubsphp.blogspot.com/