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是基于文本的列，所以1\10会排在降序之后（参见小提琴中第二个查询的结果）。 1\9

即使您开始跟踪通常便宜且易于跟上的深度和路径长度，也完全有可能获得如下路径：

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

仍然无法正确排序。

即使您使用字母而不是数字，这也只会将问题范围推到第 26 个孩子而不是第 10 个孩子：

SQLFiddle 使用字母

我对物化路径操作不像我对嵌套集和邻接列表那样熟悉，并且没有使用 django 的经验，所以如果有我不知道的方法，我会遵从其他人，但你几乎肯定必须对列执行某种解析path以始终获得正确的叶子。

编辑 - 解决了排序是否是有效解决方案的问题后，在经过一些讨论和思考问题后，这里有一些关于其他潜在解决方案的附加说明：

- 当节点可以有两个以上的子节点时，“最右边”是一个模糊的术语（即，树不是二叉树）。如果一个节点有 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 回答
3

是否可以通过物化路径树的路径文本字段进行排序以找到树的最右侧节点？

'/1/3/6/2'不。例如，如果节点路径的存储方式类似，请考虑：

/1
/1/3
/1/3/6/2
/1/3/6/5
/1/3/6/21
/1/40

请参阅 Paul 的回答，了解上述排序不起作用的原因。

然而，所有的希望并没有失去。如果您正在搜索“最右边的节点”，我假设您的意思是树中最深的节点，您可以简单地计算分隔符。例如：

select length(regexp_replace('/1/3/6/2', '[^/]+', '', 'g')) as depth;

如果您正在寻找最大值，请使用以下内容：

order by length(regexp_replace(path, '[^/]+', '', 'g')) desc

...或等效的python代码。索引选项包括索引相同的表达式，或将结果存储在单独的深度字段中并对其进行索引。

如果您仍然对 ID 的实际值感兴趣，上面的数字通常与 ID 对应，因此请使用该列进一步订购。如果它们不同，请使用不同的正则表达式提取最右边的数字，并将其转换为整数，以便自然地对它们进行排序 (1, 11, 2) 而不是按字典顺序 (1, 11, 2)：

select regexp_replace('/1/3/6/2', '^.+/', '')::int as value;
于 2015-05-01T14:19:57.307 回答
0

编辑：保罗格里芬正确地指出我的回答是不可靠的，因为它假设节点会低于某个值。这是一个更好的尝试，在 Denis de Bernardy 的深度函数上加入了两次旋转。

使用两种排序标准，一种用于深度，另一种用于最左侧节点转换为整数的值：

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

这会将具有最高值的最深节点放在顶部。

SQLFiddle

于 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 回答