Изучение дерева двоичного поиска

Question

Я считаю, что двоичное дерево поиска - это самый простой пример, но я действительно хотел бы знать, как исследовать тройное дерево поиска или несколько вариантов попыток. У меня нет опыта с ними, но я понимаю понятия добавления и поиска их.

Вопрос, когда я нахожу узел, который соответствует моему вводу (например, для автозаполнения), как эффективно собрать все дочерние узлы?

Answer 1

Это зависит от реализации вашего дерева поиска. Если получение всех дочерних узлов определенного узла является общей операцией, которую вам нужно выполнить, вы должны использовать реализацию, которая делает эту операцию эффективной.

Например, для каждого узла вы можете сохранить дочерний массив, содержащий указатели на каждый из дочерних узлов.

Answer 2

Для TRIE, вы должны иметь структуру узла в

class Node 
{ 
    char data; 
    ArrayList<Node> children; 

    public Node getChild(char data) 
    { 
     for(Node child : this.children) 
      if(child.data == data) 
       return child; 
     return null; 
    } 
} 

Каждый узел будет содержать символ и список его детей узла
Таким образом, ваш поиск будет loook что-то вроде этого

public boolean search(String s) 
{ 
    Node current = root;   // root is the Node present in Trie 
    for(int i=0; i<s.length(); i++) 
    { 
     char c = s.charAt(i); 
     Node n = current.getChild(c); 
     if(n==null) 
      return false; // Match not present 
     current = n; 
    } 
    return true;  // Match found 
} 

Вышеуказанный метод поиска просто проверяет, присутствует ли искомая строка в вашем trie. Вы можете настроить его, чтобы собрать всех детей в соответствии с вашим требованием (это сохраняется для вас :))

Надеюсь, это поможет вам и даст вам представление о том, как его собрать. Если вам нужна помощь в заполнении trie. Дайте нам знать!

ПРИМЕЧАНИЕ В узле Trie вы также можете указать boolean marker, чтобы указать конец слова. Вы можете использовать или не использовать его в зависимости от вашего приложения и использования.