读 Computing the nearest common ancestor

原文地址: http://codinggorilla.com/?p=91&cpage=1

这篇文章介绍了两种算法, Alstrup-Gavoille-Kaplan-Rauhe(AGKR) 和 Schieber-Vishkin. 他们是用来解决 Nearest Common Ancestor (NCA) 或者 Lowest common ancestor (LCA) 问题的.

首先, 文章给出了NCA/LCA问题的定义, 即在树状结构下, 求解任意两个node的最近公用node.

LCA/NCA

如上图中, node e和 node m 的公用node是a. 这个问题是 Alfred Aho教授提出的, 就是那个ac自动机匹配的那个a..

文章给出了一个最简单的算法

Simple Solution

这个算法是利用两个node的parent信息, 通过两个stack存储node的路径, 进而找到公用node. 这种解法的时间和空间复杂度是o(n). 最坏情况就是刚才的满树下的最左和最右.

Schieber-Vishkin算法是由Baruch Schieber 和 Uzi Vishkin 通过简化 Harel and Tarjan的算法得来的. 它的复杂度包含了两个部分, o(n)的preprocessing(预处理)阶段和o(1)的query(解答)阶段.

在预处理阶段, Schieber-Vishkin算法需要重新编码整颗树: 首先假设一棵树是满树时, 对一棵树做inorder traverse. 并且加一个数字计数器, 便有下图:

full tree after preprocessing

从左往右看, 最左节点是inorder下访问的第一个节点, 即标记1, 它的父节点标记2, 兄弟节点标记3. 这种标记后, 我们就给了满树下所有的节点可能的位置的数字表示.

这个编码方式有两个特性, 一个特性是, 通过数字标记, 我们可以用数学方法, 得到一个节点的高度. 即 height(v) = ⌊ log2(v & –v) ⌋ , 比如height(3) = ⌊ log2(00011 & -00011) ⌋ = ⌊ log2(00011 & -11101) ⌋ = ⌊ log2(00001) ⌋ = 0. 这个height是从底往上的, 比如 height(20) = ⌊ log2(10100 & -10100) ⌋ = ⌊ log2(10100 & -01100) ⌋ = ⌊ log2(00100) ⌋ = 2 , 这个2是从最底下的叶节点, 往上计算height的, 所以是2. 另外一个特性是, a(v, h) = ((v >> h) | 1) << h . 这里v是一个节点, h是这个节点的父节点的高度, 它返回的是这个节点高度为h的父节点. 比如

  • a(3,4) = ((3 >> 4) | 1) << 4 = ((0) | 1) << 4 = 1 << 4 = 16 node 3的高度为4的父节点是16
  • a(3,1) = ((3 >> 1) | 1) << 1 = ((1) | 1) << 1 = 1 << 1 = 2 node 3的高度为1的父节点是2
  • a(3,0) = ((3 >> 0) | 1) << 0 = ((3) | 1) << 0 = 3 << 0 = 3 node3的高度为0的父节点是自己(3).

如果理解以上两点, 就可以得出 NCAcbt(x, y) = ((x >> h) | 1) << h where h = ⌊ log2(x & –y) ⌋

由于NCA/LCA问题并不是二叉树下的问题, 所以对于其他形状的树, 需要做mapping到满二叉树. 所以这里引入一个head方法, Head(x) = v such that Inlabel(v)≠ Inlabel(Parent(v)) ∩ Inlabel(v) = x
head方法返回的是一个node, 这个node是在任意树上的x的父节点中标记和x的标记不同的点. 而其中的InLabel(v)就是把二叉完全树映射到一般树的方法.

附上一个实现:

package graphs.lca;

import java.util.*;
import java.util.stream.Stream;

// Answering LCA queries in O(1) with O(n) preprocessing
public class LcaSchieberVishkin {
    int[] parent;
    int[] preOrder;
    int[] I;
    int[] head;
    int[] A;
    int time;

    void dfs1(List<Integer>[] tree, int u, int p) {
        parent[u] = p;
        I[u] = preOrder[u] = time++;
        for (int v : tree[u]) {
            if (v == p) continue;
            dfs1(tree, v, u);
            if (Integer.lowestOneBit(I[u]) < Integer.lowestOneBit(I[v])) {
                I[u] = I[v];
            }
        }
        head[I[u]] = u;
    }

    void dfs2(List<Integer>[] tree, int u, int p, int up) {
        A[u] = up | Integer.lowestOneBit(I[u]);
        for (int v : tree[u]) {
            if (v == p) continue;
            dfs2(tree, v, u, A[u]);
        }
    }

    public LcaSchieberVishkin(List<Integer>[] tree, int root) {
        int n = tree.length;
        preOrder = new int[n];
        I = new int[n];
        head = new int[n];
        A = new int[n];
        parent = new int[n];

        dfs1(tree, root, -1);
        dfs2(tree, root, -1, 0);
    }

    int enterIntoStrip(int x, int hz) {
        if (Integer.lowestOneBit(I[x]) == hz)
            return x;
        int hw = Integer.highestOneBit(A[x] & (hz - 1));
        return parent[head[I[x] & -hw | hw]];
    }

    public int lca(int x, int y) {
        int hb = I[x] == I[y] ? Integer.lowestOneBit(I[x]) : Integer.highestOneBit(I[x] ^ I[y]);
        int hz = Integer.lowestOneBit(A[x] & A[y] & -hb);
        int ex = enterIntoStrip(x, hz);
        int ey = enterIntoStrip(y, hz);
        return preOrder[ex] < preOrder[ey] ? ex : ey;
    }

    // Usage example
    public static void main(String[] args) {
        List<Integer>[] tree = Stream.generate(ArrayList::new).limit(5).toArray(List[]::new);
        tree[0].add(1);
        tree[0].add(2);
        tree[1].add(3);
        tree[1].add(4);
        LcaSchieberVishkin lca = new LcaSchieberVishkin(tree, 0);
        System.out.println(0 == lca.lca(1, 2));
        System.out.println(1 == lca.lca(3, 4));
        System.out.println(0 == lca.lca(4, 2));
    }
}

上面的code是 https://github.com/indy256/codelibrary/blob/master/java/graphs/lca/LcaSchieberVishkin.java