21 二叉搜索树的属性

“等等，”Frank说，“错了。”

Socks刚刚插入了一个节点，他惊讶地抬起头，问道：“什么？”

“你刚刚插入的那个节点，”Frank说，“插错地方了。”

Socks盯着树：“但是63确实是大于60，所以需要将它加进右子树啊。”

“但是它比它的祖父节点61都要大，所以应该把它加入到61这个节点的右子树，你却把它加入了左子树。二叉搜索树的一个关键属性是左子树中的所有节点的值都小于当前节点的值，而右子树中的所有节点的值都要大于当前节点的值。”

“我知道。”Socks安静地说。

“那它为什么会在左子树中？”Frank问。

“我犯了一个错误。”Socks说。

“你为什么忘记将61与63进行比较？”Frank问。

“我……我是从60这个节点开始的。”Socks承认。

“什么？”

“嗯，我最近一次插入的节点是60……63和60比较接近……所以我刚刚从节点60开始，就将其插入到了60的下面。”

“你没有从树根开始？”Frank嚷道。

“我想这样会更快，”Socks说，“这样可以跳过树中大部分节点。”

“你最终把它放在了错误的地方！有多少个节点使用了这种投机取巧的方式？”

“有几个吧。”Socks承认道。

Frank长叹一声，便开始一连串的抱怨和咒骂。Socks盯着地面明智地没有吭声。

在他终于平静下来后，Frank深吸了一口气，重新开始观察这棵树。

“我们必须做一个穷举搜索，”Frank从牙缝里硬挤出了几句话，“如果这棵树没能维持二叉搜索树的属性，我们就不能安全地做任何剪枝。我们必须检查每个节点。

“嘿，”Socks突然说，“如果我们必须检查每个节点后再把它插入到树中，那我们为什么不直接做一个穷举搜索呢？”

“摊销时间成本，”Frank说，“将来我希望使用这棵树进行多次搜索。我猜测50天到70天才是我们应该搜索的范围。当我们有更多依据时，我们可以再进行不同范围的搜索。我们甚至可能要去做一些更加精确的搜索。构建树的成本将在多次搜索中被平摊，这样平均的时间成本就会比较低，总的时间成本也会比较低。摊销时间成本是考虑了多次搜索的总体时间成本，从而将构建树的成本分摊到很多次的搜索中。”

“哦，”Socks说，“像我的魔术按钮树。”

Frank本想用力摇晃这个年轻巫师并大喊“当然像按钮树了！它们两个都是二叉搜索树！”，不过他努力控制住了自己，只是无奈地嘲讽道：“当然了。”

“好主意，”Socks说，“未来我们可以节省大量的时间。”

“是‘可能’会节省。”Frank纠正他。

“哦，”Socks说，“对。我破坏了这个树，不是吗？”

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

节选自Drecker教授讲义

正如我们在讲义中所看到的，我们可以使用二叉搜索树的结构来进行有效的搜索。不仅如此，我们还可以往树中添加和删除节点。但是，每当我们更改了原有数据的结构时，必须要确保不能破坏二叉搜索树的属性，这非常重要。

对于二叉搜索树，最重要的是时刻保持二叉搜索树的属性。该属性规定（1）左子节点（及其所有左子节点）中的值小于或等于当前节点的值，以及（2）右子节点（以及其所有右子节点）中的值大于或等于当前节点的值。如果我们违反这个属性，此时这棵树就不再是一棵二叉搜索树，我们也不能在搜索时进行任何剪枝。