4

pathツリーの右端のノードを見つけるために、マテリアライズド パス ツリーのテキスト フィールドで並べ替えることは可能ですか? たとえば、django-treebeard の を使用するこの python 関数を考えてみましょうMP_Node:

def get_rightmost_node():
    """Returns the rightmost node in the current tree.

    :rtype: MyNode
    """
    # MyNode is a subclass of django-treebeard's MP_Node.
    return MyNode.objects.order_by('-path').first()

私のすべてのテストから、期待どおりの結果が得られたようですが、それを証明するための計算方法がわかりません。そして、具体化されたパスツリーでこの操作を実行することに関する情報は見つかりませんでした。

Treebeard の実装では、パスに区切り記号がないため、パスは 、 、 などのように0001なり00010001ます000100010012。

4

4 に答える 4

4

簡単な答え: いいえ。

これは、コメントで説明した問題を示すSQLFiddleです。

この簡単なセットアップの場合:

id, path
1,  '1'
2,  '1\2'
3,  '1\3'
4,  '1\4'
5,  '1\5'
6,  '1\6'
7,  '1\7'
8,  '1\8'
9,  '1\9'
10, '1\10'

単純な並べ替えで右端の葉 ( ) を取得しようとするid = 10と失敗します。

SELECT TOP 1
  id,
  path
FROM hierarchy
ORDER BY path DESC

戻り値：

id, path
9,  1\9

pathはテキストベースの列であるため、降順で並べ替えられます (フィドルの 2 番目のクエリの結果を参照してください)1\10。 1\9

深さと経路の長さの追跡を開始したとしても、これらは一般的に安価で追いつきやすいものですが、次のような経路を取得することは完全に可能です。

path       depth  length
12\3\11\2  4      9
5\17\10\1  4      9

それでも正しくソートされません。

数字の代わりに文字を使用している場合でも、問題の範囲が 10 番目ではなく 26 番目の子に押し出されるだけです。

文字を使用した SQLFiddle

私はネストされたセットと隣接リストと同様に具体化されたパス操作に精通しておらず、django の経験がないため、私が知らない方法がある場合は他の人に委ねますが、ほぼ確実にそうしなければならないでしょう列に対して何らかの解析を実行して、path一貫して正しいリーフを取得します。

編集 - 並べ替えが有効な解決策であるかどうかという問題に対処した後、少し議論して問題を少し考えた後、他の潜在的な解決策に関する追加のメモを次に示します。

- 「右端」は、ノードが 3 つ以上の子を持つことができる場合のあいまいな用語です (つまり、ツリーはバイナリ ツリーではありません)。ノードに 10 個の子がある場合、どれが親の左側にあり、どれが右側にありますか? 問題の解決策を定義する前に、この条件を定義する必要があります。

-問題空間に対して「右端」が適切に定義されたら、右端のノードが必ずしもツリーの最下位レベルにあるとは限らないことを理解してください。

        1
       / \
    1\1   1\2 <= This is the rightmost node
    /
  1\1\1 <= This is the lowest node

-「一番右」が定義されると、単純なループを使用してプログラムで一番右のノードを見つけることができます。

//in pseudocode
function GetRightmostNode(Node startNode)
{
  Node currentNode = startNode;

  while(currentNode.RightChildren != null)
  {
    currentNode = maximum of currentNode.RightChildren;
  }

  return currentNode;
}

このループは、現在のノードの右側にある現在のノードの子を探します。存在する場合は、右端の子を選択して繰り返します。右側に子がないノードに到達すると、ツリー (またはサブツリー) の右端のノードをstartNodeルートとして見つけたので、現在のノードを返します。

于 2015-04-27T19:46:02.430 に答える
0

編集:ポール・グリフィンは、ノードが特定の値を下回ると想定していたため、私の答えは信頼できないと正しく指摘しました。これは、Denis de Bernardy の深さ関数に 2 つのスピンを組み込んだ、より良い試みです。

2 つの並べ替え条件を使用します。1 つは深さ用、もう 1 つは整数に変換された左端のノードの値用です。

SELECT path, 
       length(regexp_replace(path, '[^/]+', '', 'g')) as depth,
       regexp_replace(path, '^.*/', '')::int as last       
FROM test 
ORDER BY depth DESC, last DESC;

これにより、最も高い値を持つ最も深いノードが一番上に配置されます。

SQLフィドル

于 2015-04-30T19:21:08.293 に答える
-1

@Paulが説明した方法を少し変更して使用できます0。すべての数字の前に追加でき、各パスの長さを均一にすることができます。

ノードには、次のようにパスを割り当てることができます。

id |  path
-----------------
1  |  '01'
2  |  '01\01'
3  |  '01\02'
4  |  '01\03'
5  |  '01\04'
6  |  '01\04\01'
7  |  '01\04\02'
8  |  '01\04\03'
9  |  '01\05\01'
10 |  '01\05\02'
11 |  '01\05\03'
12 |  '01\05\04'

上記の例は、子ノードの最大数を持つノードの子ノードの数が 100 未満の場合に使用できます。

100 ～ 1000 の場合は、同様に追加でき0ます001\003\002\005。

次に、次のように最も正しいノード12を取得できます。

SELECT TOP 1 id
FROM tree
ORDER BY path DESC

ここでデモを見つけることができます。 デモ

于 2015-04-28T20:44:18.427 に答える