Buscar array...

[Bruno Augusto 417]

Estava eu trabalhando (num fim de semana) com Pixels e Imagens quando precisei descobrir as cores de uma imagem.

 

Certo, imagecolorat() resolve meu problema. Mas eu precisava saber à qual cor-base, digamos assim, essas cores pertenciam.

 

Como não consegui nada "simples" com a GD, fiz metade do serviço "no braço".

 

Peguei uma Tabela de Cores bem ampla, separei os Hexadecimais e os correspondentes RGB das informações menos úteis e montei 10 tabelas diferentes, cada uma para uma cor-base.

 

Depois exclui algumas cores que na tabela original, pelo menos visualmente, em nada se pareciam com a categoria à qual pertenciam.

 

Agora, para descobrir a variação de cores de cada pixel da imagem eu teria de fazer um foreach pela tabela de cores dentro de um for-loop pela largura, dentro de outro for-loop pela altura, para só então trabalhar com imagecolorclosest()

 

Isso demorou muito e quase fritou o PC, que já não anda bem das pernas :lol:

 

Então, decidi fazer de uma forma diferente.

 

Se eu JÁ TENHO estruturadas as informações de cores de CADA PIXEL, bastaria que eu comparasse essa matriz com a Tabela de Cores que montei.

 

Mas eu precisaria que essa comparação trabalhasse como imagecolorclosest(), isto é, por proximidade.

 

Ex: Se um pixel da imagem for azul claro (como um céu, por exemplo), mas na tabela eu não tenha EXATAMENTE esse tom de azul, a comparação retornaria a cor mais próxima e, assim, eu pegaria o índice onde esse resultado se encontra e, por conseguinte, descobriria à qual cor-base a cor do pixel pertence.

 

A estrutura inicial fiz semelhante a:

 

$colorTable = array( 'shadeName' => array( 'FFFFFF' => array( 255, 255, 255 ) ) );

$pixelColors = array( 'x;y' => array( 'R', 'G', 'B' ) );

Explicando...

 

shadeName é o nome da cor-base. Como eu disse eu tenho 10 valores, que correspondem às existentes na página que passei (Preto, Azul, Marrom...).

 

Cada shade possui N sub-arrays formados por seus respectivos códigos hexadecimais e,como valores, o correspondente em RGB.

 

Já a tabela de Pixels da imagem é mais simples. É estruturada com as coordenadas X e Y (separadas por um ponto-e-vírgula) como índices e os valores RGB dele.

 

