0020算法笔记——【动态规划】最优二叉搜索树问题 - liufeng_king的专栏 - 博客频道 - CSDN1
需积分: 0 42 浏览量
2022-08-03
19:07:12
上传
评论
收藏 888KB PDF 举报
2014/12/30 0020算法笔记——【动态规划】最优二叉搜索树问题liufeng_king的专栏博客频道CSDN.NET
http://blog.csdn.net/liufeng_king/article/details/8694652 1/8
liufeng_king的专栏
分类：算法
2015年4月微软MVP申请《京东技术解密》有奖试读，礼品大放送“我的2014”年度征文活动火爆开启CSDN2014博客之星
0020算法笔记——【动态规划】最优二叉搜索树问题
2013032010:37 3339人阅读 评论(4) 收藏 举报
最优二叉搜索树 算法笔记 最小平均路长 四边形不等式 动态规划
1、问题描速：
设S={x1,x2,···,xn}是一个有序集合，且x1,x2,···,xn表示有序集合的二叉搜索树利用
二叉树的顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的元素x大于其左
子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶
顶点是形如(xi,xi+1)的开区间。在表示S的二叉搜索树中搜索一个元素x，返回的结果有两
种情形：
(1)在二叉树的内部顶点处找到：x=xi
(2)在二叉树的叶顶点中确定：x∈(xi,xi+1)
设在情形(1)中找到元素x=xi的概率为bi；在情形(2)中确定x∈(xi,xi+1)的概率为ai。其
中约定x0=－∞,xn+1=+∞,有
集合{a0,b1,a1,……bn,an}称为集合S的存取概率分布。
最优二叉搜索树：在一个表示S的二叉树T中，设存储元素xi的结点深度为ci；叶结点（xj，
xj＋1）的结点深度为dj。
注：在检索过程中，每进行一次比较，就进入下面一层，对于成功的检索，比较的次数就是所在的层数
加1。对于不成功的检索，被检索的关键码属于那个外部结点代表的可能关键码集合，比较次数就等于此外
部结点的层数。对于图的内结点而言，第0层需要比较操作次数为1，第1层需要比较2次，第2层需要3次。
p表示在二叉搜索树T中作一次搜索所需的平均比较次数。P又称为二叉搜索树T的平均
路长，在一般情况下，不同的二叉搜索树的平均路长是不同的。对于有序集S及其存取概
率分布(a0,b1,a1,……bn,an)，在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路
长的二叉搜索树。
设Pi是对ai检索的概率。设qi是对满足ai<X<ai+1,0<=i<=n的标识符X检索的概率，(假定
a0=－∞且an+1=+∞)。
原创： 转载：
译文： 评论：
展开
个人资料
风仲达
访问：
积分：
等级：
排名：
文章搜索
博客专栏
算法笔记——
《算法设计与分
析》
文章：50篇
阅读：150542
文章分类
java基础
oracle
工具
java框架
linux
操作系统
观点
算法
android
文章存档
2014年12月
2014年11月
2014年10月
2014年04月
2013年12月
目录视图 摘要视图 订阅
登录|注册
195897次
2834
第4587名
57篇 33篇
0篇 117条
(16)
(8)
(5)
(6)
(1)
(1)
(3)
(50)
(1)
(1)
(1)
(3)
(1)
(1)
评论0