从上例看到,成功的折半查找过程恰好是走了一条从判定 树的根到被查记录的路径,经历比较的关键字次数恰为该记录 在树中的层数 若查找失败,则其比较过程是经历了一条从判定树根到某 个外部节点的路径,所需的关键字比较次数是该路径上內部节 点的总数。从上例看到，成功的折半查找过程恰好是走了一条从判定 树的根到被查记录的路径，经历比较的关键字次数恰为该记录 在树中的层数。 若查找失败，则其比较过程是经历了一条从判定树根到某 个外部节点的路径，所需的关键字比较次数是该路径上内部节 点的总数