3

この二分木が与えられた場合（実際には、二分木はランダムで動的である可能性があります。これは単なる例です...）：

二分木の画像のリンクを参照してください：二分木の例

これは与えられた事実です：

  1. すべてのノードは、下から上に（そしてもちろん上から下にも）トラバースできるように、それらの父親に接続されています。
  2. すべてのノードは、左右の部分に子孫がいくつあるかに関する情報を保持しています。

問題はこれです：レベル2のノードの総数を計算する方法を見つける必要があります（実際には、どのレベルでも、今のところはレベル2に集中しましょう）。明らかに、二分木の構造を事前に知っていれば答えは3ですが、このイメージはなく、与えられた事実だけがあると仮定します。

ここでのもう1つの問題は、ルートではなくレベル2（ターゲットレベル）にあるノードから開始することです。この例では、NODEFを選択しました。

幅優先探索を使用するのが簡単な解決策であることは知っていますが、ノードを読み取るたびにデータベースからクエリを実行するため、時間がかかりすぎることがわかります。

より実用的なアプローチを探しています。しかし、与えられたデータが不十分であるためにこの問題を解決することが「不可能」である場合、これを解決するために他にどのようなデータを与えるべきかを教えてください。可能であれば評価します。

ちなみに私はPHPとMySQLを使ってウェブサイトを作っています。しかし、プログラミングスニペットやコードではなく、アルゴリズムのような、ソリューションの概念または説明だけが必要です...

誰かが私に答えてくれることを願っています...どうもありがとうございました！

4

7 に答える 7

2

「幅優先探索」はそれを行う方法です。ただし、使用したくない場合は、ノードに兄弟へのポインターを含めることをお勧めします。通常、この種のクエリを実行する必要がある場合、それは大きな節約になります。

編集：

ノードを非正規化し、すべてのノードの兄弟とレベルをテーブルに格納できる場合は、問題なくクエリを実行できます。

SELECT * FROM nodes where level=2
于 2011-09-17T16:59:39.390 に答える
1

DBMSのツリーの場合、WITH RECURSIVE cte-idiomを使用して、適切な再帰レベルでクリップできます（==指定されたノードの再帰レベル。おそらく別の再帰副選択が必要になります）

編集:(追加されたコード）

-- the test table
DROP table tree CASCADE;
CREATE table tree
    ( id CHAR(1) NOT NULL PRIMARY KEY
    , pa CHAR(1) REFERENCES tree(id)
    , le CHAR(1)     REFERENCES tree(id)
    , ri CHAR(1) REFERENCES tree(id)
    );

-- generate some data
INSERT INTO tree (id, pa, le, ri) VALUES
      ( 'a', NULL, 'b', 'c' )
    , ( 'b', 'a', 'd', 'e' )
    , ( 'c', 'a', 'f', NULL )
    , ( 'd', 'b', 'g', NULL )
    , ( 'e', 'b', NULL, 'h' )
    , ( 'f', 'c', NULL, 'i' )
    , ( 'g', 'd', NULL, NULL )
    , ( 'h', 'e', NULL, NULL )
    , ( 'i', 'f', NULL, NULL )
    ;
-- a room with a view
CREATE VIEW reteview AS (
    WITH RECURSIVE re AS (
        SELECT 0 AS lev,id, pa, le, ri FROM tree
        WHERE pa IS NULL
        UNION
        SELECT 1+re.lev AS lev
        , tr.id,  tr.pa,  tr.le,  tr.ri
            FROM tree tr, re
            WHERE re.id = tr.pa
        )
    SELECT * FROM re
    );

/* EXPLAIN ANALYZE */ -- SELECT * FROM reteview ;

/* EXPLAIN ANALYZE */ SELECT re0.*
    FROM reteview re0
    , reteview re1
    WHERE re1.id = 'f'
    AND re0.lev <= re1.lev
    ;

結果：

 lev | id | pa | le | ri 
-----+----+----+----+----
   0 | a  |    | b  | c
   1 | b  | a  | d  | e
   1 | c  | a  | f  | 
   2 | d  | b  | g  | 
   2 | e  | b  |    | h
   2 | f  | c  |    | i
(6 rows)

クエリプラン（Postgres 9.01）

                                                                   QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=949.93..2773.55 rows=35167 width=36) (actual time=0.159..0.337 rows=6 loops=1)
   Join Filter: (re.lev <= re1.lev)
   ->  CTE Scan on re  (cost=474.97..566.71 rows=4587 width=36) (actual time=0.034..0.151 rows=9 loops=1)
         CTE re
           ->  Recursive Union  (cost=0.00..474.97 rows=4587 width=36) (actual time=0.021..0.129 rows=9 loops=1)
                 ->  Seq Scan on tree  (cost=0.00..23.10 rows=7 width=32) (actual time=0.012..0.014 rows=1 loops=1)
                       Filter: (pa IS NULL)
                 ->  Hash Join  (cost=2.28..36.01 rows=458 width=36) (actual time=0.018..0.022 rows=2 loops=4)
                       Hash Cond: (tr.pa = re.id)
                       ->  Seq Scan on tree tr  (cost=0.00..23.10 rows=1310 width=32) (actual time=0.001..0.003 rows=9 loops=4)
                       ->  Hash  (cost=1.40..1.40 rows=70 width=12) (actual time=0.003..0.003 rows=2 loops=4)
                             Buckets: 1024  Batches: 1  Memory Usage: 1kB
                             ->  WorkTable Scan on re  (cost=0.00..1.40 rows=70 width=12) (actual time=0.001..0.002 rows=2 loops=4)
   ->  Materialize  (cost=474.97..578.52 rows=23 width=4) (actual time=0.013..0.018 rows=1 loops=9)
         ->  Subquery Scan on re1  (cost=474.97..578.40 rows=23 width=4) (actual time=0.111..0.157 rows=1 loops=1)
               ->  CTE Scan on re  (cost=474.97..578.17 rows=23 width=36) (actual time=0.110..0.156 rows=1 loops=1)
                     Filter: (id = 'f'::bpchar)
                     CTE re
                       ->  Recursive Union  (cost=0.00..474.97 rows=4587 width=36) (actual time=0.008..0.135 rows=9 loops=1)
                             ->  Seq Scan on tree  (cost=0.00..23.10 rows=7 width=32) (actual time=0.002..0.008 rows=1 loops=1)
                                   Filter: (pa IS NULL)
                             ->  Hash Join  (cost=2.28..36.01 rows=458 width=36) (actual time=0.021..0.024 rows=2 loops=4)
                                   Hash Cond: (tr.pa = re.id)
                                   ->  Seq Scan on tree tr  (cost=0.00..23.10 rows=1310 width=32) (actual time=0.001..0.004 rows=9 loops=4)
                                   ->  Hash  (cost=1.40..1.40 rows=70 width=12) (actual time=0.004..0.004 rows=2 loops=4)
                                         Buckets: 1024  Batches: 1  Memory Usage: 1kB
                                         ->  WorkTable Scan on re  (cost=0.00..1.40 rows=70 width=12) (actual time=0.001..0.001 rows=2 loops=4)
 Total runtime: 0.764 ms
