Java'da sıralanmamış bir ikili ağaç oluşturmanın en etkili yolu nedir?

Question

Ben onun değeri olarak bir String tutan bir sıralanmamış ikili ağaç (şartı, sıralanmamış olmasıdır) oluşturmanız gerekir. Benim sınıf olarak şu şekildedir:

public class Node { 

private String desc; 
private Node leftNode = null; 
private Node rightNode = null; 

public Node(String desc) { 
    this.desc = desc; 
} 

public String getDesc() { 
    return desc; 
} 

public Node getLeftNode() { 
    return leftNode; 
} 

public Node getRightNode() { 
    return rightNode; 
} 
} 

Sonunda (eski bilgi ile yinelenenler dahil) yeni bir açıklama sahip yeni düğüm ile String tanıma uyan herhangi bir düğüm yerine isterler.

Benim soru, sıralanmamış ikili ağaç oluşturulurken Node s yerleştirilmesini işlemek için en iyi yolu nedir nedir?

Ben iki yoldan düşündü. İlk sadece iki yöntem, setLeftNode(Node root, String desc) ve birisi root olarak kendi seçtikleri bir Node ile diyebiliriz ki setRightNode(Node root, String desc) sahip olacaktır. Eğer zaten bir sol/sağ Node varsa, Node sola sahip olmayan bir düğüme gelene kadar aşağı doğru ilerler. Ancak bu, süper büyük yükseklikler üreterek sorunlara yol açabilir.

Bu durumda oluşturulan ilk Node yılında, özel bir kök Node sahip olmak ve sonra sadece amacıyla yeni Node s inşa etmek olacağını düşündüm ikinci yolu.

Yani bir sıralanmamış ikili ağaç oluşturmak için en iyi yolu nedir? Tanım gereği

Answer 1

public class BinaryTree{ 
    private BinaryTree right; 
    private BinaryTree left; 
    private String data;   

    public BinaryTree(String s){ 
     data = s; 
     right = null; 
     left = null;   
    } 

    public void setLeft (BinaryTree l){ left = l; } 
    public void setRight(BinaryTree r){ right = r; }   
} 

Sorunuz ağaç dengeli olması gerektiğini önerir ve böylece bir elemanın yerleştirilmesi üzerine, özyinelemeli ağacın her tarafta düğümlerin sayısını kontrol etmelidir:

public int checkTree(){ 
    if(left == null && right == null){ 
     return 1; 
    }else if(left == null){ 
     return 1 + right.checkTree(); 
    }else if(right == null){ 
     return 1 + left.checkTree(); 
    }else{ 
     return 1 + left.checkTree() + right.checkTree(); 
    } 
} 

public void insert(BinaryTree bt){ 
    if(left == null){ 
     setLeft(bt); 
    }else if(right == null){ 
     setRight(bt); 
    }else{ 
     if(left.checkTree() <= right.checkTree()){ 
      left.insert(bt); 
     }else{ 
      right.insert(bt); 
     } 
    } 
} 

REDAKTE:

public class BinaryTree { 
    private BinaryTree right; 
    private BinaryTree left; 
    private String data; 
    private int weight; 

    public BinaryTree(String s){ 
     data = s; 
     right = null; 
     left = null; 
     weight = 1; 
    }  

    public void setLeft (BinaryTree l){ 
     left = l; 
     weight++; 
    } 

    public void setRight(BinaryTree r){ 
     right = r; 
     weight++; 
    } 

    public int getWeight(){ return weight; } 

    public void insert(BinaryTree bt){ 
     if(left == null){ 
      setLeft(bt); 
     }else if(right == null){ 
      setRight(bt); 
     }else{ 
      if(left.getWeight() <= right.getWeight()){ 
       left.insert(bt); 
       weight++; 
      }else{ 
       right.insert(bt); 
       weight++; 
      } 
     } 
    }  
}  

Answer 2

bir ikili ağaç en düşük solda elemanları ve sağda en yüksek vardır. Ama eğer gerçekten tüm bunları karıştırdıysanız (sıralı), 0 veya 1 ile sonuçlanan rand işlevini çağırabilir ve 0 ise sola, 1 sağa, rasgele giderse. Bu bir sıralanmamış ağacın neden olacaktır

Answer 3

Sonunda, String açıklamasında yer alan herhangi bir düğümü, yeni bir açıklamaya sahip olan yeni bir düğmeyle (eski açıkla birlikte yineleme dahil) değiştirmek istiyorum.

private Node searchBasedOnValue(String desc, Node currentNode) 
{ 
    Node result = null 
    if (currentNode == null) 
     return null; 
    if (currentNode.getDesc().equals(desc)) 
     return currentNode ; 
    if (currentNode.getLeftNode() != null) 
     result = searchBasedOnValue(desc,currentNode.getLeftNode()); 
    if (result == null) 
     result = searchBasedOnValue(desc,currentNode.getRightNode()); 
    return result; 
} 

IMO, düzenli Binary TreeBinary Search Tree denir sıralanır birini sıralanmış asla: Eğer olarak tüm ağaç aramak zorunda kalacak Bunun için

. Eklemek için istediğiniz şekilde işlem yapmanız gerekir. Ağacınızın sol ve sağ çocuğuna alternatif olarak düğümler ekleyebilir, böylece bir dereceye kadar dengelenebilir. Bu nasıl halledeceğinize bağlı.

Düzenli Binary Tree için daha fazla performans (lg(n)) daha iyi bir performans (lg(n)) ekleme, silme ve arama açısından kullandığımız çoğu zaman kullandığımız için çok pratik kullanım görmedim.

Answer 4

Sıralanmamışsa, neden ikili bir ağaç inşa etsin? Tam tarama yapmadan arama yapamazsınız, bu yüzden her şeyi bir diziye koyabilirsiniz, çünkü herhangi bir öğeye erişme, arama yapamama nedeniyle O (n) olur.

public Node(String desc, Node left, Node right) { 
     this.desc = desc; 
     this.left = left; 
     this.right = right; 
    } 

Sonra böyle ağaç oluşturmak: Eğer böyle bir yapıcı gerek

Birinci:

Answer 5

Bu şekli üzerinde herhangi bir kısıtlama olmaksızın bir sıralanmamış ikili ağaç oluşturmak için en hızlı yoldur

Node root = null; 
    for (String input: ...) { 
     root = new Node(input, root, null); 
    } 

Açıkçası, bu, arama yapmak için tüm düğümlere bakmayı gerektiren dengesiz, ayrılmamış bir ağaç verir. Ancak, ağaç ayrılmamışsa, ağacın dengesiz olduğu gerçeği fark etmez.

Genel olarak, sıralanmamış bir ağacın aranması, bir liste aramakla aynı karmaşıklığa sahiptir ve kod daha karmaşıktır.