php:algoritmo de estrutura de árvore

Autor：Eve Cole Data da Última Atualização：2009-06-02 18:07:31

Postado novamente por Joy Murakami, já li este artigo antes e ele é explicado com bastante clareza.
Encontraremos esse problema em muitos lugares, como classificação de produtos, fóruns estruturados em árvore de vários níveis, listas de discussão, etc.: Como armazenar dados estruturados de vários níveis?

Em aplicativos PHP, o armazenamento de dados de back-end geralmente é um banco de dados relacional, que pode salvar grandes quantidades de dados e fornecer serviços eficientes de recuperação e atualização de dados. No entanto, a forma básica de dados relacionais é uma tabela cruzada, que é uma estrutura plana. Se você deseja armazenar uma estrutura de árvore multinível em um banco de dados relacional, precisará realizar um trabalho de tradução razoável. A seguir, discutirei com vocês o que vi e ouvi e algumas experiências práticas.

Existem basicamente dois métodos de design comuns para armazenar dados hierárquicos em bancos de dados simples:

modelo de lista de adjacências
Algoritmo modificado de passagem de árvore de pré-ordem
Não sou especialista em informática e não aprendi nada sobre estruturas de dados, então traduzi esses dois nomes literalmente.

Essas duas coisas podem parecer assustadoras, mas na verdade são muito fáceis de entender. Aqui eu uso um diretório de alimentos simples como nossos dados de exemplo. Nossa estrutura de dados é assim:

Food: Food
Fruta: fruta
Vermelho: vermelho
Cereja:cereja
Amarelo: amarelo
Banana:banana
Carne: Carne
Carne:carne
Carne de porco:

O modelo de lista de adjacência

de carne de porco

é um modelo que usamos com frequência e foi introduzido em muitos tutoriais e livros. Descrevemos toda a estrutura da árvore por meio de uma tabela plana, adicionando um atributo pai a cada nó para representar o nó pai deste nó. Seguindo este princípio, os dados do exemplo podem ser transformados na seguinte tabela:

Exibindo uma árvore multinível Se precisarmos exibir uma estrutura multinível, precisaremos de uma função recursiva.

<?php
// $parent é o pai dos filhos que queremos ver
// $level aumenta quando nos aprofundamos na árvore,
// usado para exibir uma bela

função de árvore recuada display_children($parent, $level)
{
// Obtém todos os nós filhos de um nó pai $parent
$resultado = mysql_query('SELECIONE nome DA árvore '.
'WHERE parent="'.$parent.'";');

// Exibe cada nó filho.
while ($linha = mysql_fetch_array($resultado))
{
//Recua o nome do nó
echo str_repeat(' ',$level).$row['name']."n"

//Chame esta função novamente para exibir os nós filhos do nó filho

display_children($row['name'], $level+ 1);
}
}
?>
Usar esta função no nó raiz (Food) de toda a estrutura pode imprimir toda a estrutura da árvore multinível. Como Food é o nó raiz e seu nó pai está vazio, chame: display_children('',0). exibirá o conteúdo de toda a árvore:

Comida
Fruta
Vermelho
Cereja
Amarelo
Banana
Carne
Carne bovina
Carne de porco
Se você quiser exibir apenas uma parte de toda a estrutura, como a parte da fruta, você pode chamá-la assim:

display_children

('Fruit',0);

para qualquer nó. Por exemplo, o caminho de Cherry é “Comida > Fruta > Vermelho”. Para obter esse caminho, precisamos começar do nível mais profundo "Cherry", consultar para obter seu nó pai "Red" e adicioná-lo ao caminho, e então consultar o nó pai de Red e adicioná-lo ao caminho. , e assim por diante até o nível superior "Comida"

