time-complexity - インターバル ツリーの時間計算量分析

Question

私が現在学習しているインターバル ツリーには、ノードごとに次のデータ構造があります。

• key: すべての間隔の終点の中央値
• left, right: 左右のサブツリーを指す
• intervals: を含む間隔を含む間隔のリストkey。

より正確な情報は、このリンクにあります。

インターバル ツリーを使用したクエリの時間計算量は O(logn + k) であることがわかりました。ここで、n はインターバルの数、k は報告された結果の数です。

の部分がよくわかりませんlogn。がインターバルvツリーの現在のノードで、Qがクエリ間隔であるとします。アルゴリズムは次のようになります。

if v.key is in Q,
  add v.intervals into results
  search_on_left_subtree
  search_on_right_subtree
else if Q.right < key,
  add some intervals
  search_on_left_subtree
else
  add some intervals
  search_on_right_subtree

最初は、if2 つのサブツリーに入る必要があるようです。最悪の場合、すべてのツリー ノードをトラバースしなければならず、時間計算量が O(n + k) になるのではないでしょうか?