Как найти первого общего предка узла в двоичном дереве? - PullRequest
Новая
       42

Как найти первого общего предка узла в двоичном дереве?

8 голосов
/ 11 мая 2011

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

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    if (covers(root.left, p) && covers(root.left, q))
        return commonAncestor(root.left, p, q);
    if (covers(root.right, p) && covers(root.right, q))
        return commonAncestor(root.right, p, q);
    return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}

Ответы [ 2 ]

9 голосов
/ 11 мая 2011

Хорошо, давайте начнем с определения наихудшего варианта для этого алгоритма. covers ищет дерево слева направо, поэтому вы получаете наихудший вариант поведения, если искомый узел является самым правым листом или его нет в поддереве вообще. В этот момент вы посетили все узлы в поддереве, поэтому covers равно O (n) , где n - количество узлов в дереве.

Аналогично, commonAncestor демонстрирует поведение в худшем случае, когда первый общий предок p и q находится глубоко внизу в дереве. В этом случае он сначала вызовет covers дважды, получая наихудшее время в обоих случаях. Затем он снова вызовет себя на правом поддереве, которое в случае сбалансированного дерева имеет размер n/2.

Предполагая, что дерево сбалансировано, мы можем описать время выполнения с помощью отношения повторения T(n) = T(n/2) + O(n). Используя основную теорему, мы получаем ответ T(n) = O(n) для сбалансированного дерева.

Теперь, если дерево не сбалансировано, мы могли бы в худшем случае только уменьшить размер поддерева на 1 для каждого рекурсивного вызова, что приведет к повторению T(n) = T(n-1) + O(n). Решение этой проблемы: T(n) = O(n^2).

Вы можете добиться большего, чем это, хотя.

Например, вместо простого определения, какое поддерево содержит p или q с помощью cover, давайте определим полный путь к p и q. Это займет O(n), как и cover, мы просто храним больше информации. Теперь пройдите эти пути параллельно и остановитесь там, где они расходятся. Это всегда O(n).

Если у вас есть указатели от каждого узла на их родителя, вы можете даже улучшить это, сгенерировав пути «снизу вверх», что даст вам O(log n) для сбалансированного дерева.

Обратите внимание, что это компромисс между пространством и временем, поскольку, пока ваш код занимает O(1) пробел, этот алгоритм занимает O(log n) пробел для сбалансированного дерева и O(n) пробел в целом.

0 голосов
/ 11 мая 2011

Как показывает ответ Хаммара , ваш алгоритм довольно неэффективен, так как многие операции повторяются.

Я бы использовал другой подход: вместо тестирования для каждого потенциального корневого узла, если два заданныхузлы не находятся в одном и том же поддереве (что делает его первым общим предком). Я бы определил пути от корня до двух заданных узлов и сравнил узлы.Последний общий узел на путях от корня вниз также является первым общим предком.

Вот (непроверенная) реализация в Java: 

private List<Tree> pathToNode(Tree root, Tree node) {
    List<Tree> path = new LinkedList<Tree>(), tmp;

    // root is wanted node
    if (root == node) return path;

    // check if left child of root is wanted node
    if (root.left == node) {
        path.add(node);
        path.add(root.left);
        return path;
    }
    // check if right child of root is wanted node
    if (root.right == node) {
        path.add(node);
        path.add(root.right);
        return path;
    }

    // find path to node in left sub-tree
    tmp = pathToNode(root.left, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    // find path to node in right sub-tree
    tmp = pathToNode(root.right, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    return null;
}

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    List<Tree> pathToP = pathToNode(root, p),
               pathToQ = pathToNode(root, q);
    // check whether both paths exist
    if (pathToP == null || pathToQ == null) return null;
    // walk both paths in parallel until the nodes differ
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next());
    // return the previous matching node
    return iterP.previous();
}

Оба pathToNode и commonAncestor находятся в O (n).

...