我似乎无法弄清楚线程二叉树的顺序遍历是如何 O(N).. 因为你必须下降链接才能找到最左边的孩子，然后在你想要的时候通过线程返回将父级添加到遍历路径。那不是O（N ^ 2）吗？
谢谢！
问问题
462 次
2 回答
4
树的遍历（无论是否线程化）是 O(N)，因为从其父节点开始访问任何节点都是 O(1)。一个节点的访问由三个固定的操作组成：从父节点下降到节点，访问本身（在节点上花费时间），然后返回父节点。O(1 * N) 是 O(N)。
看它的终极方式是，树是一个图，遍历只穿过图中的每条边两次。并且边的数量与节点的数量成正比，因为没有循环或冗余边（每个节点都可以通过唯一的路径到达）。具有 N 个节点的树恰好有 N-1 条边：每个节点都有一条从其父节点通向它的边，但树的根节点除外。
有时，访问一个节点似乎需要不止一次下降。例如，在访问子树中最右边的节点之后，我们必须弹出许多层才能向右行进到下一个子树。但是我们并没有一路下降只是为了访问那个节点。每个一级下降都可以被认为是访问紧接其下的节点所必需的，并且相反的上升成本与此混为一谈。通过访问节点 V，我们还可以访问它下面的所有节点，但是所有这些节点都受益于并共享从 V 的父节点到 V 的边遍历，并再次备份。
这与摊销分析有关，它适用于我们可以根据对问题结构的一些一般观察来全局了解总体成本的情况，但在单个操作的详细级别，成本以不均匀的方式分布，即显得混乱。
摊销分析有助于我们理解，例如，通过指数增长调整自身大小的哈希表中的 N 次插入是 O(N)。大多数插入操作都很快速，但有时我们会增大表并处理其内容。这类似于在树遍历期间，我们必须不时地执行多次连续上升以爬出深子树。
对哈希表的全局观察是，在 3 次 resize 操作中，每次插入表中的项平均会移动到更大的表中大约 3 次，因此每次插入可以视为“预付”了 3 次重新插入，即是固定成本。当然，“较旧”的项目将被移动更多次，但这被移动较少的“年轻”条目所抵消，从而稀释了成本。上面已经提到了关于树的全局观察：它有 N-1 条边，每条边在遍历期间恰好被遍历两次，因此每个节点的访问“支付”其各自边的双重遍历。因为这很容易看到，我们实际上不必正式将摊销分析应用于树遍历。
现在假设我们对每个节点执行单独的搜索（并且树是平衡搜索树）。那么遍历仍然不是 O(N*N)，而是 O(N log N)。假设我们有一个有序的搜索树，其中包含连续的整数。如果我们对整数进行递增并对每个值执行单独的搜索，那么每次搜索都是 O(log N)，我们最终会执行其中的 N 个。在这种情况下，不再共享边遍历，因此不适用摊销。为了到达我们正在搜索的某个给定节点，该节点位于深度 D，我们必须穿过 D 边两次，为了那个节点和那个节点。循环中对另一个整数的下一次搜索将完全独立于前一个整数。
它也可以帮助你想到一个链表，它可以被视为一棵非常不平衡的树。访问一个长度为 N 的链表中的所有项目并返回到头节点显然是 O(N)。单独搜索每个项目是 O(N*N)，但是在遍历中，我们不是单独搜索每个节点，而是使用每个前驱作为跳板来寻找下一个节点。
于 2013-07-17T23:38:27.930 回答
1
没有找到父项的循环。否则说，您将通过两个节点之间的每条弧线两次。那将是 2 * 弧数 = 2 *（节点数 -1），即 O（N）。
于 2013-07-17T20:41:45.737 回答