<?php
// $node é o nó mais profundo
função get_path($nó)
{
// Consulta o nó pai deste nó
$resultado = mysql_query('SELECIONE pai FROM árvore '.
'WHERE nome="'.$node.'";');
$row = mysql_fetch_array($result);

// Use um array para salvar o caminho
$path = array();

// Se não for o nó raiz, continue a consultar para cima
// (O nó raiz não possui nó pai)
if ($row['parent']!='')
{
// a última parte do caminho para $node, é o nome
//do pai de $node
$path[] = $row['parent'];

// devemos adicionar o caminho ao pai deste nó
//para o caminho
$caminho = array_merge(get_path($row['parent']), $path);
}

// retorna o caminho
retornar $caminho;
}
?>
Se você usar esta função para "Cherry": print_r(get_path('Cherry')), você obterá um array como este:

Variedade
(
[0] => Comida
[1] => Fruta
[2] => Vermelho
)
Como imprimi-lo no formato desejado depende de você.
Desvantagens: Este método é muito simples, fácil de entender e fácil de usar. Mas existem algumas desvantagens. Principalmente porque a velocidade de execução é muito lenta, pois cada nó requer uma consulta ao banco de dados e, quando a quantidade de dados é grande, muitas consultas são necessárias para completar uma árvore. Além disso, devido à necessidade de operações recursivas, cada nível de recursão precisa ocupar alguma memória, de modo que a eficiência de utilização do espaço é relativamente baixa.

Agora vamos dar uma olhada em outro método que não usa cálculos recursivos e é mais rápido. Este é o algoritmo de passagem de árvore de pré-ordem modificado. Você pode ter menos exposição a esse método e não é como o acima quando você o usa. na primeira vez, o método é fácil de entender, mas como não usa algoritmos de consulta recursivos, possui maior eficiência de consulta.

Primeiro, desenhamos os dados multiníveis no papel da seguinte maneira, escrevemos 1 no lado esquerdo do nó raiz Comida, depois continuamos descendo a árvore, escrevemos 2 no lado esquerdo de Fruta e continuamos a nos mover ao longo de toda a árvore As arestas rotulam cada nó com números à esquerda e à direita. O último número é 18 marcado à direita de Comida. Na imagem abaixo você pode ver toda a estrutura multinível marcada com números. (Não entendeu? Aponte os números com os dedos e conte de 1 a 18 e você entenderá. Se ainda não entender, conte novamente e tenha cuidado ao mover os dedos).
Esses números indicam o relacionamento entre cada nó. Os números de “Vermelho” são 3 e 6, que são os nós descendentes de “Comida” 1-18. Da mesma forma, podemos ver que todos os nós com valor à esquerda maior que 2 e valor à direita menor que 11 são descendentes de "Fruta" 2-11

Desta forma, toda a estrutura da árvore pode ser armazenada no banco de dados através dos valores esquerdo e direito. Antes de continuar, vamos dar uma olhada na tabela de dados compilada abaixo.

+------------+-----+-----+
| nome |
+------------+-----+-----+
Fruta 2 |
|
Cereja 4 |
Amarelo 7 |
|
+------------+-----+-----+
Veja, você pode obter todos esses nós com apenas uma consulta. Para poder exibir toda a estrutura da árvore como a função recursiva acima, também precisamos classificar essa consulta. Classifique pelo lvalue do nó:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
A questão restante é como exibir o recuo hierárquico.

<?php
função display_tree($root)
{
//Obtém os valores esquerdo e direito do nó raiz
$resultado = mysql_query('SELECT lft, rgt FROM tree '.'WHERE nome="'.$root.'";');
$row = mysql_fetch_array($result);

// Prepara uma pilha de rvalue vazia
$right = array();

// Obtém todos os nós descendentes do ponto raiz
$resultado = mysql_query('SELECIONE nome, lft, rgt FROM árvore '.
'ONDE lft ENTRE '.$row['lft'].'
$row['rgt'].' ORDER BY lft ASC;');

// Exibe cada linha
while ($linha = mysql_fetch_array($resultado))
{
// só verifica a pilha se houver uma
if (contagem($direita)>0)
{
// Verifica se devemos mover o nó para fora da pilha
while ($right[count($right)-1]<$row['rgt'])
{
array_pop($direita);
}
}

// Recua o nome do nó.

echo str_repeat(' ',count($right

)

).$row['name']."n";

$direita[] = $linha['rgt'];
}
}
?>
Se você executar a função acima, obterá o mesmo resultado da função recursiva. Acontece que nossa nova função pode ser mais rápida porque existem apenas 2 consultas ao banco de dados. É mais fácil saber o caminho de um nó. Se quisermos saber o caminho do Cherry, usamos seus valores esquerdo e direito 4 e 5 para fazer uma consulta.

