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

Question

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

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

Answer 1

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

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

Answer 2

Для Trie у вас должна быть структура Node как

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;
    }
}

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

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 вы также можете сохранить boolean marker указать конец слова. Вы можете использовать или не использовать его в зависимости от вашего приложения и использования.