跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問8

标签：

Author​

GPT-5

Description​

各節点に正の整数値が格納された二分木を考える。節点 ii の値を V(i)V(i)、左の子を L(i)L(i)、右の子を R(i)R(i) とし、子が存在しない場合は L(i)=−1L(i)=-1 または R(i)=−1R(i)=-1 とする。部分木の重みを、その部分木に含まれる節点の値の総和と定義する。

  1. 節点 ii を根とする部分木の重みを求める再帰的アルゴリズムを示せ。
  2. すべての節点において左右の部分木の重みが等しい二分木を「釣り合っている」とする。節点数が 7 の釣り合っている二分木の最大の高さを求め、その例を示せ。ただし、根だけの木の高さを 0 とする。
  3. 各節点で (1) のアルゴリズムを用いて左右の重みを比較する素朴な釣り合い判定アルゴリズムについて、節点数を nn としたときの最悪時間計算量を求めよ。
  4. (3) より効率のよい釣り合い判定アルゴリズムを示し、その時間計算量を求めよ。

题目描述​

考虑一棵每个结点都存有正整数值的二叉树。以 V(i)V(i) 表示结点 ii 的值，以 L(i)L(i)、R(i)R(i) 分别表示其左、右孩子；若相应孩子不存在，则记 L(i)=−1L(i)=-1 或 R(i)=−1R(i)=-1。一棵子树的重量定义为其中所有结点值之和。

  1. 给出一个递归算法，计算以结点 ii 为根的子树重量。
  2. 若一棵二叉树在每个结点处的左、右子树重量都相等，则称它是“平衡的”。求结点数为 77 的平衡二叉树所能达到的最大高度，并给出达到该高度的例子；规定只有根结点的树高度为 00。
  3. 考虑一种朴素的平衡判定算法：在每个结点都调用第 1 问的算法，分别计算并比较左右子树重量。设结点总数为 nn，求该算法最坏情况下的时间复杂度。
  4. 给出一个比第 3 问更高效的平衡判定算法，并求其时间复杂度。

考点​

  • 二叉树递归：按后序遍历汇总左右子树重量，并正确处理空孩子的哨兵值。
  • 带正权树的结构约束：利用左右子树重量相等及结点值为正整数，分析七结点平衡树的最大高度并构造实例。
  • 树算法复杂度优化：识别朴素算法对同一子树的重复求和，将重量计算与平衡检查合并为一次遍历。

Kai​

(1)​

存在しない部分木の重みを 0 とすれば、次の再帰で求められる。

weight(i):
    if i == -1:
        return 0
    return V(i) + weight(L(i)) + weight(R(i))

(2)​

答えは

3\boxed{3}

である。

値はすべて正なので、釣り合っている木のある節点が子を一つだけ持つことはない。一方の部分木の重みが正、もう一方が 0 となるからである。したがって木は full binary tree であり、高さ hh の木は少なくとも根から最深葉までの各内部節点に兄弟部分木を必要とするため、少なくとも 2h+12h+1 節点を持つ。n=7n=7 より 2h+1≤72h+1\le 7、すなわち h≤3h\le 3 である。

次の値を持つ木で高さ 3 が実現できる。丸括弧内は節点の値である。

最下段の内部節点では左右の重みが 11、その親では左右がともに 33、根では左右がともに 77 であり、確かに釣り合っている。

(3)​

ある節点で weight を呼ぶと、その左右の部分木の全節点を走査する。この処理を各節点で繰り返すため、実行時間は各節点の部分木サイズの総和に比例する。

木が一方向に深い full binary tree の形を取ると、この総和は

Θ(n+(n−2)+(n−4)+⋯ )=Θ(n2)\Theta(n+(n-2)+(n-4)+\cdots)=\Theta(n^2)

となる。この形でも節点値を適切に選べば釣り合った木にでき、途中で判定が打ち切られない。したがって最悪時間計算量は

Θ(n2)\boxed{\Theta(n^2)}

である。

(4)​

後順走査によって、釣り合いの判定結果と部分木の重みを同時に返す。

check(i):
    if i == -1:
        return (true, 0)

    (left_ok,  left_weight)  = check(L(i))
    (right_ok, right_weight) = check(R(i))

    ok = left_ok and right_ok and (left_weight == right_weight)
    total = V(i) + left_weight + right_weight
    return (ok, total)

各節点をちょうど一度処理するので、時間計算量は

Θ(n)\boxed{\Theta(n)}

である。再帰スタックに必要な領域は木の高さを hh として O(h)O(h) である。

本页目录