Почему это решение общего предка имеет лучшую производительность в худшем случае? - PullRequest
Новая
       28

Почему это решение общего предка имеет лучшую производительность в худшем случае?

3 голосов
/ 17 июня 2019

Я смотрю на два решения, чтобы найти первого общего предка двух узлов в двоичном дереве (не обязательно в двоичном дереве поиска). Мне сказали, что второе решение обеспечивает лучшее время выполнения в худшем случае, но я не могу понять, почему. Может кто-нибудь, пожалуйста, просветите меня?

Решение 1:

  • Найдите глубину каждого из двух узлов: p, q
  • Рассчитать дельту их глубин
  • Установить указатель на более мелкий узел, указатель на более глубокий узел
  • Переместить указатель более глубокого узла вверх по дельте, чтобы мы могли начать движение с той же высоты
  • Рекурсивно посещать узлы частей обоих указателей, пока мы не достигнем того же узла, который находится вне первого общего предка 
import com.foo.graphstrees.BinaryTreeNodeWithParent;

/*
   Find the first common ancestor to 2 nodes in a binary tree.
*/
public class FirstCommonAncestorFinder {

    public BinaryTreeNodeWithParent find(BinaryTreeNodeWithParent p, BinaryTreeNodeWithParent q) {

        int delta = depth(p) - depth(q);
        BinaryTreeNodeWithParent first = delta > 0 ? q: p; // use shallower node
        BinaryTreeNodeWithParent second = delta > 0 ? p: q; //use deeper

        second = goUp(second, delta); // move up so they are level, if 1 node is deeper in the tree than the other, their common ancestor obviously cannot be below the shallower node, so we start them off at the same height in the tree


        //keep going up the tree, once first == second, stop
        while(!first.equals(second) && first !=null && second !=null) {
            first = first.getParent();
            second = second.getParent();
        }

        return first == null || second == null ? null : first;

    }

    private int depth(BinaryTreeNodeWithParent n) {
        int depth = 0;
        while (n != null) {
            n = n.getParent();
            depth++;
        }
        return depth;
    }

    private BinaryTreeNodeWithParent goUp(BinaryTreeNodeWithParent node, int delta) {

        while (delta > 0 && node != null) {
            node = node.getParent();
            delta--;
        }
        return node;
    }
}

Решение 2:

  • Убедитесь, что оба дерева (p, q) существуют в дереве, начиная с корневого узла
  • Убедитесь, что q не является потомком p и p не является потомком q, пройдя через их поддеревья
  • Рекурсивно исследовать поддеревья последовательных родительских узлов p, пока не будет найдено q 
import com.foo.graphstrees.BinaryTreeNodeWithParent;

public class FirstCommonAncestorImproved {

    public BinaryTreeNodeWithParent find(BinaryTreeNodeWithParent root,
                                         BinaryTreeNodeWithParent a,
                                         BinaryTreeNodeWithParent b) {

        if (!covers(root, a) || !covers(root, b)) {
            return null;
        } else if (covers(a, b)) {
            return a;
        } else if (covers(b, a)) {
            return b;
        }

        var sibling = getSibling(a);
        var parent = a.getParent();

        while (!covers(sibling, b)) {
            sibling = getSibling(parent);
            parent = parent.getParent();
        }
        return parent;
    }

    private BinaryTreeNodeWithParent getSibling(BinaryTreeNodeWithParent node) {
        if (node == null || node.getParent() == null) return null;
        var parent = node.getParent();
        return node.equals(parent.getLeft()) ? node.getRight() : node.getLeft();
    }

    private boolean covers(BinaryTreeNodeWithParent root,
                           BinaryTreeNodeWithParent node) {

        if (root == null) return false;
        if (root.equals(node)) return true;
        return covers(root.getLeft(), node) || covers(root.getRight(), node);

    }
}

1 Ответ

0 голосов
/ 18 июня 2019

Это зависит от структуры проблемы.

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

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

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

Set<Node> visited = new HashSet<>();
while (a != null && b != null) {
  if (visited.contains(a)) return a;
  if (visited.contains(b)) return b;
  visited.add(a);
  visited.add(b);
  a = a.parent();
  b = b.parent();
}
while (a != null) {
  if (visited.contains(a)) return a;
  a = a.parent();
}
while (b != null) {
  if (visited.contains(b)) return b;
  b = b.parent();
}
return null;
...