(28 rows)
于 2011-09-17T17:10:18.777 に答える
1

オプションは、phpでテーブル全体をロードし、配列ツリーを作成することです。行数が多い場合（100k以上）、テーブルの読み込みが完了する前にプロセスを開始できますが、それを制御するにはさらに多くのコードが必要です。

または、トリガーを使用して各ノードに結果を保存できます。

編集：少し考えて、さまざまな答えやコメントを読んだ後。最善の選択肢は、ソリューションを分割することだと思います。

  1. 2つの列（level、nbNodes）を持つテーブルnodesPerLevelを作成します。
  2. 各ノードの挿入/削除時にトリガーを作成します。これにより、この新しいテーブルの対応するレベルに1が加算/減算されます。
  3. 結果が必要な場合は、select sum(nbNodes) from nodesPerLevel where level >= ?
于 2011-09-17T17:07:43.053 に答える
0

ノードはデータベースに保存されているため、最善の解決策は次のようなSQLクエリである可能性があります（構文が間違っている可能性があります）。

select count(third.id) from node as first, node as second, node as third where first.id =`your top node id`  and second.parent = first.id and third.parent =  second.id

このようなクエリを実行すると、ノードごとにDBに余分にアクセスすることなくノードが提供されます。ただし、データベースにはコストがかかる場合があります（データベースとノードの数によって異なります）。ノードのレベルをノード自体に格納することもできます。これにより、クエリがより簡単になり、必要なリソースが少なくなります。

于 2011-09-17T17:11:22.523 に答える
0

ルートから完全にレベル2までツリーを読み取り、インスタンスをカウントする以外の唯一のことは、同じレベルのインスタンス間にリレーションフィールドを設定するか、データが揮発性が高すぎてそのアプローチのパフォーマンスを向上できない場合は、短い実装を行うことです。 -同じレベルのノードを迅速に識別できる、タイミングはあるが高速な（メモリ？）キャッシング システム。

于 2011-09-17T17:06:52.810 に答える
0

これを行う最も簡単な方法は

1.木のすべてのパスを見つける

       50
     /    \
   30      60
 /   \    /  \
10   20  55   70

パスは次のとおりです。

50-30-10
50-30-20
50-60-55
50-60-70

2.別々の配列に格納します。

3.各配列の k 番目の要素にアクセスします。

すべてのパスを見つけるための sudo コード:

Inorder(root)
{
 //do the required null checks
         if(root==null)
            return

  1.     PushOnStack(root->info)  

  2.     Inorder(root->left)

  3.     peekAllStackElement (read all the elements in stack and store in array an         reverse)

  4.     PopFromStack(root->info)         

  5.     Inorder(root->right)

 }
于 2013-09-13T18:57:39.700 に答える