读 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(xy) = ((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)就是把二叉完全树映射到一般树的方法.

附上一个实现:

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