从有序遍历和预遍历遍历构造二叉树的时间复杂度 [英] Time complexity of construction of a binary tree from inorder and preorder traversals

问题描述

给出此处是代码用于根据有序和预遍历遍历构造树。我无法弄清楚它们是如何达到O（n ^ 2）时间复杂度的。有任何想法吗？我看到按顺序搜索索引为O（n），其余部分如何计算？

Given Here is the code for constructing a tree from the inorder and preorder traversals. I cant figure out how they arrived at an O(n^2) time complexity. Any ideas? I see that the search for an index in the inorder sequence would be O(n), how is the rest of it computed?

推荐答案

O（N ^ 2）的复杂性是由于以下事实造成的：对于遍历遍历中的每个项目（其中有 N ），则必须在顺序遍历中搜索其分区（同样，其中的 N 个）。

The O(N^2) complexity results from the fact that for every item in the Preorder traversal (of which there are N), you have to search for its partition in the Inorder traversal, (again there are N of these).

粗略地说，您可以将此算法视为将节点放置在网格上，其中有序遍历提供了x坐标，而有序遍历提供了y坐标：

Roughly speaking, you can consider this algorithm as placing the nodes on a grid, where the Inorder traversal provides the x co-ordinates and the Preorder traversal provides the y co-ordinates:

以他们给出的示例为例，并进行以下遍历（先后顺序）：

Take the example they gave, with the following traversals (Inorder then Preorder):

Inorder: DBEAFC
Preorder: ABDECF

现在这是他们放置的网格：

Now this is the grid they are being put on:

     D    B    E    A    F    C
A    +    +    +    A    |    |
     |    +--------------+    |
B|F  +    B    |         F    |
     +---------+         -----+
DE|C D         E              C

现在，该算法需要知道将每个节点放置在网格中的位置，只需将节点置于x和y坐标在网格中的位置即可。

Now, the algorithm needs to know where in the grid to place each node, which it does simply by putting the node at the position in the grid where the x and y co-ordinates are the same.

在这种情况下，看起来网格的大小实际上是 NlogN ，这将导致 NlogN 遍历网格的复杂度（因此，算法的 NlogN 时间复杂度）但这棵树是平衡的。在最坏的情况下，您的树实际上可能是一个链表。

It looks as though the size of the grid is actually NlogN in this case, which would result in an NlogN complexity for traversing the grid (and so an NlogN time complexity for the algorithm) but this tree is balanced. In the worst case, your tree might in fact be a linked list.

例如考虑这棵树，其中预遍和遍历遍历是相同的：

E.g. consider this tree, where the preorder and inorder traversals are the same:

Inorder: DBEAFC
Preorder: DBEAFC

     D    B    E    A    F    C
D    D    |    |    |    |    |
     -----+    |    |    |    |
B         B    |    |    |    |
          -----+    |    |    |
E              E    |    |    |
               -----+    |    |
A                   A    |    |
                    -----+    | 
F                        F    |
                         -----+
C                             C

这是最坏的情况，您会看到网格中有 N * N 个位置需要检查。因此，在最坏的情况下，时间复杂度为 N * N 。

This is the worst case, and you see, the grid has N*N positions in it to check. So in the worst case, there is an N*N time complexity.

这篇关于从有序遍历和预遍历遍历构造二叉树的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！