同じレベルで複製が許可されていない効率的なツリーデータ構造

Question

各親ノードに一意のノードセットしか含まれないようにするツリー構造を開発しています。

public class TreeNode implements Iterable<TreeNode> { 

    private final TreeNode parent; 
    private final List<TreeNode> children = new LinkedList<>(); 

    public TreeNode(TreeNode parent) { 
     this.parent = parent; 
    } 

    public TreeNode append(TreeNode child) { 
     int index = children.indexOf(child); 
     if (index < 0) { 
      children.add(child); 
      return child; 
     } else { 
      return children.get(index); 
     } 
    } 

    public Iterator<TreeNode> iterator() { 
     return children.iterator(); 
    } 

    /* Other unimportant application details */ 

    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     TreeNode t = (TreeNode) o; 
     return parent != null ? parent.equals(t.parent) : t.parent == null; 
    } 

    public int hashCode() { 
     return parent != null ? parent.hashCode() : 0; 
    } 

} 

ここでの問題は私の木が深いのであれば、各children.indexOf()呼び出しを再帰的に各appendメソッド呼び出し上のすべての親の平等をチェックすることです。ここに私のコードです。私は、equals()とhashCode()メソッドを再実装する方法は、同じレベルの各ノードに対して、Immetiateの親が同じであることをチェックするという方法です。ように：

public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     TreeNode t = (TreeNode) o; 
     return parent == t.parent; 
    } 

    public int hashCode() { 
     return System.identityHashCode(parent); 
    } 

私はこれが問題になる理由を考えることはできません。この実装の問題はありますか？もしそうなら、あなたはこの問題のより良い解決策を提案できますか？ありがとう！

Answer 1

"は、各親ノードに固有のノードセットのみが含まれていることを保証する必要があります。

私の意見では、 プライベート最終的なリスト子供=新しいLinkedList <>（）;

1. hashCode（）とequals（）を実装している場合は、子ノードの一意性を保証できるように、Mapである必要があります。
2. マップとして取ると、append（）呼び出しはO（1）時間の複雑さになります。これはリストの場合はO（n）です。

子供をリストとして定義するための他の考えがある場合は、私たちと共有してください。