< O(log n) 時間でランクを使用して、バランスのとれた二分探索ツリーの 2 つのノード間のノードの数 (カウントのみ) を見つける方法はありますか?
各ノードのランク (または高さ) を Node クラスのメンバー変数として動的に格納していると仮定できます。したがって、直接アクセスできます。
質問する
2668 次
1 に答える
2
はい、最小共通祖先クエリを使用すると、その間のノードを一定時間でカウントできます。線形時間でのツリーの前処理が 1 回必要です。
2 つのノードの最も低い共通の祖先のランクがわかっている場合、子ノードのランクから祖先のランクを差し引くことで、ノードと祖先の間にあるノードの数を計算できます。
nodes_between = a.rank + b.rank - 2*(lowest_common_ancestor(a, b).rank) + 1
上記は、ノード間のパスの長さを返し、2 つの終点を含みますa。bは+ 1、最下位共通祖先そのものです。を見つけるlowest_common_ancestorことは一定時間で行うことができ、計算は一定時間です。
于 2013-08-31T20:41:26.573 に答える