树算法高度分析疑问：为何节点操作代价不是2cₚ？

原代码 #

int height2(const Tree& T, const Position& p) {
    if (p.isExternal()) return 0; 
    int h = 0;
    PositionList ch = p.children(); // iterate on the children of the node
    for (Iterator q = ch.begin(); q != ch.end(); ++q)
        h = max(h, height2(T, *q));
    return 1 + h;
}

疑问解答 #

你纠结的“为什么不是cₚ + cₚ”，核心在于对children()函数的开销理解偏差，结合作者的分析（翻译如下）就能理清：

作者分析说明（翻译）
我们给每个节点定义的代价为1 + cₚ，其中cₚ是节点p的子节点数量。这里的“1”对应节点自身的基础操作——比如判断是否为外部节点、初始化变量h、返回计算结果这些步骤；而cₚ则是获取子节点列表+遍历子节点的总开销。
在绝大多数树的实现中，children()并不会复制整个子节点集合，它返回的是迭代器或者视图对象，调用本身的开销是O(1)。真正的cₚ次操作是在后续的for循环里，逐个访问每个子节点。也就是说，“获取子节点”和“遍历子节点”是绑定在一起的过程，总开销就是cₚ，而非两次独立的cₚ。
举个例子：如果子节点用链表存储，children()只是返回链表头指针，循环里才会遍历cₚ个节点；如果是数组存储，children()返回数组引用，循环遍历的cₚ次访问才是主要开销。作者把这部分合并为cₚ，再加上节点自身的基础操作1，所以总代价是1 + cₚ。

简单来说，children()本身没有额外的cₚ开销，它和循环遍历的开销是重叠的，不需要重复计算两次。

内容的提问来源于stack exchange，提问作者Gipreel