Mas eu não sei comparar por proximidade. :(

 

Suponhamos que a cor do pixel seja, em RGB, 155;155;238 (azul arroxeado - #9191EE), mas na tabela eu tenho apenas um tom um pouco mais escuro dele, digamos, 145;145;228 ( #9191E4 ).

 

Obs.: Visualmente, parecem a mesma cor, mas são diferentes.

 

Seria completamente inviável, ficar testando por força bruta a existencia dos arrays entre o primeiro e o segundo.

 

Isso porque, nesse exemplo, fiz uma variação de apenas 10 níveis por canal, mas em produção a coisa pode variar o quê, 50 canais em uma, 2 canais em outra e 120 na terceira.

 

Alguma idéia?

[ell_cpu 0]

http://br.php.net/manual/pt_BR/function.array-diff.php

[Bruno Augusto 417]

array_diff() retorna um array com os elementos doprimeiro array que não existem no segundo.

 

Para esse caso talvez servisse apenas se eu tivesse TODAS 16581375 cores do RGB Color Space (isso que ainda não estou considerando o canal Alpha).

 

Mas se eu tivesse todas elas, com certeza faria de uma forma diferente.

 

Se acompanhar o fórum Design Geral verá que eu até já adaptei, melhorando, um algoritimo de classificação por proximidade, mas que está levemente falhopois necessito de mais Cores Puras.

[João Batista Neto 448]

Bruno, pesquise (nessa ordem):

 

Heap (Min ou Max Heap)

Map

Binary Search

 

Se não conseguir implementar posto um exemplo, mas pesquise antes.

 

;)

[Bruno Augusto 417]

Eu até entendi como SplHeap funciona, mas não consegui implementar o retorno pois, para esse caso, a comparação deveria ocorrer com cada um dos 3 canais.

 

Mas o SplHeap::compare() espera um inteiro como retorno.

 

class colorsHeap /*extends SplHeap*/ {

   public function compare( $a, $b ) {

       list( $R1, $G1, $B1 ) = $a;
       list( $R2, $G2, $B2 ) = $b;

       printf( '%d<br />%d<br />%d<br /><br />', $R1, $G1, $B1 );
       printf( '%d<br />%d<br />%d', $R2, $G2, $B2 );
   }
}

Obs: Comentei a herança à SplHeap para ver como eu chegaria no inteiro que ela utilizaria antes de, de fato, o fazer.

 

Eu poderia usar strcmp() e comparar $R1 com $R2, por exemplo.

 

Mas em que isso ajudaria se eu também precisaria comparar os canais G e B das mesmas cores passadas?

 

Continuando com as "solicitações de pesquisa", Map! Map o quê? Ficou meio genérico e toda vez que eu buscava retornava Google Map

 

E sobre Binary Search experimentei esta usando assim:

 

$givenValue = 127;

binaryComparison( $givenValue, array( 120, 128, 136 ),

                 function( $obj, $needle ) {
                     return strcmp( $obj, $needle );
                 }

                );

Mas não entendi o que acontecia.

 

Tendo $givenValue como 120, obtinha 0 (zero).

Tendo $givenValue como 128, obtinha 1.

Tendo $givenValue como 136, obtinha 2.

 

Qualquer valor diferente dos que haviam no array, retornava -1, mas era o -1 de erro da função, após término do loop;

 

Mas enfim, mesmo com tudo isso, ainda não ajudou em nada pois eu ainda assim precisaria ter todas as variações dos canais para poder determinar se uma cor é derivada de uma ou de outra base.

 

Eu acho que precisode um algoritimo mais aprimorado, mas rodei tantas fórmulas matemáticas sem sucesso que já estou até meio zonzo.

[João Batista Neto 448]

Eu até entendi como SplHeap funciona, mas não consegui implementar o retorno pois, para esse caso, a comparação deveria ocorrer com cada um dos 3 canais.

 

Mas o SplHeap::compare() espera um inteiro como retorno.

 

Sim, nesse caso você deveria extrair um hash da cor e fazer a comparação utilizando o hash.

 

Continuando com as "solicitações de pesquisa", Map! Map o quê? Ficou meio genérico e toda vez que eu buscava retornava Google Map

 

Bom, foi falha minha.

 

Realmente a palavra é muito genérica e o Google com toda certeza colocaria o Google Maps no topo da pesquisa.

 

Procure por hash map (ou hash table).

 

Mas não entendi o que acontecia.

 

Ué Bruno,

 

Ele está te devolvendo o offset do valor procurado. Se não encontra, devolve -1. :P

 

Mas enfim, mesmo com tudo isso, ainda não ajudou em nada pois eu ainda assim precisaria ter todas as variações dos canais para poder determinar se uma cor é derivada de uma ou de outra base.

 

Eu acho que precisode um algoritimo mais aprimorado, mas rodei tantas fórmulas matemáticas sem sucesso que já estou até meio zonzo.

 

Certo, vamos bem devagar então, começando por uma árvore binária simples (sem balanceamento), depois vamos caminhando para coisas menos simples.

 

Node.php

<?php
/**
* Interface para definição de um nó em uma árvore binária
*/
interface Node {
/**
 * Recupera o valor do nó
 * @return mixed
 */
public function getData();

/**
 * Recupera o nó da esquerda
 * @return Node
 */
public function getLeft();

/**
 * Recupera o nó da direita
 * @return Node
 */
public function getRight();

/**
 * Insere um valor qualquer no nó
 * @param $value mixed
 */
public function insert( $value );
}

 

BTNode.php

<?php
/**
* Implementação de um nó em uma árvore binária
*/
class BTNode implements Node {
/**
 * O valor do nó
 * @var mixed
 */
private $value;

/**
 * Nó da esquerda. Pode ser um nó final (Leaf) ou uma sub-árvore porém, qualquer
 * elemento contido a esquerda da árvore será menor ou igual ao nó.
 * @var Node
 */
private $left;

/**
 * Nó da direita. Pode ser um nó final (Leaf) ou uma sub-árvore porém, qualquer
 * elemento contigo a direita da árvore será maior ou igual ao nó.
 * @var Node
 */
private $right;

/**
 * Um contador que será utilizado para contagem de iterações em uma busca
 * @var integer
 */
private static $count = 0;

/**
 * Constroi um nó com um valor qualquer
 * @param $value mixed
 */
public function __construct( $value ){
	$this->value = $value;
}

/**
 * Recupera o valor do nó
 * @return mixed
 * @see Node::getData()
 */
public function getData(){
	return $this->value;
}

/**
 * Recupera o nó da esquerda
 * @return BTNode
 * @see Node::getLeft()
 */
public function getLeft(){
	return $this->left;
}

/**
 * Recupera o nó da direita
 * @return BTNode
 * @see Node::getRight()
 */
public function getRight(){
	return $this->right;
}

/**
 * Insere um valor qualquer
 * @see Node::insert()
 */
public function insert( $value ){
	if ( $value <= $this->value ){
		if ( $this->left == null ) $this->left = new BTNode( $value );
		else $this->left->insert( $value );
	} else {
		if ( $this->right == null ) $this->right = new BTNode( $value );
		else $this->right->insert( $value );
	}
}

/**
 * Procura um valor qualquer
 * @param $value mixed
 * @return boolean
 */
public function find( $value ){
	++self::$count;

	if ( $value != $this->value ){
		if ( $value < $this->value ){
			printf( "%d < %d\n" , $value , $this->value );
			printf( "O valor procurado é menor que o valor do nó atual, vamos para a esquerda\n\n" );
		} else {
			printf( "%d > %d\n" , $value , $this->value );
			printf( "O valor procurado é maior que o valor do nó atual, vamos para a direita\n\n" );
		}
	}

	if ( $value == $this->value ){
		printf( "Encontramos %d com %d iterações\n" , $value , self::$count );
		self::$count = 0;
		return true;
	}
	elseif ( $value <= $this->value && $this->left != null ) return $this->left->find( $value );
	elseif ( $value >= $this->value && $this->right != null ) return $this->right->find( $value );

	self::$count = 0;
	return false;
}
}

 

BTree.php

<?php
/**
* Implementação de uma árvore binária não balanceada
*/
class BTree implements Node {
/**
 * Nó raiz da árvore
 * @var BTNode
 */
private $root;

/**
 * Recupera o valor do nó raiz
 * @return mixed
 */
public function getData(){
	if ( $this->root !== null ) return $this->root->getData();
}

/**
 * Recupera o nó a esquerda do nó raiz
 * @return BTNode
 */
public function getLeft(){
	if ( $this->root !== null ) return $this->root->getLeft();
}

/**
 * Recupera o nó a direita do nó raiz
 * @return BTNode
 */
public function getRight(){
	if ( $this->root !== null ) return $this->root->getRight();
}

/**
 * Insere um valor qualquer na árvore
 * @param $value mixed
 */
public function insert( $value ){
	if ( $this->root == null ) $this->root = new BTNode( $value );
	else $this->root->insert( $value );
}

/**
 * Procura um valor qualquer na árvore
 * @param $value mixed
 * @return boolean
 */
public function find( $value ){
	if ( $this->root !== null ) return $this->root->find( $value );

	return false;
}
}

 

Agora vamos fazer um experimento utilizando uma busca linear em uma matriz e uma busca binária na árvore:

 

<?php
/**
* Vamos utilizar uma matriz com 100 números aleatórios para o experimento
*/
$numbers = range( 0 , 1000 );
shuffle( $numbers );
$numbers = array_slice( $numbers , 0 , 100 );

/**
* Inserindo os dados na árvore
*/
$tree = new BTree();

for ( $i = 0 , $t = count( $numbers ); $i < $t ; ++$i ){
$tree->insert( $numbers[ $i ] );
}

/**
* Escolhemos um número aleatório para ser procurado
*/
$toFind = $numbers[ rand( 0 , 99 ) ];

/**
* Fazendo a busca linear na matriz
*/
printf( "Busca linear:\n" );
for ( $i = 0 , $t = count( $numbers ); $i < $t ; ++$i ){
if ( $numbers[ $i ] == $toFind ){
	printf( "Encontramos %d com %d iterações\n\n" , $toFind , $i + 1 );
}
}

/**
* Fazendo a busca binária na árvore
*/
printf( "\nBusca binária:\n" );
$tree->find( $toFind );

 

Como os números do experimento são aleatórios, você terá um resultado diferente do meu, mas a saída será parecida com:

 

Busca linear:
Encontramos 1000 com 63 iterações


Busca binária:
1000 > 906
O valor procurado é maior que o valor do nó atual, vamos para a direita

1000 > 912
O valor procurado é maior que o valor do nó atual, vamos para a direita

1000 > 975
O valor procurado é maior que o valor do nó atual, vamos para a direita

1000 > 995
O valor procurado é maior que o valor do nó atual, vamos para a direita

Encontramos 1000 com 5 iterações

Ou

 

Busca linear:
Encontramos 820 com 76 iterações


Busca binária:
820 > 164
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 > 468
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 < 966
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

820 < 953
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

820 > 617
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 > 644
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 > 740
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 < 870
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

820 > 746
O valor procurado é maior que o valor do nó atual, vamos para a direita

820 < 854
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

Encontramos 820 com 11 iterações

Ou

 

Busca linear:
Encontramos 958 com 81 iterações


Busca binária:
958 > 527
O valor procurado é maior que o valor do nó atual, vamos para a direita

958 > 942
O valor procurado é maior que o valor do nó atual, vamos para a direita

958 < 972
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

958 < 961
O valor procurado é menor que o valor do nó atual, vamos para a esquerda

958 > 951
O valor procurado é maior que o valor do nó atual, vamos para a direita

Encontramos 958 com 6 iterações

Se estiver tudo ok até aqui, dá um toque que vamos balancear essa árvore.

 

PS: esses dias meu tempo tem estado meio curto, então talvez eu volte a demorar a responder.

[Bruno Augusto 417]

Olha, a implementação foi tranquila de entender. O único senão foi a definição da propriedade $value de BTNode.

 

Se o root da BTree estiver vazio, significa que ela acabou de ser construída, logo o insert() vai primeiro criar o nó e, com isso, passar pelo construtor, atribuindo o primeiro valor aleatório à propriedade.

 

Depois disso vai só adicionar o valor em um nó específico, baseando-separa isso nesse primeiro valor.

 

Certo? Se sim, por que? Se não, acho que não entendi, de fato, como find() trabalha.

 

Explicado isso, não me leve a mal, mas o que uma BTree teria a ver com o tipo de problema proposto?

 

Digo isso porque pedi ao meu irmão, que ainda estuda, perguntar aos professores de Física se haveria alguma fórmula, no quesito de Ótica que comparasse uma Cor com outra, por analisar cada um dos seus canais.

 

Para minha "felicidade", existe. Mas para infelicidade, o animal esqueceu de copiar a fórmula, mesmo eu alertando que a coisa seria cabeluda. ^_^

 

A primeira vista, a idéia seria comparar por proximidade, mas se alguém foi acertado por uma pedra na cabeça, louco apaixonado o suficiente para desenvolver uma fórmula (e ter reconhecimento de que funciona) para isso, todoo tópico não estaria reinventando a roda?

 

Ah! Quanto ao terceiro QUOTE, Questionei apenas por pura má interpretação do retorno de strcmp()

 

Em outros problemas que essa função se involveu (ou envolveu?) como solução (ou quase isso :P ) ela sempre retornava -1, 0 ou 1. Essa foi a primeira vez que retornou algo diferente desses três valores.

 

Por isso fiquei na dúvida.

 

Ufa! :P

[João Batista Neto 448]

Certo? Se sim, por que? Se não, acho que não entendi, de fato, como find() trabalha.

 

Você percebeu a comparação do custo para encontrar um determinado valor em uma busca linear em relação a uma busca binária ?

 

Explicado isso, não me leve a mal, mas o que uma BTree teria a ver com o tipo de problema proposto?

 

Busca linear:
Encontramos 958 com 81 iterações

Busca binária:
Encontramos 958 com 6 iterações

Como eu disse, esse é apenas o primeiro passo, ainda vamos balancear essa árvore para diminuir o custo da busca já que esse custo está diretamente relacionado com a altura da árvore e depois vamos trabalhar com o map.

 

Mas talvez seja interessante você explicar melhor seu problema, exatamente, o que você quer fazer ?

 

Digo isso porque pedi ao meu irmão, que ainda estuda, perguntar aos professores de Física se haveria alguma fórmula, no quesito de Ótica que comparasse uma Cor com outra, por analisar cada um dos seus canais.

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif http://en.wikipedia....wiki/Mean-shift

 

Mean Shift for Tracking

The mean shift algorithm can be used for visual tracking. The simplest such algorithm would create a confidence map in the new image based on the color histogram of the object in the previous image, and use mean shift to find the peak of a confidence map near the object's old position. A few algorithms, such as Ensemble Tracking(Avidan, 2001), expand on this idea.

 

 

[Bruno Augusto 417]

Inicialmente, antes de fazer todas as buscas relativas a HSI descritas na última reposta do tópico do referido algoritimo, a intenção era, em tendo uma lista de cores RGB puras ou primitivas, isto é, aquelas de que delas outras possam derivar, comparar os canais de outra cor passada com cada canal dessas cores:

 

Exemplos:

 

Vermelho: #FF0000. Em RGB: 255, 0, 0

Alguma tonalidade de Carmim: #FF003F. Em RGB: 255, 0, 63

 

E a partir disso determinar que esse tom de Carmim deriva do Vermelho.

 

Cinza-Médio (aparentemente, é o Cinza Puro): #808080. Em RGB: 128, 128, 128

Algum outro tom de Cinza: #78736B. Em RGB: 120, 115, 107

 

E a partir disso determinar que esse tom de Cinza deriva mesmo do Cinza.

 

E por aí vai.

 

Agora, depois de toda a pesquisa que fiz e me informei melhor sobre os principais Espaços de Cor, como trabalham, pra que servem, qual o melhor para cada situação e etc. já não estou bem certo se essa abordagem é a melhor possível, dadas as informações que passei naquela resposta e que não justifica repetir aqui.

[João Batista Neto 448]

E a partir disso determinar que esse tom de Carmim deriva do Vermelho.

E a partir disso determinar que esse tom de Cinza deriva mesmo do Cinza.

 

Como você deve ter percebido em suas pesquisas, hue é exatamente o que você quer, por exemplo:

 

Vermelho: H: 0, S: 255, V: 255

Vermelho escuro: H: 0, S: 255, V: 139

Vermelho indiano: H: 0, S: 141, V: 205

Vermelho laranja: H: 16, S: 255, V: 255

 

Independente da saturação ou do valor, a tonalidade continua estando na faixa que compreende o vermelho.

 

Dessa forma, você terá um map dessas cores primárias: k -> v(1..*) onde cada chave do map conterá uma lista de cores da sua paleta.

 

Como eu mostrei antes, uma busca em uma BST é muito mais eficiente que uma busca linear, e uma busca em uma AVL é ainda melhor (isso ainda não mostrei); Se o objeto que será adicionado à árvore tiver uma interface que nos permita compará-lo, podemos encapsular o algorítimo de comparação nesse objeto e fazer tanto a busca da paleta adequada, quanto a busca pela cor mais próxima dentro dessa paleta.

[Bruno Augusto 417]

Exato, o que "manda" é o grau (Hue) em que a cor se encontra na... na... sei lá com que se parece o gráfico do espectro de cor. Parece um cone cruzado com pião. :P

 

Se o exemplificado no tópico ainda continua certo, vamos continuar como válido então. :D

 

Eu percebi que na BTree os resultados aparecem em bem menos iterações, mas não sei, ainda não entendi inteiramente como funciona.

 

Você citou (primeiro QUOTE) a pergunta que eu fiz, mas não explicou se o que eu escrevi é mesmo o "como" funciona.

 

Deu pra perceber que ao invés de buscar um por um, até encontrar o valor que combine, a busca binária vai "batendo" o valor buscado de um lado pro outro até que encontra, fazendo menos buscas.

 

Veja se está certo:

 

958 < 961

O valor procurado é menor que o valor do nó atual, vamos para a esquerda

 

958 > 951

O valor procurado é maior que o valor do nó atual, vamos para a direita

 

Encontramos 958 com 6 iterações

Essa mensagem final, após a busca significa que o 958 buscado se encontra entre as duas iterações anteriores?

 

Se sim, como que foi determinado, na próxima iteração (que não ocorreu) a localização do 958? Sabe-se que, de fato, está entre 951 e 961, mas como?

 

Afinal existe um intervalo de outros 10 números entre ambas que deveriam ser testados não?

 

E eu não acredito que até códigos tenham sorte ^_^

 

Quanto ao AVL, se for o que acho que é, com certeza seria melhor ainda, pois numa dessas "batidas" pra um lado da árvore, haveria uma "descida" para uma sub-ramificação do ladoaoquala iteração se posicionou.

 

E em tendo essa ramificação um intervalo a ser buscado bem mais restrito, a iteração seria ainda mais rápida.

 

P.S.: Depois de tudo explicado, entendido e funcional não haveriaproblema de implementara solução em outro Color Space, certo? Ou faria-se desnecessário e eu poderia trabalhar com HSV ao invés de HSI?

[João Batista Neto 448]

Essa mensagem final, após a busca significa que o 958 buscado se encontra entre as duas iterações anteriores?

 

Se sim, como que foi determinado, na próxima iteração (que não ocorreu) a localização do 958? Sabe-se que, de fato, está entre 951 e 961, mas como?

 

Afinal existe um intervalo de outros 10 números entre ambas que deveriam ser testados não?

 

E eu não acredito que até códigos tenham sorte ^_^

 

Bruno, funciona assim:

 

1. Se não existir nenhum nó na árvore, o primeiro item inserido passa ser o nó raiz:

 

Vamos inserir o número 50:

 

 

2. Como agora temos o nó raiz, qualquer outro item que for adicionado à árvore será adicionado a esse nó. Porém, existe uma regra para adicionar valores na árvore.

 

Qualquer valor que for menor ou igual ao nó que receberá o valor deverá ficar a esquerda desse nó e qualquer valor que for maior deverá ficar a direita.

 

Vamos inserir o número 17:

 

 

 

Como 17 é menor que 50, ele fica do lado esquerdo, vamos adicionar o 76:

 

 

 

Como 76 é maior que 50, ele fica do lado direito. Nesse instante, temos uma árvore completa, vamos adicionar o número 9 agora:

 

 

 

 

O que aconteceu:

 

1. 9 é menor que 50, então fica do lado esquerdo.

2. No lado esquerdo já existe um nó raiz então o novo nó será adicionado a esse nó.

3. 9 é menor que 17, então fica do lado esquerdo.

 

Vamos adicionar o 23:

 

 

 

 

O processo é o mesmo:

 

1. 23 é menor que 50, então fica do lado esquerdo.

2. No lado esquerdo já existe um nó raiz então o novo nó será adicionado a esse nó.

3. 23 é maior que 17, então fica do lado direito.

 

Esse processo é repetido até que o último valor seja adicionado na árvore:

 

54:

14:

 

19:

 

72:

 

12:

 

67:

 

http://btree.improjetos.com.br/node11.png

 

Com a árvore montada, a pesquisa funciona baseando-se na regra da árvore (se o valor for menor ou igual, estará no lado esquerdo):

 

Vamos procurar o 19:

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif 19 é menor que 50 ?

Sim, vamos continuar a busca no lado esquerdo

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif 19 é menor que 17 ?

Não, 19 é maior que 17, vamos continuar a busca do lado direito

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif 19 é menor que 23 ?

Sim, vamos continuar a busca do lado esquerdo.

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif 19 é igual a 19, encontramos. :D

 

 

O problema da BST é que, como ela não é balanceada, temos um problema sério.

 

Se inserirmos na árvore os seguintes números: {1, 2, 3, 4, 5} Exatamente nessa ordem, teremos o seguinte:

 

1. Como não existe nenhum número, 1 torna-se o nó raiz

2. Como 2 é maior que 1, 2 fica do lado direito

3. Como 3 é maior que 2, 3 fica do lado direito de 2.

4. Como 4 é maior que 3, 4 fica do lado direito de 3.

5. Como 5 é maior que 4, 5 fica do lado direito de 4.

 

Resultado:

 

http://btree.improjetos.com.br/btree.png

 

 

O custo para encontrar o número 5 nessa árvore é o mesmo que encontrar o 5 em uma lista encadeada.

 

Exatamente essa é a diferença entre uma BST e uma AVL.

[André D. Molin 15]

Show de bola João, muito bom saber disso. E a implementação disso é muito simples, gostei de mais.

Valeu!

[David Ramires 1]

excelente explicação!

 

parabéns! http://forum.imasters.com.br/public/style_emoticons/default/joia.gif

[Bruno Augusto 417]

:o

 

Impressionante.

 

Mas como o exemplo se baseia em números aleatórios, para minha aplicação ainda devo ter os ditos valores. <_<

 

Em produção, importa qual número vai encabeçar o topo da árvore?

[João Batista Neto 448]

Em produção, importa qual número vai encabeçar o topo da árvore?

 

É exatamente esse o ponto.

 

Na BST importa sim, na AVL não.

 

A AVL é auto-balanceada, isso significa que a cada inserção ela garantirá que a árvore não "penda" para um lado específico, causando o problema ilustrado no caso do {1, 2, 3, 4, 5}

 

A implementação da AVL é bastante similar à BST, a diferença consiste exatamente na verificação da altura dos nós e nas rotações necessárias para garantir o balanceamento da árvore.

 

NodeBalance.php

<?php
/**
* Constantes para identificação do tipo de balanceamento dos nós
*/
interface NodeBalance {
/**
 * O nó está pesado do lado direito
 */
const RIGHT_HEAVY = -1;

/**
 * O nó está balanceado
 */
const BALANCED = 0;

/**
 * O nó está pesado do lado esquerdo
 */
const LEFT_HEAVY = 1;
}

 

Node.php

<?php
/**
* Interface para definição de um nó em uma árvore de busca binária
*/
interface Node extends Countable {
/**
 * Insere um valor qualquer no nó
 * @param $value mixed
 */
public function insert( $value );

/**
 * Procura um determinado valor
 * @param $value mixed
 * @return boolean
 */
public function search( $value );
}

 

AVLNode.php

<?php
/**
* Implementação de um nó de uma árvore auto-balanceada
*/
class AVLNode implements Node {
/**
 * Nó filho da esquerda
 * @var AVLNode
 */
private $left;

/**
 * Nó pai
 * @var AVLNode
 */
private $parent;

/**
 * Nó da esquerda
 * @var AVLNode
 */
private $right;

/**
 * Valor do nó
 * @var mixed
 */
private $value;

private static $count = 0;

/**
 * Constroi o objeto do nó
 * @param $value mixed Um valor qualquer
 */
public function __construct( $value , AVLNode $parent = null ){
	$this->value = $value;

	if ( $parent !== null ){
		$this->parent = $parent;
	}
}

/**
 * Recupera a quantidade de itens do nó
 * @return integer
 * @see Countable::count()
 */
public function count(){
	$ret = 1;

	if ( $this->left !== null ) $ret += $this->left->count();
	if ( $this->right !== null ) $ret += $this->right->count();

	return $ret;
}

/**
 * Recupera a altura do nó
 * @return integer
 */
private function getHeight(){
	$left = $this->left == null ? 0 : $this->left->getHeight();
	$right = $this->right == null ? 0 : $this->right->getHeight();

	return 1 + max( array( $left , $right ) );
}

/**
 * Recupera o fator de balanceamento do nó
 * @return integer
 */
private function getBalance(){
	$left = $this->left == null ? 0 : $this->left->getHeight();
	$right = $this->right == null ? 0 : $this->right->getHeight();

	return $left - $right;
}

/**
 * Insere um valor qualquer
 * @see Node::insert()
 */
public function insert( $value ){
	if ( $value <= $this->value ){
		if ( $this->left == null ) $this->left = new AVLNode( $value , $this );
		else $this->left->insert( $value );

		if ( $this->getBalance() >= NodeBalance::LEFT_HEAVY ){
			if ( $this->left->getBalance() < NodeBalance::BALANCED ){
				$this->left->leftRotation();
			}

			$this->rightRotation();
		}
	} else {
		if ( $this->right == null ) $this->right = new AVLNode( $value , $this );
		else $this->right->insert( $value );

		if ( $this->getBalance() <= NodeBalance::RIGHT_HEAVY ){
			if ( $this->right->getBalance() > NodeBalance::BALANCED ){
				$this->right->rightRotation();
			}

			$this->leftRotation();
		}
	}
}

/**
 * Efetua uma rotação a esquerda
 */
private function leftRotation(){
	$parent = $this->parent;

	$right = clone $this->right;
	$this->right = $right->left == null ? null : clone $right->left;
	$right->left = clone $this;
	$right->left->parent = $right;
	$right->parent = $parent;

	foreach ( $right as $property => $value ){
		$this->$property = $value;
	}
}

/**
 * Efetua uma rotação a direita
 */
private function rightRotation(){
	$parent = $this->parent;

	$left = clone $this->left;
	$this->left = $left->right == null ? null : clone $left->right;
	$left->right = clone $this;
	$left->right->parent = $left;
	$left->parent = $parent;

	foreach ( $left as $property => $value ){
		$this->$property = $value;
	}
}

/**
 * Procura um determinado valor
 * @param $value mixed
 * @return boolean
 * @see Node::search()
 */
public function search( $value ){
	++self::$count;
//
//		if ( $value != $this->value ){
//			if ( $value < $this->value ){
//				printf( "\t%d < %d\n" , $value , $this->value );
//				printf( "\tO valor procurado é menor que o valor do nó atual, vamos para a esquerda\n\n" );
//			} else {
//				printf( "\t%d > %d\n" , $value , $this->value );
//				printf( "\tO valor procurado é maior que o valor do nó atual, vamos para a direita\n\n" );
//			}
//		}

	if ( $value == $this->value ) {
		printf( "Encontramos %d com %d iterações\n" , $value , self::$count );
		self::$count = 0;
		return true;
	}
	elseif ( $value <= $this->value && $this->left != null ) return $this->left->search( $value );
	elseif ( $value >= $this->value && $this->right != null ) return $this->right->search( $value );

	self::$count = 0;
	return false;
}
}

 

AVLTree.php

<?php
/**
* Implementação da uma árvore auto-balanceada
*/
class AVLTree extends AVLNode {
/**
 * Nó raiz
 * @var AVLNode
 */
private $root;

/**
 * Constroi a árvore
 */
public function __construct(){}

/**
 * Recupera a quantidade de elementos da árvore
 * @return integer
 * @see Countable::count()
 */
public function count(){
	if ( $this->root == null ) return 0;
	else return $this->root->count();
}

/**
 * Insere um valor qualquer no nó
 * @param $value mixed
 * @see Node::insert()
 */
public function insert( $value ){
	if ( $this->root == null ) $this->root = new AVLNode( $value );
	else $this->root->insert( $value );
}

/**
 * Procura um determinado valor
 * @param $value mixed
 * @return boolean
 * @see Node::search()
 */
public function search( $value ){
	if ( $this->root !== null ) return $this->root->search( $value );
	else return false;
}
}

 

Para o experimento, vamos usar uma quantidade maior de itens, em vez de apenas 100, vamos usar 1000:

 

<?php
$max = 1000;
$ltime = 0;
$ttime = 0;

/**
* Vamos utilizar uma matriz com 100 números aleatórios para o experimento
*/
$numbers = range( 0 , $max * 10 );
shuffle( $numbers );
$numbers = array_slice( $numbers , 0 , $max );

/**
* Inserindo os dados na árvore
*/
$tree = new AVLTree();

for ( $i = 0 ; $i < $max ; ++$i ){
$tree->insert( $numbers[ $i ] );
}

$tests = 10;

while ( $tests-- ){
/**
 * Escolhemos um número aleatório para ser procurado
 */
$toFind = $numbers[ rand( 0 , $max - 1 ) ];

/**
 * Fazendo a busca linear na matriz
 */
printf( "\nBusca linear:\n" );
$time = microtime( true );
for ( $i = 0 ; $i < $max ; ++$i ){
	if ( $numbers[ $i ] == $toFind ){
		printf( "Encontramos %d com %d iterações\n" , $toFind , $i + 1 );
		break;
	}
}

$time = microtime( true ) - $time;
$ltime += $time;

printf( "Tempo para encontrar %d na matriz: %f\n" , $toFind , $time );

/**
 * Fazendo a busca binária na árvore
 */
printf( "\nBusca binária:\n" );
$time = microtime( true );
$tree->search( $toFind );
$time = microtime( true ) - $time;
$ttime += $time;

printf( "Tempo para encontrar %d na árvore: %f\n" , $toFind , $time );
print( "----------------------------------------------------\n" );
}

printf( "Tempo total da lista..: %f\n" , $ltime );
printf( "Tempo total da árvore.: %f\n" , $ttime );

 

A saída foi:

 Busca linear:
Encontramos 5942 com 747 iterações
Tempo para encontrar 5942 na matriz: 0.003135

Busca binária:
Encontramos 5942 com 12 iterações
Tempo para encontrar 5942 na árvore: 0.000194
----------------------------------------------------

Busca linear:
Encontramos 584 com 781 iterações
Tempo para encontrar 584 na matriz: 0.003101

Busca binária:
Encontramos 584 com 10 iterações
Tempo para encontrar 584 na árvore: 0.000151
----------------------------------------------------

Busca linear:
Encontramos 3108 com 727 iterações
Tempo para encontrar 3108 na matriz: 0.002895

Busca binária:
Encontramos 3108 com 9 iterações
Tempo para encontrar 3108 na árvore: 0.000139
----------------------------------------------------

Busca linear:
Encontramos 1436 com 745 iterações
Tempo para encontrar 1436 na matriz: 0.002920

Busca binária:
Encontramos 1436 com 9 iterações
Tempo para encontrar 1436 na árvore: 0.000142
----------------------------------------------------

Busca linear:
Encontramos 5797 com 369 iterações
Tempo para encontrar 5797 na matriz: 0.001473

Busca binária:
Encontramos 5797 com 11 iterações
Tempo para encontrar 5797 na árvore: 0.000149
----------------------------------------------------

Busca linear:
Encontramos 5796 com 768 iterações
Tempo para encontrar 5796 na matriz: 0.003011

Busca binária:
Encontramos 5796 com 10 iterações
Tempo para encontrar 5796 na árvore: 0.000158
----------------------------------------------------

Busca linear:
Encontramos 8645 com 989 iterações
Tempo para encontrar 8645 na matriz: 0.004015

Busca binária:
Encontramos 8645 com 10 iterações
Tempo para encontrar 8645 na árvore: 0.000163
----------------------------------------------------

Busca linear:
Encontramos 9637 com 238 iterações
Tempo para encontrar 9637 na matriz: 0.001000

Busca binária:
Encontramos 9637 com 10 iterações
Tempo para encontrar 9637 na árvore: 0.000158
----------------------------------------------------

Busca linear:
Encontramos 7457 com 421 iterações
Tempo para encontrar 7457 na matriz: 0.001691

Busca binária:
Encontramos 7457 com 11 iterações
Tempo para encontrar 7457 na árvore: 0.000153
----------------------------------------------------

Busca linear:
Encontramos 6674 com 699 iterações
Tempo para encontrar 6674 na matriz: 0.002788

Busca binária:
Encontramos 6674 com 10 iterações
Tempo para encontrar 6674 na árvore: 0.000148
----------------------------------------------------
Tempo total da lista..: 0.026029
Tempo total da árvore.: 0.001555

Se tiver dado para compreender continuamos, se não, dá um toque que eu mostro o processo igual foi feito para a BST (com as bolinhas).

 

;)

