BST検索problen

Question

これは、n個のノードにPoint（x、y）タイプのオブジェクトを含むBSTを実装しました。ツリー内の順序はXの値に従います。

Iは入力として、Xの範囲取得（Xの左、右x）関数 を実装する必要があり、出力が （EDIT）ある：範囲内のYの座標の和は、（付属します）。

すべてのノードを「歩いて」いることはそれほど難しくありませんが、問題はO（logn）の複雑さでそれを行うことです。

私は範囲とYの合計のフィールドを初期化することについて考えましたが、何とか挿入と削除の機能ではうまくいきません。 アイデア？

Answer 1

範囲の各端を見つけることは、O(log n)の複雑さです。ツリー内のすべてのノードを見る必要はありません。

範囲の数値を合計する必要がある場合は、高境界から低境界を引いた値（連続した直線範囲を想定します）は、一定の時間操作です。