题目描述
假设给定一个n个不同关键字的严格升序序列K=<k[1], k[2], …, k[n]>，用这些关键字构造二叉搜索树。对关键字k[i]，有p[i]次被检索到。有些搜索的值可能不在K中，假设n+1个伪关键字D=<d[0], d[1], …, d[n]>，对i=1, 2, ..., n-1，d[i]表示在k[i]和k[i+1]之间的值，d[0]表示小于k[1]的值，d[n]表示大于k[n]的值。对每个伪关键字d[i]，有q[i]次被检索到。请注意这里规定了每个关键字和伪关键字的检索次数。假设给定一个n个不同关键字的严格升序序列K=<k[1], k[2], …,
