首页 > 试题广场 >

最佳二叉搜索树是？

[单选题]

最佳二叉搜索树是？

```
关键码个数最少的二叉搜索树
```

搜索时平均比较次数最少的二叉搜索树

所有结点的左子树都为空的二叉搜索树

所有结点的右子树都为空的二叉搜索树

推荐

牛客-007

答案：B

二叉搜索树上面的搜索相当于二分查找

所有节点的左子树或者右子树为空，则搜索退化为顺序查找，是最不理想的

二叉搜索树就是为了减少比较次数，所有平均搜索次数最少的二叉搜索树是最佳的

编辑于 2015-02-02 10:20:50 回复(1)

MyGoodHelper

B.搜索时平均比较次数最少的二叉搜索树

最优二叉查找树：

给定n个互异的关键字组成的序列K=<k1,k2,...,kn>，且关键字有序（k1<k2<...<kn），我们想从这些关键字中构造一棵二叉查找树。对每个关键字ki，一次搜索搜索到的概率为pi。可能有一些搜索的值不在K内，因此还有n+1个“虚拟键”d0,d1,...,dn，他们代表不在K内的值。具体：d0代表所有小于k1的值，dn代表所有大于kn的值。而对于i = 1,2,...,n-1,虚拟键di代表所有位于ki和ki+1之间的值。对于每个虚拟键，一次搜索对应于di的概率为qi。要使得查找一个节点的期望代价（代价可以定义为：比如从根节点到目标节点的路径上节点数目）最小，就需要建立一棵最优二叉查找树。

发表于 2015-01-18 15:33:16 回复(0)