078 | 从Binary Tree数据结构到具体问题的抽象化

今天我们从计算机的binary tree数据结构讲起，然后谈谈如何从很多具体的事物或者现象中抽象出具有共性的概念，和提出解决一大堆问题的通用工具。在讲述今天的内容之前，思考这个问题: 在我们真实的世界里，到底是具体的数值重要，还是数值之间相对的大小更重要，或者说相对的次序更重要？

我想绝大多数会这样说，“这得看具体情况了，比如体育比赛，成绩的相对值就比较重要，因为只要比其他选手得分高或者成绩好，就是冠军，至于你在百米比赛中是9.9秒还是10秒得到冠军，或者足球比赛中是1：0夺冠，还是5：0大圣，其实关系都不大。但是，在另一些地方，比如钱财方面，拥有1个亿，100万还是1万差别就大多了”。（哎哟，我从来没考虑到过这个问题啊，结合现实生活中的例子，很值得go deeper，在这是世界里，到底是具体的数值重要还是相对大小或者次序更重要？）

但是，如果必须让你在上述问题中做出二选一的回答，并且明确地告诉你，那种“既XXX，又XXX”的答案统统是零分，你会怎么办？如果你在面试中遇到了这样的两难，我告诉你一个技巧 —— 任何选择都比没有选择要好！在生活中也是如此，我们通常无法脚踩两条船。具体到上面的问题，在CS中其实是有明确的答案的，那就是相对的大小要比绝对的数量更重要。这一点，CS和数学、物理，化学都不相同留在数学上，数字是准确的；在物理中，水的冰点有一个确切的温度，水如果不到0度，是无法结冰的。但在CS里并不是这样的。AlphaGo在和柯洁下棋时，讲解棋局的几位高手有时会觉得下得莫名其妙，因为明明一步棋可以赢20目，它却要走一步稳妥的。原因其实很简单，计算机只看重相对的输赢。

世界上有什么样的问题，就有什么样的工具，或者说工具的发明是针对问题来的。（作为人类，我感觉好骄傲啊。It is a far better place that I go to, than I have ever gone. It is a place where I can talk and walk with those forerunners of humankind.）在数学上要计算数字，人类就发明了算盘。在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子，计时的钟，称重量的天平和秤等等。在化学上，人类就发明了各种有刻度的量器。在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为Binary Tree.（也就是说，在不同的领域里，还是需求逼出了进步和发明创造，灿烂的工具被supplied），为了有一个感性的认识，下面是示意图。我们可以将Binary Tree和自然界的树木对应起来。 

• 首先，它们都有一个根。Binary Tree的根就是图中顶上的红点。当然，为了将拉力把Binary Tree一层层扩展，Binary Tree的根画在了最顶端，而不是下面，你把自然界的大叔转180度就可以了。
• 其次，从根开始，它们都有分叉。只不过Binary Tree为了简单起见，只能有两个分叉，不能更多，这一点和自然界的树不同。每一个分叉也有自己的一个根节点，就是图中蓝色的那些点，你可以把它们想象成大树各级主干分叉前的部分。当然，你可能会问，如果遇到一个特殊的问题，需要三个分支怎么办？在数学上，两个分支和N个分支是等价的，或者说N个分支的情况可以通过两个分支来实现（Hmmm，这个没懂诶）。因此，为了简单起见，也为了更好的通用性，我们只研究Binary Tree就可以了。
• 最后，我们知道一棵树的树杈还能再分叉，Binary Tree也是如此，任何一个枝杈都可以再分叉两支，这个过程可以无限持续下去。

我们在生活中，一些组织结构其实就是树状结构，比如一个公司的大老板是根节点，每一个部门的老板是主干的根，下面职能部门的总监是枝干的根，再下面小组的经理是更小支子的根，最后基层员工是叶子节点。接下来，可能会有一个问题，这些怪怪的数据结构在CS中有什么用处呢？它的用途很多，比如说可以用于排序。前面我们介绍了一些排序的算法，无论是高效率的快速排序，还是最直观的冒泡排序，使用的都是昨天介绍的数组，或者说一个线性的列表。其实，Binary Tree可以直接完成排序，因为它有一个很好的性质，就是它左右两个分叉可以和比较大小后的两种结果自然对应起来。具体讲就是，用Binary Tree排序的过程只要遵循下面两条规则就可以了：

• 第一，先来的占据根部，以及靠近顶部层级比较高的位置，后来的放在相对靠下的位置。
• 第二，每当一个分支的根部被占据之后，接下来的数字，是和根部的数字进行比较，小的放到左边分叉中，大的放到右边的分叉中（哇，像是给大脑里的thought梳头一样，感觉好爽）

这样安排得出的Binary Tree，里面的数字从左到右自然是从小到大排好序的。为了便于理解这个操作的原则（吴军老师实在是太懂how to teach了，对很多事物的理解已经超一流的深了。），我们不妨打个比方。假如一个公司的组织架构是个Binary Tree，创始人最先来，因此占据了顶部位置，随后来的人是元老，直接汇报给创始人，因此放在了左右两个位置，你可以理解他们是事业部的副总裁。当然，我们加了一条规定，如果新人的个头比创始人矮，他就站在左边，比他高，就站在右边。再接下来，新来的人一级级地往下放，最后加入公司的只好到下面去当叶子了。但是在这个过程中还遵循另一个原则，矮个子的到左边高个子的到右边。最后，如果把这个公司的人从左往右扫一眼，个头正好越来越高。

