1

二分探索ツリーで 2 つのノードの最も低い共通の祖先を見つけるための以下のアルゴリズムがどれほど効率的かを知りたかっただけです。

Node getLowestCommonAncestor (Node root, Node a, Node b) {

   Find the in-order traversal of Node root.
   Find temp1 = the in-order successor of Node a.
   Find temp2 = the in-order successor of Node b.

   return min (temp1, temp2);
}
4

3 に答える 3

8

二分探索木で最下位の共通祖先を検索するのは、それよりも簡単です。LCA は、アイテム A とアイテム B の検索が最初に分岐するノードであることに注意してください。

ルートから始めて、A と B を同時に検索します。両方の検索で同じ方向に進む限り、検索を続けます。A と B を検索すると別のサブツリーに移動するようなノードに到達すると、現在のノードが LCA であることがわかります。

于 2012-09-23T12:23:20.803 に答える
2

大規模な二分探索ツリーの最下部にあるノードは、その近くに順序どおりの後継者を持つことができます。たとえば、それがノードの左側の子である場合、その順序どおりの後継者はその親です。

ルートの異なる子から派生した 2 つのノードは、それらがどこにあるかに関係なく、ルートを最も一般的でない先祖として持つため、アルゴリズムがこのケースを間違っていると思います。

これは、 http://en.wikipedia.org/wiki/Lowest_common_ancestorでの効率的な LCA アルゴリズム (準備用のデータ構造を構築する時間が与えられた場合) の議論であり、コードへのポインタが含まれています。

LCA を見つける非効率的で簡単な方法は次のとおりです。ツリーで、子から親へのポインターと、各ノードの深さのメモを保持します。2 つのノードが与えられた場合、同じ場合は最も深いノードからその深さまで上に移動します。他のノードを指している場合、それは LCA です。それ以外の場合は、各ノードから 1 ステップ上に移動して再度チェックするなど、LCA で会うまで繰り返します。

于 2012-09-23T12:24:58.850 に答える