Dynamic Programming: Optimal Binary Search Tree

目录

1. 最优二叉搜索树简介
2. 举例以及详细分析
3. 代码块
4. 测试结果

最优二叉搜索树简介

1、概念引入

基于统计先验知识, 我们能够计算出一个数表（集合）中各元素的查找概率, 即各元素出现频率的度量. 例如, 在中文输入法的词库中, 各词条（单字、词组等）的先验概率可以根据用户的使用习惯自动调整, 这种做法通常被称为动态调频或高频优先显示原则. 其意义在于减少用户的查找次数. 在最优二叉查找树问题中, 我们的目标是通过最少的关键码比较次数来实现键值的有效查找. 为此, 我们需要对集合中的每个元素赋予一个特殊属性——查找概率. 因此, 构造一颗具有最少键值比较次数的最优二叉查找树就成为了解决这一问题的核心任务.

2、最优二叉搜索树

最优二叉查找树：
给定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的概率