0

我正在使用大约 15,000 个节点并尝试从它们构建层次结构。节点不能以任何方式排序，每个节点都可以有无限数量的孩子——但父母总是会在他们的孩子之前被喂给这个函数。我的代码适用于 N 的小值，但最终超过服务器上的最大执行时间 N>2,000。我不确定是否有更好的方法来做到这一点，但这就是我所拥有的：

function insertNode(&$treeNode, $insertNode) {
    if($insertNode['DEPTH'] <= $treeNode['DEPTH']) return false; 
    if($treeNode['ID'] == $insertNode['PARENT_ID']) {
        $treeNode['CHILDREN'][] = $insertNode;
        $treeNode['CHILD_COUNT']++;
        return true;
    }
    else {
        foreach($treeNode['CHILDREN'] as $key=>$value) {
            $found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
            if($found) {
                $treeNode['CHILD_COUNT']++;
                return true;
            }
        }
    }
}

我现在最好的解决方案是将递归限制为仅构建几千个深度节点，然后在 Javascript 中为每个底部节点调用脚本，直到树真正完成。不过，我宁愿一口气把它全部搞定。

4

1 回答 1

0

我自己想通了。关键是：

父母总是会在孩子之前被喂饱

我使用的 SQL 查询（一个 Oracle CONNECT BY）直接在他们的直系祖先之后打印出每个孩子（以及他们所有的孩子）。例如，数据集：

|id|parent_id|
|A-|---------|
|C-|-----A---|
|Bb|-----B---|
|B-|-----A---|

将由查询传递为：

|id|parent_id|
|A-|---------|
|B-|-----A---|
|Bb|-----B---|
|C-|-----A---|

我按顺序循环遍历查询的每一行，然后为每一行调用递归插入函数。在每个函数调用中，我使用foreach循环对树中当前节点的每个子节点进行递归调用，直到找到该行的父节点，这里：

foreach($treeNode['CHILDREN'] as $key=>$value) {
    $found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
    if($found) {
        $treeNode['CHILD_COUNT']++;
        return true;
    }
}

但是，因为每个孩子的父母始终是其深度的最新插入项（因为它是我循环通过其深度的最后一行），所以父母被保证是树最右边分支中最右边的孩子。循环不仅是不必要的，而且实际上是我能做的最糟糕的事情——它从左到右循环遍历子代，但父代始终是最右边分支的最右边的子代，函数将循环的最后一项通过和遍历。（那是什么，O(N^2)？）难怪它超时了。

我把foreach它删掉并用一个end()电话代替了它。

$lastChild = $treeNode['CHILDREN'];
end($lastChild);
$key = key($lastChild);
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode);
if($found) {
    $treeNode['CHILD_COUNT']++;
    return true;
}

这大大缩短了执行时间，因为它以指数方式减少了函数每行递归调用自身的次数。它现在在大约 6 秒内工作 N=15,000（之前它的上限是 30 秒，低至 N=2,000）。不需要节点数上限或通过 JS 延迟加载。

于 2013-08-01T18:13:02.563 回答