SELECIONE o nome DA árvore WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
Isso lhe dará o seguinte resultado:

+----------------+
| nome |
+----------------+
Alimentos |
Fruta |
| Vermelho |
+----------------+
Então, quantos nós descendentes um determinado nó possui? É muito simples, o número total de descendentes = (rvalor - valor esquerdo - 1)/2 descendentes = (direita - esquerda - 1) / 2 Não acredita? Faça você mesmo as contas. Usando esta fórmula simples, podemos calcular rapidamente que o nó "Fruta 2-11" possui 4 nós descendentes, enquanto o nó "Banana 8-9" não possui nós descendentes, o que significa que não é um nó pai.
Incrível, certo? Embora eu tenha usado esse método muitas vezes, ainda é incrível cada vez que o faço.

Este é realmente um bom método, mas existe alguma maneira de nos ajudar a criar uma tabela de dados com valores à esquerda e à direita? Aqui está outra função para apresentar a você. Esta função pode converter automaticamente a tabela com nome e estruturas pai em uma tabela de dados com valores esquerdo e direito.

<?php
function reconstruir_tree($parent, $left) {
// o valor certo deste nó é o valor esquerdo + 1
$right = $left+1;

// obtém todos os filhos deste nó
$resultado = mysql_query('SELECIONE nome DA árvore '.
'WHERE parent="'.$parent.'";');
while ($linha = mysql_fetch_array($resultado)) {
// execução recursiva desta função para cada
// filho deste nó
// $right é o valor correto atual, que é
// incrementado pela função reconstruir_tree
$direita = reconstruir_tree($linha['nome'], $direita);
}

// temos o valor esquerdo e agora que processamos
// os filhos deste nó também sabemos o valor correto
mysql_query('UPDATE árvore SET lft='.$left.', rgt='.
$right.' WHERE name="'.$parent.'";');

// retorna o valor certo deste nó + 1
retornar $direito+1;
}
?>
Claro, esta função é uma função recursiva. Precisamos executar esta função a partir do nó raiz para reconstruir uma árvore com valores à esquerda e à direita

reconstruir_tree('Food',1);
Esta função parece um pouco complicada, mas sua função é a mesma de numerar manualmente a tabela, que é converter a estrutura tridimensional multicamadas em uma tabela de dados com valores à esquerda e à direita.

Então, como adicionamos, atualizamos e excluímos um nó para tal estrutura? Geralmente, há duas maneiras de adicionar um nó:

manter o nome original e a estrutura pai, usar o método antigo para adicionar dados aos dados e usar a função reconstruir_tree para renumerar toda a estrutura após cada dado ser adicionado.
Uma abordagem mais eficiente é alterar todos os valores à direita do novo nó. Por exemplo: queremos adicionar uma nova fruta “Morango” que se tornará o último nó filho do nó “Vermelho”. Primeiro precisamos abrir algum espaço para isso. O valor direito de "Vermelho" deve ser alterado de 6 para 8, e os valores esquerdo e direito de "Amarelo 7-10" devem ser alterados para 9-12. Por analogia, podemos saber que se você quiser abrir espaço para novos valores, você precisa adicionar 2 a todos os nós com valores esquerdo e direito maiores que 5 (5 é o valor certo do último nó filho de "Vermelho" ). Portanto, realizamos operações de banco de dados como esta:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE árvore SET lft=lft+2 WHERE lft>5;
Isso libera espaço para o valor recém-inserido Agora você pode criar um novo nó de dados no espaço liberado. Seus valores esquerdo e direito são 6 e 7, respectivamente

