先週試験を受け、次の質問に直面しました。
O(h) 時間でキー k を持つ T のエントリ数をカウントするように二分探索木を変更する方法を説明してください。このアルゴリズムは、リストではなく整数を返す必要があります。
その後、試験後に回答が公開され、次のようになります。
解決策: 各ノードに、そのノードをルートとするサブツリー内の内部ノードの数を追加して、ツリーを変更します。ノードが挿入、削除、および再構築される可能性がある場合は、これらを再計算します。これには、次のアルゴリズムが必要です。
しかし、それは非常に混乱しているようです。私の質問は、赤丸で囲んだ部分の役割は何ですか?