GIT原理之最近公共祖先

2021年11月24日 阅读数:3
这篇文章主要向大家介绍GIT原理之最近公共祖先,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

 

https://labuladong.gitee.io/algo/2/18/30/git

 

读完本文,你不只学会了算法套路,还能够顺便去 LeetCode 上拿下以下题目:面试

236.二叉树的最近公共祖先(中等)算法

———–oop

若是说笔试的时候喜欢考各类动归回溯的骚操做,面试其实最喜欢考比较经典的问题,难度不算太大,并且也比较实用。翻译

上篇文章 四个命令玩转 Git 写了 Git 最经常使用的命令,没有提分支合并,其实分支合并没什么困难的,主要就是 merge 和 rebase 两种方式。本文就用 Git 的 rebase 工做方式引出一个经典的算法问题:最近公共祖先(Lowest Common Ancestor,简称 LCA)。code

好比 git pull 这个命令,咱们常常会用,它默认是使用 merge 方式将远端别人的修改拉到本地;若是带上参数 git pull -r,就会使用 rebase 的方式将远端修改拉到本地。blog

这两者最直观的区别就是:merge 方式合并的分支会有不少「分叉」,而 rebase 方式合并的分支就是一条直线。leetcode

对于多人协做,merge 方式并很差,举例来讲,以前有不少朋友参加了在 GitHub 上的仓库翻译工做,GitHub 的 Pull Request 功能是使用 merge 方式,因此你看 fucking-algorithm 仓库的 Git 历史:开发

画面看起来很炫酷,但实际上咱们并不但愿出现这种情形的。你想一想,光是合并别人的代码就这般群魔乱舞,若是说你本地还有多个开发分支,那画面确定更杂乱,杂乱就意味着很容易出问题,因此通常来讲,实际工做中更推荐使用 rebase 方式合并代码。get

那么问题来了,rebase 是如何将两条不一样的分支合并到同一条分支的呢:

上图的状况是,我站在 dev 分支,使用 git rebase master,而后就会把 dev 接到 master 分支之上。Git 是这么作的:

首先,找到这两条分支的最近公共祖先 LCA,而后从 master 节点开始,重演 LCA 到 dev 几个 commit 的修改,若是这些修改和 LCA 到 master 的 commit 有冲突,就会提示你手动解决冲突,最后的结果就是把 dev 的分支彻底接到 master 上面。

那么,Git 是如何找到两条不一样分支的最近公共祖先的呢?这就是一个经典的算法问题了,下面来详解。

_____________