以前玩过一个游戏：A心中选定一个1-1024之间的数，比如说是x，B来猜这个数；B每猜一个数，如果猜错了，A要告诉他x是比这个数大还是小。有趣的地方在于，无论A选的是什么数，B最多只要问10次，总能正确地猜出这个数来。

小时候总是对这个结论感到很神奇：上千个数，只要10次就能搞定，B是怎么做到的呢？其实方法并不难：B可以先问1和1024的中位数512；如果比512小的话，就问1和511的中位数（256）；如果比512大的话，就问513和1024的中位数（768）。每次询问都可以获得一个上限与下限，那么下一次就问这个范围里的中位数。以此类推，不出10次，一定可以将范围缩小到只有一个数。这种思路的本质是将所有数据排了个序（哪怕不连续的也没关系），然后编上号：比如3、7、1、6、9，那么第1个数就是1，第2个数就是3，第3个数就是6，然后7、9。最初我们的任务就是从编号1-5这五个数字里面找某个数，通过每次取中位数使范围折半，我们总能在对数次询问内找到这个数（或者是最终发现要找的数并不在序列里）。

好了，问题来了：如果结果总数是会变的该怎么办呢？比如说，NBA里每个球员都可以给出一个能力值，詹姆斯可以是97.5，科比是96.3，等等。这时候易建联加入了NBA，能力值是70.5。我们怎么储存阿联的相关信息，才能使得在较短的时间内就可以从全联盟的所有队员里找到阿联呢？

假定数据没有重复，那么按照刚才的思路，把联盟的人按照能力值排序，然后找到阿联的位置塞进去就可以了。但这样做会导致数据更新非常麻烦。设想在阿联来之前，NBA的档案管理员已经把大家按能力值排序，依次编号为1、2、3……。现在阿联来了，排在第5，那么从第6开始一直到最后一个，每个人的编号都要修改一遍，工作量非常之大。

一种可能的改进是把编号删掉。这样子，当阿联来的时候，我们只要把他的档案塞到对应位置就行了，不需要额外的修改工作。悲剧的是，这种储存方式下，找中位数就非常麻烦了。比如说联盟有1024个队员，按顺序存好，根据刚才的思路，我们要找阿联，当然先问阿联的能力值比排位512的那个队员高还是低。可是要想找到第512个队员，我们必须先把前511个队员检索一遍，心里不停地数着"1,2,3..."这意味着我们在对数时间内是很难找到阿联的，因为光是这一步就花了五百多次询问了。与其如此，还不如直接问“你是阿联吗”来的比较快一些。

有没有什么办法能让我们实现对数时间的查找，而又能很快地添加和删除新队员呢？模仿刚刚的思路，如果我们可以不从第一个开始找，而是直接从中位数开始，那就快多了，一下子就否定了一半的人。所以，我们放弃之前那种所有人从小到大排成一队的模式，代之以一种类似于族谱的结构进行储存。第512号球员在最上层，就好比是族谱里面的祖宗；它的长子是1-511的中位数，即第256号球员；次子是513-1024的中位数，第768号球员；孙子辈的结构与之类似。概括起来，每个球员都有最多两个儿子，其中长子是比它小的所有球员的中位数，次子是比他大的所有球员的中位数，一代一代向下繁衍。这样形成的数据结构，就是一种比较理想的binary-search tree。很显然，在这种数据结构中，沿着家族树向下找人，树有多高，最多便需要花多少时间。

可是树究竟有多高呢？如果只是最初那1024个人就好办了，由于后代都是指数增长的，树显然是对数那么高。可是随着时代的发展，大郅、姚明、阿联都来了，树要去旧迎新发生变化，这时候树的高度就不是那么容易确定了。很显然，要弄清这个问题，我们先要讨论新球员的加入是如何改变这棵树的。假定现在能力70.5的阿联来了，和找人类似，我们先把阿联先和祖宗比。由于我们假定了没有相同能力值的球员，所以阿联要么比祖宗牛一些，要么比祖宗渣一些。阿联要是牛，就沿着次子往下走，反之则沿着长子走。一路都没有跟阿联能力一样的人，所以一直向下走，走到树的最底层没人的位置，阿联就可以作为新的一代人成长起来了。概括而言，阿联加入联盟的过程，就是给阿联找爹的过程。

很显然，这种新队员加入的方式保持了binary-search tree的性质，即长子以及长子的后代都比父亲渣一些，次子以及次子的后代都比父亲牛一些，所以想找人的话，仍旧只需沿着某一谱系往下走，走到最底层就行了。可是最底层究竟有多深，或者说树究竟有多高？应该说，平均来看，树的高度还是非常乐观的，只保持在对数的数量级上。所谓平均，是指在构建这棵树的过程中，所有队员加入联盟的先后顺序是等可能的。换句话说，联盟有1024个人，阿联可能是第一个加入联盟的，也可能是第二个，也可能是第1024个，而且是等概率的；其他人也是一样。这在数学上表现为，1024个人的1024！种排列是等可能的。如果满足这样的假设，那么binary-search tree的表现整体上就还是很给力的。

当然，这样的假设其实并不一定合理。比如新秀往往能力值并不太高，所以我们可以预见，新秀成为长子的可能性应当比次子大。或者我们可以假设一种极端的情况，档案管理员有个死对头，偷偷地提前把所有1024名队员排了个序，然后按顺序把信息提供给档案管理员。这下管理员就会构建起一棵繁殖了1023代、一直没有长子（或次子）的树了。要想避免这种情况的发生，就要使用balanced binary-search tree，比如AVL tree、Red-black tree了。