1, 问题描述
给定一个由 n 个互异的关键字组成的有序序列 K={k1<k2<k3<,......,<kn}和它们被查询的概率 P={p1,p2,p3,......,pn}, 要求构造一棵二叉查找树 T, 使得查询所有元素的平均比较次数最小.
对于一个搜索树, 当搜索的元素在树内时, 表示搜索成功. 当不在树内时, 表示搜索失败, 用一个 "虚叶子节点" 来标示搜索失败的情况, 又因为二叉树具有左右结点, 因此需要 n+1 个虚叶子节点 {d0<d1<......<dn}, 对应于 di 的概率序列是 Q={q0,q1,......,qn}. 其中 d0 表示搜索元素小于 k1 的失败结果, dn 表示搜索元素大于 kn 的失败情况. di(0<i<n) 表示搜索节点在 ki 和 k(i+1)之间时的失败情况. 搜索成功与搜索失败概率和为 1, 因此有如下公式:
由每个关键字和每个虚拟键被搜索的概率, 可以确定在一棵给定的二叉查找树 T 内一次搜索的平均搜索路径长度(也即平均比较次数). 设一次搜索的实际代价为检查的节点个数, 即在 T 内搜索所发现的节点的深度加上 1. 所以在 T 内一次搜索的期望代价为:
需要注意的是: 一棵最优二叉查找树不一定是一棵整体高度最小的树, 也不一定总是把最大概率的关键字放在根部.
最优二叉搜索树_动态规划(还未写完, 尚待补充)
来源: http://www.bubuko.com/infodetail-3282596.html