用树的形状逐步缩小，树

数据分成枝

前面我们学过
把数据排成一行的方法。
一行看着整齐，
可要找中间的值，
有时得从一头一路走过去。
所以这次换个形状。
顶上放一个根，
从它分成两枝。
每枝再分两枝。
这种分叉的形状叫树。

点一下根来展开枝。每点一次就多分一层。

越分，格子越快变多。
每一层枝就翻一倍。
可这个形状
为什么适合查找呢?
秘密在分叉的方向。
从根选枝的时候
不是随便走，
而是带着规则只选一边。
那个规则下面来看。

每一步缩小一半

把值放进树时
定一条规则。
比某个格小的值放左枝，
大的放右枝。
这样查起来很省事。
要找的值比当前格小，
就把整个右边扔掉，只看左边。
大，就反过来把整个左边扔掉。
每选一次，
剩下的候选就消失一半。

把要找的值和当前格比一比: 小点左边，大点右边。每点一次剩下的候选少一半。

每选一次，
候选就一下掉到一半。
扔掉的枝再也不用看。
靠规则你就知道
答案不在它里面。
所以格子再多，
选几次就很快缩小。
那就定个目标，
从根跟着走一遍吧?

几步就找到

现在定一个目标值，
从根跟着走。
把根的格和目标比，
按规则往左或往右下。
到那枝再比，再往下。
直到走到目标格，
重复同样的事。
数数走了几步，
你会惊讶它少得出奇。

定个目标，从根一格格往下走。它会一起数走了几步。

哪怕是七格的树，
最多三步就到了。
要是排成一行，
最后那个值得看七次。
靠树的形状，
看少得多就找到了。
那么格子再多起来，
步数也会猛涨吗?
下面自己来加加看。

深度就是步数

树的深度，
是从根到最底的步数。
那也正是查找
最多要走的步数。
有趣的是，格子翻一倍，
深度只多一步。
再翻一倍，再多一步。
所以数据多到惊人，
步数也涨得很慢。
这样慢慢加深，
我们说它像对数那样长。

点一下把格子数翻倍。格子猛增，但深度(步数)只一步步慢慢加。

格子从一千变两千，
深度也只多了一步。
哪怕一百万格，
二十步以内就到。
这正是树形状的真本事。
数据再怎么膨胀，
查找的步数几乎不涨。
所以处理大数据时，
树的形状用得那么多。

来理一理

归成一句话，是这样。
把数据摆成枝的形状，树。
用小走左、大走右的规则，
每一步候选少一半。
所以几千个也几步就找到。
步数，也就是深度，就是速度。
数据翻一倍，
深度只多一步。
这就跟从中间翻开词典、
一半一半缩小一样。

依次点要点回顾一下。(分成枝 → 缩小一半 → 几步找到 → 深度 = 步数)

现在你知道把数据
摆成树为什么找得快了。
不过有一点稍微挂心。
要是放值的顺序不好，
树可能只往一边长长的，
变成歪歪的树。
那减半的妙处就没了。
怎么才能让树
两边匀称呢?
那个平衡的事，下一讲来看。