バイナリツリーのルート値を探す？

Question

は、私はいくつかの木のようなものになる値の関係を格納した配列、している：

ので、この場合には、私の配列は次のようになります（ルートは、リンクへ）（

8,3） （8,10） （3,1） （3,6） （6,4） （6,7） （10,14） （14,13）

と私は（すべての木で）ツリー内のメインルートに、アレイ内のすべてのルートの値を設定したいと思います：

（8,3） （8,1） （8,6） （8,4） （8,7） （8,10） （8,14） （8,13）

私は何のアルゴリズムを調査する必要がありますか？

Answer 1

1）タプルのすべての固有の最初の要素のリストを作成します。

2）タプルの2番目の要素としても見えるものを削除します。

3）ルート（ここでは8）のままになります。すべてのタプルの最初の要素をこの値に置き換えます。

---

EDIT：次のように複数のツリーで動作します

より複雑なアプローチは次のようになります。

まず、親ルックアップテーブルに変換：

1 -> 3 
3 -> 8 
4 -> 6 
6 -> 3 
7 -> 6 
10 -> 8 
13 -> 14 
14 -> 10 

次に、各要素の "パス圧縮を持つ親を見つける" 実行します。

1）

1 -> 3 -> 8 

を与えます

1 -> 8 
3 -> 8 
4 -> 6 
... 

3）

3 -> 8 

4）

4 -> 6 -> 3 -> 8 

1 -> 8 
3 -> 8 
4 -> 8 
6 -> 8 
7 -> 6 
... 

6）

6 -> 8 (already done) 

7）

7 -> 6 -> 8 

0123を与えます

など

結果：次に

1 -> 8 
3 -> 8 
4 -> 8 
6 -> 8 
7 -> 8 
... 

タプルのリストにこのバック変換：

(8,1)(8,3)(8,4)... 

---

find_setは例えば、互いに素な集合の森のためになるようにパス圧縮アルゴリズムで検索親であります

int find_set(int x) const 
{ 
    Element& element = get_element(x); 
    int& parent = element.m_parent; 
    if(parent != x) 
    { 
     parent = find_set(parent); 
    } 
    return parent; 
} 

重要な点は、パス圧縮が多くの作業を回避するのに役立つことです。上記の場合、たとえば、4の検索を実行すると、6 -> 8が格納され、後で参照が6を参照するようになります。

Answer 2

ですから、点を表すタプルのリストを持っていると仮定します。

def find_root(ls): 
    child, parent, root = [], [], [] 
    for node in ls: 
    parent.append(node[0]) 
    child.append(node[1]) 

    for dis in parent: 
    if (!child.count(dis)): 
     root.append(dis) 

    if len(root) > 1 : return -1 # failure, the tree is not formed well 

    for nodeIndex in xrange(len(ls)): 
    ls[nodeIndex] = (root[0], ls[nodeIndex][1]) 

    return ls