从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);
}
}
}
}