18 建造二叉搜索梯（第2/2页）

在当时，整个表演看起来棒极了。但现在，坐在已经被变成武器的二叉搜索树上面，Frank觉得这整个想法实在太愚蠢了。他简直无法理解当时他为什么会觉得这种递归分割画的方式很有美感。

耳边的嘶嘶声将Frank的思绪带回了现实。一条铁蛇的头爬上了平台，正在寻找Frank。眼前的蛇其实只是一条会动的铁栏杆，它们没有眼睛，没有鼻子，也没有嘴巴。Frank很不能理解它们到底是用什么来寻找的。也许它们能感应到震动？

他想把蛇踢下去，但最终决定不这样做。因为铁蛇虽然并没有嘴巴，但毒性却难以置信得大。

Frank决定继续撤退。他走到了上一层梯子旁边，并将自己拉了上去。这时候他的脚踝已经没有那么疼了，所以他得以以一个正常的姿势来爬这截梯子。

Frank一直向上爬着。一会儿便回到了顶层写着50的那层平台。

他定了一会儿神儿，心中再一次开始咒骂二叉搜索梯。虽然没有任何具体的理由，他现在坚信二叉搜索梯是一个愚蠢的设计。Frank满意地点了点头，爬回了街道上，逃离了那些铁蛇。

警用算法导论：二叉搜索树Ⅱ

节选自Drecker教授讲义

你可以从一个排好序的数组中创建出一棵二叉搜索树。你只需要不断递归地将所有元素划分成更小的集合。在每一层中，选择最中间的那个元素作为那一层的节点。如果元素个数为偶数，那么随意选择中间两个元素中的一个就行。

创建好根节点之后，可以用同样的方式来分割左边的元素和右边的元素。从概念上来说，我们将排好序的数组分成了左右两个数组，并将同样的算法作用于它们上面。

但实际在建造这棵树的时候，我们不需要真正去分割或者复制这个数组。整个算法可以只使用一个数组，我们只要记录好当前分支中最小和最大元素的下标编号就好了。