Difficulty understanding the tree traversal analysis of height1() of O(n^2) in Data Structure and Algorithms in C++ Michael T. Goodrich 第二版

Question

我会尽量总结和解释的。这是关于树遍历算法的。

A) Class 位置

template <typename E> // base element type
class Position<E> { // a node position
public:
    E& operator*(); // get element
    Position parent() const; // get parent
    PositionList children() const; // get node’s children
    bool isRoot() const; // root node?
    bool isExternal() const; // external node?
};

B) Class 树

template <typename E> // base element type
class Tree<E> {
public: // public types
    class Position; // a node position
    class PositionList; // a list of positions
public: // public functions
    int size() const; // number of nodes
    bool empty() const; // is tree empty?
    Position root() const; // get the root
    PositionList positions() const; // get positions of all nodes. According to author, PositionList is implemented as list<Position>. There's no definition for PositionList nor is there implementation for positions() function shown. Left as an exercise.
};

根据作者的说法，树的depth() & height1()可以如下实现。

int depth(const Tree& T, const Position& p) {    
     if (p.isRoot()) return 0; // root has depth 0     
     else return 1 + depth(T, p.parent());     
}    

int height1(const Tree& T) {
    int h = 0;
    PositionList nodes = T.positions(); // list of all nodes
    for (Iterator q = nodes.begin(); q != nodes.end(); ++q) {
       if (q−>isExternal())
          h = max(h, depth(T, *q)); // get max depth among leaves
    }
    return h;
}

作者摘录：

Unfortunately, algorithm height1 is not very efficient. Since height1 calls algorithm depth(p) on each external node p of T , the running time of height1 is given by O(n+∑p(1+dp)), where n is the number of nodes of T , dp is the depth of node p, and E is the set of external nodes of T . In the worst case, the sum ∑p(1 + dp) is proportional to n^2.

为什么是 n^2（二次）？

我尝试了几个示例，如下所示：

我试了 N=5,6,7,8 还是达不到 n^2。

这里的任何帮助都很棒。谢谢。

Answer 1

In the worst case, the sum ∑p(1 + dp) is proportional to n^2

用“最坏情况”的场景应该更容易理解。考虑一个“skewed”子树，其中 n/2 个节点线性排列，最后一个节点有 n/2 个子节点（在这种情况下将是叶节点或“外部”节点）。这棵树看起来像

1
 \
  2
  ...
    \
     n/2
 ______|________
|  |  |  |  |  |
(remaining n/2 nodes)

对于每个外部节点，我们的深度为n/2，因此计算它需要O(n/2) ~ O(n) 时间。并且由于有 n/2 个节点需要计算深度，所以复杂度变为 O(n/2 * n/2) ~ O(n^2)，这是作者提到的最坏情况复杂度。

编辑：

这是 n=10 的上述树的图示。您可以看到为什么每个外部节点都需要 O(n/2) ~ O(n) 遍历：

Difficulty understanding the tree traversal analysis of height1() of O(n^2) in Data Structure and Algorithms in C++ Michael T. Goodrich 第二版

Difficulty understanding the tree traversal analysis of height1() of O(n^2) in Data Structure and Algorithms in C++ Michael T. Goodrich 2nd ED

algorithm

tree

big-o

data-structures

编辑：