Website Logo. Upload to /source/logo.png ; disable in /source/_includes/logo.html

舞乐 VOLER

舞动我人生

最近公共祖先问题

Mar 28, 2016

从git merge说起

接着 使用Git协同工作 中的内容,使用伪代码描述git merge的原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
找到目标分支current和被合并分支merge的共同祖先分支ancestor;
// 在fix_bug分支上执行git merge master
// master为目标分支,fix_bug为被合并分支
if(ancestor == merge) {
  return;
} else if(ancestor == current) {
  fast forward merge,分支current指向merge
} else {
  确定ancestor与merge的差异
  try {
      将差异合并到current
    } catch(合并出现矛盾) {
      添加矛盾标记,通知用户解决矛盾
        return;
    }
    根据current、merge创建新的子分支
    分支current指向新的子分支
}

Git的分支结构为树形结构,这里找到两个分支的共同祖先分支,即求树中两个节点的最近公共祖先

如果每个分支可以确定其父分支,即树中节点具有指向其父亲的parent指针,那问题可以转化为求两个链表的公共节点。两个节点分别使用parent指针遍历到根节点root,遍历步数之差即两节点到公共节点的步数之差,由步数较大的节点先遍历步数之差对应的步数,接着两节点同时使用parent指针遍历,当parent指针的指向一致时,其指向即所求的公共节点。可以进一步参考 两链表的第一个公共结点

如果树为平衡二叉树,根据BST的性质,从根节点root开始遍历,如果当前节点的值同时大于两节点的值,说明两节点都位于当前节点的左子树,接下来向左子树遍历;如果当前节点的值同时小于两节点的值,说明两节点都位于当前节点的右子树,接下来向右子树遍历;如果当前节点的值位于两节点的值之间,那当前节点即所求的公共节点。

下面介绍使用Tarjan离线算法解决上述问题,Tarjan算法基于深度遍历和并查集,先介绍并查集相关的内容。

并查集

并查集详解 (转) 非常生动地介绍了并查集相关的内容,这里给出并查集的Java实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class UnionFindSet {

  private int[] set;
  private static final int INIT_SET_SIZE = 8;
  /** 参数超出并查集下标范围,返回ERROR_INDEX */
  private static final int ERROR_INDEX = -1;

  public UnionFindSet() {
      this(INIT_SET_SIZE);
  }

  public UnionFindSet(int size) {
      set = new int[size];
      for (int i = 0; i < set.length; i++) {
          set[i] = i;
      }
  }

  /**
  * 等价于find(x, true)
  * 
  * @param x
  * @return
  */
  public int find(int x) {
      if (outOfLength(x)) {
          return ERROR_INDEX;
      }

      if (set[x] != x) {
          set[x] = find(set[x]);
      }
      return set[x];
  }

  /**
  * 
  * @param x
  * @param compress
  *            是否压缩路径
  * @return x超出并查集下标范围,返回ERROR_INDEX;否则返回x的根元素
  */
  public int find(int x, boolean compress) {
      if (outOfLength(x)) {
          return ERROR_INDEX;
      }
      if (compress) {
          return find(x);
      }

      int temp = x;
      while (set[temp] != temp) {
          temp = set[temp];
      }
      return temp;
  }

  /**
  * 
  * @param x
  * @param y
  * @return x、y的根元素是否相等
  */
  public boolean query(int x, int y) {
      if (outOfLength(x) || outOfLength(y)) {
          return false;
      }
      return find(x) == find(y);
  }

  /**
  * 将x、y合并到同一根元素下
  * 
  * @param x
  * @param y
  */
  public void join(int x, int y) {
      int prex = find(x);
      int prey = find(y);
      if (prex != ERROR_INDEX && prey != ERROR_INDEX && prex != prey) {
          set[prex] = prey;
      }
  }

  private boolean outOfLength(int index) {
      return index < 0 || index >= set.length;
  }

}
Tanjar离线算法

理解并查集之后,Tanjar算法即将并查集与深度遍历有效结合,伪代码描述原理为

1
2
3
4
5
6
7
8
9
Tarjan(u) {
  begin
      设置u号节点的祖先为u
        深度遍历u的子树
        访问每一条与u相关的询问u和v
          -若v已经被访问过则输出v当前的祖先t
        标记u为已被访问将所有u的子节点包括u本身的祖先改为u的父节点
    end
}

具体的Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 *
 * @param node
 * @param queryList
 *            LCA查询条件列表,Query类的u、v属性为查询条件,即已知的两节点;ancestor属性保存查询结果,即公共节点
 */
public void tarjan(TreeNode node, ArrayList<Query> queryList) {
  node.ancestor = node;// 初始标记node的祖先为自己
  for (TreeNode child : node.children) {
      tarjan(child, queryList);// 深度遍历
      join(child, node);// 将子节点的祖先修改为node
  }

  node.searched = true;// 标记node已被访问
  // 遍历查询条件,如果查询条件与node相关且两节点已被访问,基于并查集查找公共节点
  for (Query query : queryList) {
      if (query.u == node) {
          if (query.v.searched) {
              query.ancestor = find(query.v);
          }
      } else if (query.v == node) {
          if (query.u.searched) {
              query.ancestor = find(query.u);
          }
      }
  }
}