. 'Morango';

Vamos fazer outra consulta e ver! Que tal? Breve.
Ok, agora você pode projetar sua estrutura de banco de dados multinível de duas maneiras diferentes. O método usado depende inteiramente do seu julgamento pessoal, mas para estruturas com muitos níveis e um grande número, prefiro o segundo método. O primeiro método é mais fácil se o volume de consultas for pequeno, mas os dados precisarem ser adicionados e atualizados com frequência.

Além disso, se o banco de dados suportar, você também pode escrever reconstruir_tree() e a operação de liberação de espaço como uma função de gatilho no lado do banco de dados e executá-la automaticamente durante a inserção e atualização. adicionar novos nós. As instruções SQL se tornarão mais simples.
Método recursivo de classe
Postado por convidado em 31 de maio de 2004 - 9h18.
Escrevi um programa usando um método quase recursivo, que não é exatamente igual à recursão do artigo, e estou me preparando para transplantá-lo para o xoops:
http://dev.xoops.org/modules/xfmod/project/?ulink

sofreu estouro de memória, mas pretendo continuar a usar o método recursivo, só preciso continuar a melhorar e

espero ter a oportunidade de discutir

cms com você.
» responder a este comentário
Ou uma comparação dos dois métodos?
Postado por convidado em 2004, 17 de março - 20h30.
Estudei este artigo com atenção e achei que era muito benéfico, mas depois pensei sobre isso novamente e senti que havia um problema (por uma questão de memória, chamo o modo de diretório adjacente de método recursivo e a travessia de pré-classificação algoritmo de árvore que chamo de método de árvore de pré-classificação):

1. A maior diferença entre os dois métodos é que a recursão requer o uso de uma pilha durante a consulta, enquanto a árvore de pré-classificação requer metade dos nós (referindo-se à segunda metade de o nó inserido) ao atualizar os nós de atualizações. Embora você também tenha dito que se houver muitos nós e atualizações frequentes, a eficiência da árvore pré-classificada será reduzida e a recursão será melhor. Se houver muitos níveis de nós, em primeiro lugar, a recursão causará estouro de pilha e. além disso, a recursão em si não é muito eficiente e cada nível de recursão requer a operação do banco de dados, o efeito geral não será o ideal. Minha abordagem atual é retirar todos os dados de uma vez e, em seguida, realizar operações recursivas no array, o que será melhor se puder ser melhorado ainda mais, um nó raiz ROOT pode ser adicionado a cada linha de registros (atualmente, apenas; nós pais adjacentes são registrados), de modo que a eficiência ao pesquisar o ramo da árvore será maior, e também será muito conveniente ao atualizar a árvore, o que deve ser a melhor maneira.

2. Melhore o método recursivo No artigo, ao calcular os valores esquerdo e direito dos nós da árvore pré-classificados, um método de travessia é realmente usado. A pilha é substituída por uma matriz, e o push e o pop. são implementados manualmente; se este método for referenciado no algoritmo recursivo, se você usar uma matriz em vez da pilha ao executar a recursão, também poderá melhorar a eficiência da recursão.

3. Simultaneidade Se a simultaneidade for levada em consideração, especialmente ao atualizar a árvore, o método de atualização das informações do nó em uma grande área da árvore pré-classificada requer atenção extra ao uso de mecanismos de bloqueio e transação para garantir. consistência dos dados.

4. No caso de vários nós raiz ou múltiplos nós pais, neste caso, obviamente não é uma árvore binária padrão ou uma árvore multi-fork. O algoritmo de árvore pré-classificado precisa ser bastante melhorado para se adaptar, e o método recursivo. é aplicado livremente, portanto, neste caso, a recursão é mais adaptável. É claro que isso ocorre porque o método recursivo é uma forma de lista vinculada. Árvores e gráficos podem ser expressos por listas vinculadas e, claro, é altamente adaptável.

