将军树高度

Question

我正在学习 Tamassia 和 Goodrich 的 C++ 数据结构和算法（第 2 版）

我无法理解一般树 T 的运行高度时间为 O(n + sum_over_p(1 + dp)) 其中 n 是 T 的节点数，dp 是节点 p 的深度（第 276 页）。

这里使用的概念是"the height of tree is the maximum depth of external nodes"

这里是书中给出的求树高的代码

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;
}

谢谢！！

更新

深度函数的代码是

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

Answer 1

按照我的理解，您遍历 O(n) 树中的所有节点。对于每个外部节点，你调用 depth 函数，它采用 O(1+dp)（因为对于深度为 0 的根节点，它需要 1 次函数调用，因此是 1+dp），所以这就是原因 sum_over_p(1 + dp).

唯一的问题是在代码中他们只为外部节点运行 depth 而在定义中似乎他们为每个节点调用它...所以我不确定哪里错了

Answer 2

想象一个完整的二叉树 T 具有 N 个节点（N = 2^K - 1 对于一些 K 因为 T 已满）。在 T 中恰好有 N / 2 个叶子，每个叶子的深度等于 K - 1。对于这样的树，该算法将在 O(N log N) 时间内运行（每个叶子的计算深度需要 O(K) ).知道像计算树高这样简单的操作可以在 O(N).

中完成，这真是糟糕

我从未读过这本书，但我建议更改它。 Thomas H. Cormen 的算法简介 是很好的介绍。

将军树高度

Height of General Tree

c++

algorithm

tree

big-o

data-structures