什么是树数据结构

数据分成枝

前面看过把数据排成一排的方法。一排看起来整齐，可要找想要的值，有时得从一头一路扫过去。
所以这次换个形状。在最上面放一个根，从那里长出两根枝，每根枝上再各长出两根。像这样分叉的形状叫作树，放值的每一个位置叫作节点，这一课把它叫作格子。

点一下根，把枝展开。每点一次，就再多分出一层。

分得越多，格子增加得越快：每往下一层，格子数就翻一倍。
可是，这种形状为什么适合查找？秘密在于分叉的方向。从根选枝的时候，不是随便往哪边走，而是按规则只选一边。下面就来看看这个规则。

每走一步就缩小一半

往树里放值的时候，先定一条规则：比某个格子小的值放在它的左枝，大的值放在右枝。遵守这条规则的树，叫作二叉搜索树。
这样一来，查找就非常方便。要找的值比当前格子小，就把右边整个扔掉，只看左边；比它大，就反过来把左边整个扔掉。每选一次，剩下的候选就少掉一半。

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

每选一次，候选就一下子减半。扔掉的枝不用再看，因为有规则在，就知道答案不在里面。
所以格子再多，选几次就能很快缩小范围。那么，实际定一个目标，从根开始跟着走走看。

几步就找到

现在定一个目标值，从根开始往下跟。把根格子和目标比一比，按规则往左或往右走下去。到了那根枝，再比一次，再往下走。
一直重复同样的事，直到到达目标格子。数一数走了几步，会惊讶地发现比想象的少得多。

定好目标，从根开始一格格往下走。走了几步会同时数出来。

就算是七个格子的树，最多三步也就到了。要是排成一排，最后面的值得看七次。
多亏了树的形状，少看很多次就找到了。那么，格子再多一些，步数也会跟着同样多吗？下面亲手把它变大看看。

深度就是步数

树的深度，就是从根到最下面的步数。这也正是查找时最多要走的步数。
有意思的是，格子翻一倍，深度只多一步。格子再翻一倍，也只再多一步。所以就算数据多得惊人，步数也增长得非常慢。像这样规模每翻一倍才多一步的增长，叫作对数增长。

点一下格子数，让它一倍倍地增加。格子猛增，深度（步数）却只一步步慢慢增加。

格子从一千变成两千，深度也只多了一步。就算有一百万个格子，不到二十步也能到达。
这才是树形状真正的力量。数据再怎么膨胀，查找的步数几乎不增加。所以处理大数据时，树用得这么多。

小结

用一句话概括：把数据摆成树枝的形状，也就是树。靠着“小的往左、大的往右”这条规则，每走一步候选就少一半。
所以就算有几千个，几步也能找到。步数，也就是深度，决定了速度。数据翻一倍，深度只多一步。这和从中间翻开词典、一半一半地缩小范围完全一样。

依次点要点回顾一下。（数据分成枝 → 每步缩一半 → 几步就找到 → 深度 = 步数）

现在你知道为什么把数据摆成树就能快速查找了。不过有一点让人放不下：放值的顺序不好，比如从小到大依次放进去，树就会只往一边长得又细又长，变成歪的。
那样一来，每次减半的长处就没了，和一排排地扫没什么两样。下一课讲树怎样自己把两边调得均匀。