这个方法的正确性我们就不证明了，我不妨给你看一个具体的例子。比如我们对（3，5，-2，0，6）这组数排序。

• 第一步，把3放到Binary Tree的顶端（根部）。
• 第二步，把5和树根的3做对比，由于5比3大，就放在右边叉数中，由于它是右边叉数上的第一个数字，因此就占据了右边叉数根部的位置。
• 第三步，把第-2拿来与根部的3对比，这次-2比3小，于是放在左边。同样，因为它是左边的第一个数，因此占据了左边叉数根的位置。
• 第四步，把0拿来和3对比，因为0比3小，所以放在左边的叉树中。但是，左边叉枝的根部已经被2占据了，因此0需要放到-2根部的左边的叉数下一层的某个位置，至于放在左边叉数下一层的左边还是右边，需要再和-2比较一次从而决定它的位置。由于0小于-2，因此放到了-2的右边。
• 第五步，把第五个，也就是最后一个数6拿来，先和根部的3比较一下，发现它比3大，因此放在右边的叉数中，但是右边的叉树根部已经被5占据，没有地方了，于是和右叉数的根点5比较了一下，发现比5大，因此要放在右叉数的右边。

​到此为止，所有的数字都放进了这棵Binary Tree里了。那么接下来呢？接下来你只要把Binary Tree数字从左到右取出来即可，从上面的过程我们可以看到，最左边的是-2，然后是0，中间根部是3，往右边是3和6。（-2，0，3，5，6）这样一来，把一堆数字按照一定的规则放到Binary Tree中，再拿出来，它们就有序了，神奇吧？（是的，非常神奇，有种给大脑的思绪梳头的感觉）当然，在计算机中这些数据一进一出需要时间，这个时间和快速排序是同一个量级。

Binary Tree这种数据结构的用途远不止排序，我举了排序的例子，只是为了说明它有用而已。在现实的工程中，Binary Tree可以做很多事情，比如快速查找到某一个数值。另外，由于网站的目录结构也是树状的（当然它们有N个分叉，hmmm，MCL就是有不同的分叉，并且我还在不停的耕耘和剪裁），因此，针对Binary Tree的各种算法，稍加改变就可以用于互联网。比如，我们找到一个网站后，要下载一个网站里面所有的网页，就会用到Binary Tree中的一种遍历（便利？）算法。

类似地，一个组织的管理结构也和Binary Tree类似。也就是说Binary Tree虽然是一种抽象的东西，在自然界中并不存在，但是它却浓缩了自然界很多事物的共性，那就是分叉、层层递进和有序。而针对这些共性，科学家们又总结出一些具有普遍性的算法，能够回过头来，应用到各种实际问题中。

在Google这样的公司面试时，不会考大家教科书上的那些基本内容，而会考如何利用那些工具（包括数据结构），解决一些实际问题（意思就是，虾兵一号：“接我北辰一刀流！”，天下第一的飞天御剑流的剑心不屑地丢了一句话：“少啰嗦！”，然后虾兵一号瞬间被割了喉咙领了盒饭。有时，在被强于自己的绝对力量终结前，安静一点、冷静一点、从容一点，就能晚一点并且更有尊严一点领盒饭啦。）。如果候选人能答得上来，说明书上的那些内容他已经掌握了。事实上，我们前面提到的如何找到周围最近的几个加油站，这个问就可以用Binary Tree的一些算法解决。（hmmm，我是这么想的，设定一个距离，比如剩下油量大概能跑到的距离，GPS会有方圆几十英里的加油站距离自己距离数据，比自己设定的距离大的，放到右边，小的放到左边，然后以此类推，最后最左边的5个椰子就应该是距离自己最近的5个加油站。）

今天的内容有点抽象，不过这是这周，也是这门课目前为止最难的内容了，（吴军老师太体贴了…这些内容估计是MIT，Berkeley，Stanford的CS101里第一个10分钟吧。）如果你坚持学习和消化了今天的内容，一定要恭喜你了，因为你已经上了一些CS系大二的课了。（天呢，Davis的CS真垃圾啊，CS10,20,30,40,50全部从最底层的语言讲起而不是从一开给你打下一个对于计算机世界的稳健的根基，Davis的就像是给了一堆砖头修卫生间卧室客厅却忘了自己在建的是一个building）

今天的总结：

• 1. 世界上的工具常常是根据所遇到的问题而发明的，有什么样的问题，就有什么样的工具。
• 2. 在CS中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构 —— Binary Tree
• 3. 很很多抽象的工具一样，Binary Tree其实能在现实生活中找到很多对应。除了比大小之外，我们的组织架构，我们的文件目录，网站的链接层次，以及我们明天要拆解的锦标赛，都能对应到Binary Tree中。
• 4. 所有能够对应到Binary Tree的问题，都有一些共性，解决它们之间问题的方法是可以触类旁通的。这就是我们要学习理论的目的，因为我们希望它能够在很多场合应用，而不只是一次，这一条很重要。（亲，谨记。）

Q：很多概念是生活中具体事物的抽象表述，比如正方形。能否再找出一些概念，讲讲它们是如何从现实生活中抽象出来。
A1：“象形文字”，馬，鳥，矛，田，以及很多繁体字
A2 ：计算机的数据比的是相对大小，而不是绝对数值。有一个笑话：两个人在森林里遇到一头狮子，其中一个人马上蹲下来系鞋带，另一个人正准备跑的人好奇地问对方为什么不跑，对方回答，不急，我只要待会比你跑得快就行了（这个太形象了）














​