algorithm - 指定された範囲で BST キーを出力する

Question

指定された範囲で BST キーを印刷する実行時間を理解しようとしています。この例から理解しようとしましたが、理解できませんでした。

O(log n)がどこから来ているのか理解できたと思います。これは、BST を再帰的に通過することによるものです。これはO(log n)各側に必要ですが、次の点についてはわかりません。

1. はどこKから来ているのか。印刷にかかる一定の時間ですか？はいの場合、ランタイムがO(log n)+O(k)ではないのはなぜですか。K を無視するよりも

2. O(n)in order traversal からの はどこにありますか? このランタイムにないためです。

3. ツリーの両側の範囲に複数の値がある場合、ランタイムがどのように変化するか。たとえば、範囲が 4 からだった場合はどうなるでしょうか。

Answer 1

ソリューションを理解する簡単な方法は、次のアルゴリズムを検討することです。

1. BST ツリーでキー k1 より大きい最小値を検索 - O(lgn)
2. k1 から k2 以下のノードに到達するまで BST ツリー ノードの順序どおりのトラバーサルを実行し、それらのキーを出力します。完全な BST の順序どおりのトラバーサルには O(n) 時間がかかるため、k1 と k2 の間に k 個のキーがある場合、順序どおりのトラバーサルには O(k) の時間がかかります。

与えられたアルゴリズムは同じことをしています。k1 と k2 の間のキーの検索には O(lgn) の時間がかかりますが、印刷は O(k) である k1 と k2 の範囲内の k 個のキーに対してのみ行われます。すべての BST キーが k1 と k2 内にある場合、実行時間は O(lgn) + O(n) = O(n) になります。これは、n 個のキーすべてを出力する必要があるためです。