Ищем быстрый алгоритм нахождения расстояния между двумя узлами в двоичном дереве

Question

Как мне найти расстояние между двумя узлами в двоичном дереве? Эквивалентно, какие существуют алгоритмы для нахождения самого последнего общего предка (самого низкого общего предка) двух узлов?

Answer 1

1. вычислить список предков для каждого узла
2. найти общий префикс
3. последний элемент из общего префикса является самым низким общим предком
4. удалитьобщий префикс из обоих списков предков
5. расстояние - сумма длин остальных списков + 1

Answer 2

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

Answer 3

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

Если вы выполняете разовую работу только линейно по размеру дерева, то получается, что вы можете найти наименьшего общего предка из любых двух узлов за постоянное время (независимо от того, насколько глубоко дерево). Смотри http://en.wikipedia.org/wiki/Lowest_common_ancestor

Алгоритм Баруха Шибера и Узи Вишкина для наименьшего общего предка является абсолютно практичным для использования и программирования.

Answer 4

здесь - реализация DP для расстояния BT. Не оптимально, но интересно. 1-е дерево создает с входным массивом.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by juanmf on 05/02/17.
 */
public class Main2 {
    /**
     * {50, 60, 30, 10, 20, 40} will form a Node Structure as follows
     * 5
     * ├─L─ 3
     * │   ├─L─ 1
     * │   │   └─R─ 2
     * │   └─R─ 4
     * └─R─ 6
     * L: left
     * R: Right
     * Path should be: [4, 3, 1, 2]
     * steps: 3 <- output
     *
     * @param args
     */
    public static void main(String[] args) {
        int i = pathSteps(new int[] {50, 60, 30, 10, 20, 40}, 6, 20, 60);
        System.out.println(i);
    }

    private static int pathSteps(int[] ints, int n, int from, int to) {
        Node root = null;
        Map<Node, Node> allNodes = new HashMap<>();

        for (int i: ints) {
            if (root == null) {
                root = new Node(i);
                allNodes.put(root, root);
            }
            root.addNode(i, allNodes);
        }
        Map<Node, List<Node>> cache = new HashMap<>();

        Node fromN = new Node(from);
        Node toN = new Node(to);

        if (! allNodes.containsKey(fromN) || ! allNodes.containsKey(toN)) {
            return -1;
        }
        fromN = allNodes.get(fromN);
        toN = allNodes.get(toN);

        List<Node> path = traverse(fromN, toN, cache);
        return path.size() - 1;
    }

    private static List<Node> traverse(Node fromN, Node toN, Map<Node, List<Node>> cache) {

        if(cache.containsKey(fromN)) {
            System.out.println("cache Hit: " + fromN);

            return cache.get(fromN);
        }
        System.out.println("visiting: " + fromN);
        if (fromN == null || fromN.visited) {
            return new ArrayList<>();
        }
        if (fromN.equals(toN)) {
            List<Node> target = new ArrayList<>();
            target.add(toN);
            return target;
        }
        fromN.visited = true;

        List<Node> parentWay = new ArrayList<>();
        List<Node> lchildWay = new ArrayList<>();
        List<Node> rchildWay = new ArrayList<>();

        parentWay.addAll(traverse(fromN.parent, toN, cache));
        lchildWay.addAll(traverse(fromN.lchild, toN, cache));
        rchildWay.addAll(traverse(fromN.rchild, toN, cache));

        List<Node> shortest = getShortestList(getShortestList(parentWay, lchildWay), rchildWay);

        cache.put(fromN, shortest);
        if (! shortest.isEmpty()) {
            shortest.add(fromN);
        }
        fromN.visited = false;
        System.out.println(shortest);
        return shortest;
    }

    private static List<Node> getShortestList(List<Node> l1, List<Node> l2 ) {
        List<Node> shortest = null;
        if (l1 != null & l2 != null) {
            if (l1.isEmpty()) {
                shortest = l2;
            } else if (l2.isEmpty()) {
                shortest = l1;
            } else {
                shortest = l1.size() < l2.size() ? l1 : l2;
            }
        } else if (l1 == null) {
            shortest = l2;
        } else if (l2 == null) {
            shortest = l1;
        }
        return shortest;
    }

    private static class Node {
        Node parent;
        Node lchild;
        Node rchild;

        final int value;
        public boolean visited;

        private Node(int value) {
            this.value = value;
        }

        public void addNode(int i, Map<Node, Node> allNodes) {
            if (i > value) {
                if (null == rchild) {
                    rchild = new Node(i);
                    rchild.parent = this;
                    allNodes.put(rchild, rchild);
                } else {
                    rchild.addNode(i, allNodes);
                }
            }
            if (i < value) {
                if (null == lchild) {
                    lchild = new Node(i);
                    lchild.parent = this;
                    allNodes.put(lchild, lchild);
                } else {
                    lchild.addNode(i, allNodes);
                }
            }
        }

        @Override
        public boolean equals(Object obj) {
            return ((Node) obj).value == value;
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }
}

Answer 5

Во-первых, искать высоту первого элемента. Кроме того, верните путь к нему, используя связанный список. Вы можете сделать это за O (logN) время. Предположим, дерево сбалансировано, где высота logN. пусть H1 = высота первого элемента.

Тогда, ищите высоту ко второму элементу. Кроме того, верните путь к нему, используя связанный список. Вы можете сделать это за O (logN) время. Пусть H2 = высота второго элемента.

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

Таким образом, самый длинный путь H1 + H2 - 2 * H3 (поскольку вам нужно H1, чтобы перейти к H1, и H2, чтобы перейти к H2. Но на самом деле, Вы можете проследить от H1 до H1-H3. а затем перейти к H2 от H3. Так что это (H1-H3) + (H2-H3) = H1 + H2 -2 * H3.

Детали реализации должны быть простыми

search(Tree* Head, Node* Value, LinkedList path, int distance); 

Таким образом,

search(Head, Value1, path1, height1); 
search(Head, Value2, path2, height2); 

i = 0; 
while (path1[i] == path2[i])
{
    i++; 
}
height3 = i-1; 
return height1+height2- 2*height3; 

Сложность времени: O (logN) + O (logN) + O (logN) = O (logN) Сложность пространства: O (logN) (для хранения обоих связанных списков расстояний)

Answer 6

Сделайте два набора, состоящих из предков каждого: пока объединение наборов пусто, добавьте следующего предка каждого узла в соответствующий список Когда есть общий узел, это общий предок.

Answer 7

1. Найдите Наименьшего общего Предка (LCA), как мы это делали в Q56. См. оба подхода, чтобы найти LCA . Я бы предпочел первый подход, так как он хранит путь каждого узла, который мы можем использовать, чтобы найти расстояние ч / б узла до LCA
2. Теперь посчитайте количество узлов в пути 1 и пути 2. Общее расстояние / вершины будет (Путь 1 Узлы -1) + (Путь 2 Узлы -1)