ADS - Abstract Data Structure: Union-Find

[Janulka]

Hallo!
Could someone please help me? I need to program ADS union-find in Delphi. How could I add nodes in a tree, which has this structure:
1. Every item is in a tree.
2. The root of the tree is the representative item of all items in that tree. i.e., the root of the tree represents the whole items.
3. In this up-tree implementation, every node (except the root) has a pointer pointing to its parent.
The root element has a pointer pointing to itself (or nil).

Delphi-Quellcode:

___________
interface :
___________

    TNode = class
       parent : TNode;
        value : integer;
        constructor Create(i : integer);
    end;

    TTree = class
       root : TNode;
        constructor Create(i : integer);
        procedure add(item : integer);
    end;

    TUnionFind = class
       root : TTree;
        parent : TUnionFind;
        size : integer;
        name : String;
        constructor Create(s : string);
    end;

function Union(X, Y : TUnionFind) : TUnionFind;
_________________
implementation :
_________________

    function Find_Set(X : TUnionFind) : TUnionFind;
   begin
       while (X <> X.parent) do
           X := X.parent;
        Result := X;
    end;
                
   function Union(X, Y : TUnionFind) : TUnionFind;
    var
       A, B : TUnionFind;
    begin
       A := Find_Set(X);
        B := Find_Set(Y);
        if (A.size <= B.size) then
        begin
           if (A.size = B.size) then
               inc(B.size);
           A.parent := b;
            Result := A;
        end else
        begin
           B.parent := A;
            Result := B;
        end;
    end;

Danke schoen :)

[edit=SirThornberry]Delphi-Tags korrigiert - Mfg, SirThornberry[/edit]

[marabu]

Hi Janulka,

welcome to Delphi-PRAXiS.

Your problem looks like an assignment and your question makes me wonder if you ever heard of union-find structures before. Those code lines are yours? Usually, there is no method named Add(), because the addition of a new node to a tree is accomplished by union. So where does Add() come from in your tree class?

Kind regards