大きなバイナリツリーを保存する方法

binary-tree php
大きなバイナリツリーを保存する方法

大きなバイナリツリー(深さ数千)を格納する方法。 データベース、elem、parent、left_child、right_childを含むテーブルに保存しようとしましたが、このツリーの処理(計算、その一部の描画)が非常に遅いです。

どの方法をお勧めしますか? (計算はphpで行われます)。 XMLまたはjson(テキストファイル)またはいくつかのマトリックスに保存することでしょうか?

  3  2


ベストアンサー

配列または他の線形ストアを使用できます(例: 関係id→ node value)各ノードxが子2 * xおよび2 * x + 1を持つ方法で。 問題は、ツリーのバランスが取れていない場合、未使用のIDがあることです。

サンプル:

    2---4---8
   /   \   \9
1--     5---10
   \       \11
    3---6---12
       \   \13
        7---14
           \15

0


あなたが提案するように、XMLのようなものに書き込むのが最善のようです。 リロードしたいときにXMLに変換してから元に戻すのは簡単です。

0


私は次のような構造を使用します

id  parent  tree    slug    name    path    children
1   0       1       root    Root    ||          |5|
2   7       1       child-1 Child 1 |1-5-8-7|   |3|

クエリは線形であるため、巨大な深さのツリーをクエリするのは非常に簡単です。 各行にはもう少しデータがありますが、それにより高速になります。

たとえば、次のような簡単なクエリでサブツリー全体を取得できます。

$sql = 'SELECT * FROM `'.$this->_table_name.'` WHERE
            `path` LIKE "%-:parent-%"
            OR `path` LIKE "%|:parent-%"
            OR `path` LIKE "%-:parent|%"
            OR `path` LIKE "%|:parent|%"';

$result = $this->_db->custom_query($sql, array('parent' => $root->id));

そして、単純な関数で深度配列を作成します。

private function _build_tree(Node $root, $data)
    {
        $mapped_node = array(
            'node' => $root,
            'subnodes' => array()
        );

        if ( !empty($root->children) )
        {
            foreach( $root->children as $child )
            {
                if ( array_key_exists($child, $data) )
                {
                    $mapped_node['subnodes'][] = $this->_build_tree($data[$child], $data);
                }
            }
        }

        return $mapped_node;
    }

注意! 子とパスの列を取得したら、それらをPHPの配列に分割して、それらをより適切に操作できるようにします。

0


タイトルとURLをコピーしました