Минимальное поддерево, содержащее узлы из набора

Существует древовидная структура, например.

   1
  / \
 /   \
2     3
|    / \
|   /   \
4  5     6

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

[5, 6]

Как найти минимальное поддерево, содержащее все эти узлы и начинающееся с корневого элемента? Как это:

   1
    \
     \
      3
     / \
    /   \
   5     6

algorithm tree subtree
person mankers    schedule 28.11.2016    source источник
comment
Всегда ли дерево сбалансировано?   -  person User_Targaryen    schedule 28.11.2016
comment
@User_Targaryen Да, это так.   -  person mankers    schedule 28.11.2016
comment
Может ли значение узла появляться в дереве более чем в одном месте?   -  person j_random_hacker    schedule 28.11.2016

Ответы (3)


arrow_upward
2
arrow_downward

По сути, вы можете вернуться к листьям и найти для каждого листа, нужен он или нет. Когда рекурсия снова возвращается, вы можете увидеть, нужен ли какой-либо из потомков.

Вот псевдокод, который это делает:

def mark_needed_nodes(node, given_nodes):
    # If a leaf, check if it is in given_nodes
    if node is leaf:
        node.needed = node in given_nodes
        return node.needed

    # It is not a leaf; check if any of the descendants is needed.
    node.needed = False
    for child in node.children:
        node.needed = needed or mark_needed_nodes(child, given_nodes)
    return node.needed

Вы бы позвонили mark_needed_nodes(root, given_nodes).

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

person Ami Tavory    schedule 28.11.2016

arrow_upward
1
arrow_downward

Я думаю, нет необходимости обходить все дерево. Мы можем просто «провести линии» от каждого из заданных листовых узлов до корня.

Что-то вроде этого:

  1. отметьте корневой узел по мере необходимости.
  2. взять первый необработанный данный листовой узел. Если их нет, мы закончили.
  3. пометить текущий узел как необходимый.
  4. перейти к родителю текущего узла.
  5. если текущий узел уже нужен, перейдите к 2, иначе перейдите к 3.
person Tymur Gubayev    schedule 28.11.2016

arrow_upward
0
arrow_downward

Предположим, у вас есть k узлов в наборе запросов и n узлов в дереве. Если вам нужно выполнить много запросов к одному и тому же дереву, и дерево намного больше, чем типичный набор запросов, вы можете рассмотреть следующее решение.

Сложное решение за O(n)-время предварительной обработки, O(k)-время запроса

Вы можете сначала предварительно обработать свое дерево за линейное время, чтобы определить наименьшего общего предка пары узлов в постоянное время. Затем для данного запроса вы можете найти наименьшего общего предка двух узлов запроса, затем наименьшего общего предка этого узла и третьего узла в вашем запросе и т. д., чтобы определить наименьшего общего предка всех узлов в вашем запросе. запрос устанавливается за время O(k) в целом. Однако предварительная обработка и запросы сложны, и вряд ли это будет самым быстрым способом, если только ваше дерево не огромно по сравнению с размером вашего запроса, и у вас есть много отдельных запросов в одном дереве (так что время, затраченное на предварительную обработку, окупается).

person j_random_hacker    schedule 28.11.2016