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

Question

Допустим, я хотел, чтобы все узлы, чьи родители соответствовали определенному условию.

Есть ли приемлемый способ сделать это, кроме проверки каждого узла и построения объекта результатов, полного либо узлов, либо поддеревьев?

Answer 1

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

Answer 2

Вот и все.Вам просто нужно получить доступ к каждому узлу, чтобы увидеть, соответствует ли он критериям.

Но есть несколько способов ускорить его:

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