c++ - 遍历层树的复杂性

Question

我有一个看起来像这样的层树

第一层树是一棵平衡二叉搜索树，它以特定顺序存储一些数据(比如整数)，第一层树的每个节点 v 包含一个指向平衡二叉搜索树根的指针，称为第二层树，在它的叶子存储 Sv1(v 的子树)的点。

现在有一个更新函数接受像 p 这样的输入并像这样操作:

Search for p in layer one tree, for each node v on the search path search for p in layer two, let Lv be the leaf of this layer two tree in which the search ends. Then starting at Lv walk back to the root of layer two tree of v and for each node on the path recompute its value.

我的书说这个 Action 可以在 lg^2(n) 中执行(n 是第一层树中的节点数)。但我不明白如何。这是我为此任务编写的算法:

L1Search(LayerOneNode* n){
    if (n == NULL) return;
    if (n->data < p)
        L1search(n->left);
    if (n->data > p)
        L1search(n->right);
    L2Search(n->pointerToLayerTwoRoot); //For each node on the search path
}
L2Search(LayerTwoNode* n){// Start at the leafs of the Layer-Two tree and go up
    if (n == NULL) return;
    L2search(n->left);
    L2search(n->right);
    computeTheValueForThisNode();
}

我不确定，但我认为我的算法的复杂度是 n*lg(n) 而不是 lg^2(n)。我对吗？是否有更好的算法来执行此任务？

Answer 1

在第 1 层树中搜索时，您会迭代 height(tree) 节点，最大值为 1。平衡二叉树的高度是 lg(n)(lg 是以 2 为底的对数)。对于这些 lg(n) 节点中的每一个，您基本上在另一棵树中重复搜索，元素数量 <=n(因为它是一棵子树)。此搜索再次花费您 lg(n)。由于您对第一个搜索路径的每个 lg(n) 元素进行第二次搜索(花费 lg(n))，因此产生的复杂度是乘法 lg(n)*lg(n)。