[Suissa 1]

Fico show de bola a implementação e a explicação. Parabéns Neto!

[Herbert Hudson 0]

Fico show de bola a implementação e a explicação. Parabéns Neto!

 

Corcodo! ficou excelente kra!

[Bruno Augusto 417]

Impressionante, tanto a implementação quanto a explicação.

 

Mas concorda comigo que isso é apenas metade da solução? Confesso que nunca havia ouvido falra em nada do que foi dito aqui, logo nem imaginava a solução seguindo essa lógica de pensamento.

 

Como ficaria a comparação dos canais de cor nessa árvore? Eu sei que existem "apenas" pouco menos de 360 "cores reais" (de 0 à 360° - sendo que começa e termina em vermelho)

 

Sei também que a Saturação e a Intensidade (agora tenho o algoritimo :D ) controlam as variações dessas cores mas existem um ponto pendente.

 

Não lembro onde eu comentei que uma cor pura precisa de 100% de Saturação e 50% de Luminosidade (ou o equivalente em Intensidade, que ao invés de variar de 0 à 100%, varia de 0 à 255).

 

Com isso, uma conversão de 0...360 (Hue, em loop), 100 (S), 50 (L) em RGB, percebe-se que existem apenas: Vermelho, Laranja, Amarelo, Verde, Ciano, Azul, Roxo, Rosa e Vermelho de novo.

 

As outras cores vêm dos "desequilíbrios" em S e L (ou I).

 

Como a AVL Tree trataria isso para, por exemplo, encontrar um marrom, que apesar de desde a pré-escola sabermos que é uma mistura de vermelho e verde, na realidade, é um descendente de vermelho?

[Evandro Oliveira 331]

Bruno, você já tem a composição das cores que 'te servem' e das cores 'a verificar'??

 

Notou que a montagem 0xRGB é, na verdade uma progressão linear numérica em hexadecimal?

 

Você pode montar a sua árvore com os valores 'que servem' e utilizá-los em busca hexadecimal.

 

Em forma decimal, decompomos as cores em seus 3 fatores de 0-255 -> X,X,X

 

Analogamente em forma hexadecimal, a composição também segue a mesma regra, 0-FF -> X,X,X

 

A diferença é que não existe 256 na decomposição d, mas 256 convertido em h nos remete a uma cor válida -> 000100

 

Aplicando os conceitos (do tópico) a essa funcionalidade, fica fácil encontrar a cor mais próxima sem sequer precisar entender os conceitos de HSV/L

 

Nota: A funcionalidade é de igual valor para endereços IPv4