20 将疑犯加到搜索树中（第2/2页）

“但这个险值得冒。”Frank最终这样说道。

“但是……”

“如果我们的搜索没有那么高效率，也没有关系。相比抱着那么多本子走过大半个城市来说，这只是一个很小的代价。那些本子看起来重极了。”

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

节选自Drecker教授讲义

向二叉搜索树中加入节点和寻找一个节点类似。我们从根节点开始逐步向下，操作就和我们寻找想加入的值一样。我们通过比较想加入的值和当前节点的值的大小，来决定是该向左下还是向右下走。当我们遇到死路时，也就是需要走的方向的子节点并不存在时，我们便将要加入的值插入到这个不存在的子节点的位置。

插入一个元素的计算量和树的深度成正比。但是，我们不能保证在插入新节点时依然可以保持树的平衡。事实上，当你按特定的顺序插入时，树很容易就会因为有很深的分支而变得不平衡。比如，如果我们按排好序的顺序来插入数字，所有这些加入的节点都会沿着一条分支排列。