4

数十種類のノードで構成されるツリー構造があります (各種類のノードはNodeBaseクラスから継承されます)。

ツリーで検索を実行して、特定のノードへの参照を返したいと考えています。たとえば、他のタイプのノードの中にノードCompanyを含むツリーがあるとします。ノードはノードで構成されます。従業員は部門の一部である必要があり、正確に 1 つの部門に属することができると想定されています。DepartmentDepartmentEmployee

現在、各ノードが type の子ノードのリストを持つように設計されていますNodeBase。ツリーは非常に大きくなり、時には数十万のノードになることがあります。挿入/削除操作はめったに使用されませんが、これらの大きなツリーでは検索操作に「時間がかかりすぎる」べきではありません。

employee IDフィールドが私が提供する文字列と等しい従業員ノードへの参照を取得したいとします。その従業員がどの部門に所属しているのかわからないので、一致するものを見つけるためにすべてのノードを検索する必要があります。すべてのノードにemployee IDフィールドがあるわけではありません。たとえば、部門にはそれらがありません。

このツリー構造の設計を考えると、検索機能を実装する最良の方法が何であるかはわかりません。

最初にデータを保存する方法を設計するためのより良い方法があると思われます (例: データベースを使用しますか?) が、現在、私はツリーで立ち往生しています。

4

3 に答える 3

2

データ構造はデータを整理する方法であり、データを整理する方法は、それらの情報を実際にどのように使用するかによって異なります。

ツリーは、「ノード X のすべての子孫を取得する」などの質問に答えるのに適したデータ構造ですが、「プロパティ X が Y に設定されたオブジェクトを見つける」という問題の解決には役立ちません(少なくとも、あなたのツリーではありません)。 : 後で説明するように、ソートされたインデックスを保持するためにツリーを内部的に使用することもできます)。

したがって、これを解決する最善の方法は、データを整理するために 2 つの別個のデータ構造を使用することだと思います。NodeBaseオブジェクト間の階層関係を反映するオブジェクトで作成されたツリーと、適切なパフォーマンスで検索を行うためのNodeBase'sソート済みインデックスです。ただし、ノードの追加/削除時に 2 つのデータ構造の同期を維持する必要があるため、同期の問題が発生します。あまり頻繁に発生しない場合、または単に検索パフォーマンスが重要な場合は、これが正しい方法である可能性があります。

于 2013-06-13T20:21:07.353 に答える
1

この質問には、クラス階層の分解と検索アルゴリズムの実装という 2 つの部分があるようです。

Java の世界では、分解の問題に対して2 つの可能な解決策があります。

  • 局所的な性質を持つオブジェクト指向の分解、および
  • instanceofと を使用した型チェック分解type casting。

関数型言語 (Scala を含む) はパターン マッチングを提供します。これは、型チェックの分解を実装するためのより優れたアプローチです。

要素 (ノード) がさまざまなタイプになる可能性があるデータ構造 (ツリー) を操作する必要があるため、分解の性質は明らかに局所的ではありません。したがって、2 番目の方法が唯一の選択肢です。

検索自体は、たとえば、二分探索ツリー アルゴリズムを使用して実装できます。そのようなツリーは、特定のノードを配置する場所の決定が実際の検索基準に依存する必要がある場合、データから構築する必要があります。基本的に、これはさまざまな検索基準があるのと同じ数のツリーが必要になることを意味します。これは本質的にインデックスを構築する方法です。データベース エンジンは、二分探索ツリーよりも洗練された構造を使用します。たとえば、red-black treesですが、考え方は非常に似ています。

ところで、二分探索木は均質な性質を持っています。たとえば、検索がEmployeebyに関連する場合、検索ツリーはインスタンスDepartmentに関連付けられたノードのみで構成されます。Employeeこれにより、分解の問題が解消されます。

于 2013-06-13T20:25:20.477 に答える
1

ツリーがDAG (有向非巡回ツリー) であると仮定すると、たとえば DFS または BFS を使用します。簡単な BFS を次に示します。

public NodeBase findEmployee (NodeBase root, Integer employeeId) {
    Queue<NodeBase> q= new LinkedList<NodeBase>();
    q.add(root);
    while (!q.isEmpty()) {
        NodeBase node= q.poll();
        if (node instanceof Employee) {
            if (((Employee)node).getId().equals(employeeId))
                return node;
        }
        for (NodeBase child : node.getChildren())
            q.add(child);
        }
    }
}

編集：訪問者パターン

または、Brabsterが提案したように、訪問者パターンを使用できます。AはメソッドNodeBaseを実装する必要があります。accept(IVisitor visitor)

public class NodeBase {
    //your code
    public void accept(IVisitor visitor) {
        visitor.visit(this); 
        for (NodeBase node : getChildren()) {
            node.accept(visitor);
        }
    }
}

IVisitor は単なるインターケースです:

public interface IVisitor {
     public void visit(NodeBase node);
}

そして、検索を行う適切な実装が必要です:

public class SearchVisitor implements IVisitor {

     private Integer searchId;

     public SearchVisitor(Integer searchId) {
          this.searchId= searchId;
     }

     @Override
     public void visit(NodeBase node) {
         if (node instanceof Employee) {
             if (((Employee)node).getId().equals(searchId)) {
                  System.out.println("Found the node " + node.toString() + "!");
             }
         }
     }
}

そして今、あなたは単にそれを呼び出すだけです：

NodeBase root= getRoot();
root.accept(new SearchVisitor(getSearchId()));
于 2013-06-13T20:17:05.413 に答える