5. Intuitivo Se você observar diretamente os dados armazenados no banco de dados sem operação do programa, é óbvio que os dados armazenados no modo recursivo são mais intuitivos, enquanto os dados na árvore pré-classificada são difíceis de ler diretamente (para hierárquico). relacionamentos). Isso é importante na troca de dados. Terá algum impacto?

De modo geral, eu pessoalmente prefiro usar métodos recursivos, mas sempre me preocupei com o impacto da recursão na eficiência. Felizmente, não fui exposto a níveis de classificação em grande escala. Usar matrizes em vez de pilhas recursivamente seria uma melhoria melhor. método. A árvore pré-classificada é um método eficiente para resolver árvores simples. Depois que você se acostumar com ela, deve ser muito bom, especialmente sua busca reversa do nó folha para o nó raiz é muito conveniente.

Lobo
www.fwolf.com
» responder a este comentário
Muito feliz em ver sua resposta
Postado por shuke em 2004, 18 de março - 5h47.
Estou muito feliz que você tenha lido este artigo com tanta atenção. Na verdade, este artigo foi publicado originalmente em sitepoint.com. Eu o traduzi, na esperança de apresentar alguns métodos aos amigos que desejam começar. Seu método também é muito bom, vou tentar se tiver chance. (Se você estiver interessado, por que não escrever seu método e código de implementação específico como um tutorial baseado no exemplo acima, para que todos possam imitá-lo com exemplos mais práticos) Se você tiver dúvidas sobre como salvar estruturas multiníveis no banco de dados Se você estão interessados em pesquisar, aqui estão outros dois bons links que podem ser usados como referência:
Apresentando os quatro métodos comuns de consulta única e script de classificação de array, acho que seu script deve ser melhor que isso.
Além disso, vi que você também usa o drupal. Ele também possui um recurso avançado chamado sistema de autenticação de usuário distribuído. Contanto que você se registre em qualquer site drupal, você pode fazer login para acessar outros sites drupal. Muito interessante.
Muitas felicidades!
» responder a este comentário
A construção de árvores usando loops foi implementada
Postado por convidado em 2004, 25 de março - 22h10.
Eu li todas as informações que você forneceu da última vez, mas para ser sincero, não há muitas novidades no primeiro artigo. Talvez eu não tenha entendido muito bem. O segundo artigo foi escrito em PHP3 e a estrutura do programa. não foi detalhado. Veja, muitas interseções de funções são usadas.
Acontece que eu precisava usar funções de usuário hierárquicas em um sistema, então anotei a travessia com base na ideia de um array e não tive tempo de resolver isso, então vou colocar aqui. para você dar uma olhada. O banco de dados é ADODB e o programa é extraído diretamente do sistema, espero que possa ser descrito claramente. Ele usa principalmente operações de array poderosas do PHP e usa loops para realizar recursão. O comentário é um método semelhante, mas o tempo de processamento dos resultados é diferente.

