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

Question

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

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

Answer 1

Итак, давайте начнем с определения, какой будет наихудший случай для этого алгоритма. 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) пространство в целом.

Answer 2

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

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

Вот (непроверенная) реализация в 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).