<?php
/**
* Mostrar lista
* @acessar público
*/
função ListaDisp()
{
//Modo de exibição sem recuo
// $this->mIsDispListIndex = true;
// echo('<a href="?action=new&part=role">Adicionar nova função</a> '); ">Adicionar nova função</a> ');"
//
// $this->mListTitle = 'Lista de funções de usuários';
// $this->SetDataOption('lista');
//
// $this->SetQueryTable( array($this->mTableUserRole) );
//
// //Ordem de consulta
// $this->SetQueryOrder( 'asc', $this->mTableUserRole, 'sequence' );
//
// $this->Query('lista');
// parent::DispList();

// //Outro método de exibição, usando um array como pilha, A: Salve a função ao empurrar na pilha e exclua a fonte após empurrar.
// $this->CheckProperty('mrDb');
// $this->CheckProperty('mrSql');
// $this->mrSql->Select('role, title, parent');
// $this->mrSql->From($this->mTableUserRole);
// $this->mrSql->Orderby('parent, sequência');
// $this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
// if (0 < contagem($this->mRs))
// {
// $source = & $this->mRs->GetArray();
//$pilha = array(''); //pilha
// $stacki = array(-1); //Corresponde à pilha, registra o nível dos dados na pilha na árvore
// $alvo = array();
// while (0 < contagem($stack))
// {
// $item = array_shift($stack);
// $lev = array_shift($stacki);
// se (!empty($item))
// {
// //Coloque os dados processados no array de destino aqui
// array_push($target, str_repeat(' ', $lev). $item);
// //$s1 = str_repeat(' ', $lev) .
// }
// $del = array(); //Nó a ser excluído de $source
// $ar = array(); //Nós que precisam ser adicionados à pilha
// foreach ($source as $key=>$val)
// {
// //Encontre nós filhos correspondentes
// se (vazio($item))
// {
// $find = vazio($source[$key]['parent']);
// }
//outro
// {
// $find = ($item == $source[$key]['parent']);
// }
//se ($encontrar)
// {
// array_unshift($ar, $source[$key]['role']);
// $del[] = $chave;
// }
// }
// foreach ($ar como $val)
// {
//array_unshift($stack, $val);
//array_unshift($stacki, $lev + 1);
// }
// foreach ($del como $val)
// {
// unset($source[$val]);
// }
// echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
// }
//debug_array();
// }
//outro
// {
// echo('<center>Nenhum dado recuperado</center>');
// }

//Outro método de exibição, usando um array como pilha, B: Salve o índice do array ao empurrar a pilha, retire-o da pilha e exclua a fonte após o uso.
$this->CheckProperty('mrDb');
$this->CheckProperty('mrSql');
$this->mrSql->Select('role, title, parent');
$this->mrSql->From($this->mTableUserRole);
$this->mrSql->Orderby('pai, sequência');
$this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
if (!empty($this->mRs) && !$this->mRs->EOF)
{
$source = & $this->mRs->GetArray();
$pilha = array(-1);
$stacki = array(-1); //Corresponde à pilha, registra o nível dos dados na pilha na árvore
$alvo = array();
while (0 <contagem($pilha))
{
$item = array_shift($stack);
$lev = array_shift($stacki);
se (-1! = $item)
{
//Coloque os dados processados no array de destino aqui
$s1 = str_repeat(' ', $lev) '<a href="?action=disp&part=role&role=' . $source[$item]['role'] . '">' . ['título'] '</a>';
$s2 = '<a href="?action=edit&part=role&role=' . $source[$item]['role'] . '">Editar</a> <a href="?action=delete&part=role&role= ' . $source[$item]['role'] .
array_push($alvo, array($s1, $s2));
}
$del = array(); //Nó a ser excluído de $source
$ar = array(); //Nós que precisam ser adicionados à pilha
foreach ($fonte como $key=>$val)
{
//Encontra nós filhos correspondentes
se (-1 == $item)
{
$find = vazio($source[$key]['parent']);
}
outro
{
$find = ($source[$item]['role'] == $source[$key]['parent']);
}
se($encontrar)
{
array_unshift($ar, $chave);
}
}
foreach ($ar como $val)
{
array_unshift($pilha, $val);
array_unshift($stacki, $lev + 1);
}
//Exclui da fonte
não definido($fonte[$item]);
//echo(implode(', ', $stack) . ' ' . implode(', ', $stacki) . ' ' . implode(', ', $target) . ' ');
}
//Saída
echo('<a href="?action=new&part=role">Adicionar nova função</a> ');
array_unshift($target, array('role', 'operação'));
$this->CheckProperty('mrLt');
$this->mrLt->SetData($target);
$this->mrLt->mListTitle = 'Lista de funções de usuários';
$this->mrLt->mIsDispIndex = false;
$this->mrLt->Disp();
}
outro
{
echo('<center>Nenhum dado recuperado</center>');
}
} //fim da função DispList
?>