数据结构

3.11 最优二叉搜索树Optimal Binary Search Trees

数据结构

1二叉搜索树 2最优二叉搜索树 3最优二叉搜索树问题描述 4最优子结构性质 5递归计算最优值(具体算例) 6算法

数据结构

1 二叉搜索树

是一棵空树或者满足以下的性质： 每个结点作为搜索对象，它的关键字是互不相同的。 对于树上的所有结点，如果它有左子树，那么左子树 上所有结点的关键字都小于该结点的关键字。 对于树上的所有结点，如果它有右子树，那么右子树 上所有结点的关键字都大于该结点的关键字。

数据结构

1 二叉搜索树

xal

wan wil yo

zol zom yu m yon

wen

wim wulxem

xul

zi

搜索过程：从根结点开始，如果根为空，则搜索 不成功；否则使用待搜索值与根结点比较，如 果待搜索值等于根结点关键字，则搜索成功返 回，如果小于根结点，则向左子树搜索；如果 大于根结点，则向右子树搜索。4

数据结构

1 二叉搜索树

对于一个给定的关键字集合，可能有若干不同的 二分检索树 如对保留字的子集 Name: 1 2 3 4 5 for if loop repeat while 的两棵二分检索树为if forrepeat loop while for if repeat

a

考虑a图和b图中最 坏比较次数和平均 比较次数

loopb

while5

数据结构

if for repeat loop a

if while forloop b

1 二叉搜索树

repeatwhile

构造不同的二叉搜索树就有不同的性能特征。

二叉搜索树a在最坏情况下找一个标识符需要4次比 较，而b表示的二分检索树最坏情况下只需3次比较。 假设只作成功的检索并且检索每个标识符的概率相同， 则两棵二分检索树在平均情况下各需要12/5和11/5次 比较。6

数据结构

2 最优二叉搜索树

二叉搜索树存在的问题

1 在实际中会遇到检索不成功检索的情况。2 在实际中，不同标识符被检索到概率不同

3相同关键字构成二叉搜索树检索效率不一样

数据结构

2 最优二叉搜索树

在实际中会遇到检索不成功的情况。 扩充二叉树：当二叉树里出现空的子树时， 就增加新的、特殊的结点——空树叶。对 于原来二叉树里度数为1的分支结点，在它 下面增加一个空树叶；对于原来二叉树的 树叶，在它下面增加两个空树叶。 扩充二叉树是满二叉树，新增加的空树叶 (以下称外部结点)的个数等于原来二叉 树的结点(以下称内部结点)个数加1。

数据结构

2 最优二叉搜索树xal

wan wil wen wim wul xem yo xul yu m

zol zom

yon

zi

A

A代表其值处于wim和wul之间的可能关键码集合9

数据结构

2 最优二叉搜索树

在实际中，不同标识符会有不同的检索概率。

设bi是对xi检索的概率。 设ai是对满足xi<x<xi+1,0 i n的标识符x检 索的概率， (假定x0=- 且xn+1=+ )。b1 b2 bi b(i+1) b(n)

E0 a(0)

x1 E1 x2 a(1)

xi Ei xi+1 a(i)

xn En

a

(n)

数据结构

2

最优二叉搜索树

最优二叉搜索树问题描述 设 S={x1, x2, · · · , xn} 是一个有序集合，且x1, x2, · · · , xn表示有序集合的二叉搜索树利用二叉 树的顶点存储有序集中的元素，而且具有性质：– 存储于每个顶点中的元素x 大于其左子树中任一个 顶点中存储的元素，小于其右子树中任意顶点中存 储的元素。二叉树中的叶顶点是形如(xi, xi+1) 的开 区间。 (1) 在二叉树的内部顶点处找到： x = xi (2) 在二叉树的叶顶点中确定： x∈ (xi , xi+1)11

数据结构

2 最优二叉搜索树

找到元素x = xi的概率为bi;确定x∈ (xi , xi+1)的 概率为ai。其中约定x0= -∞ , xn+1= + ∞ ,有

数据结构

2 最优二叉搜索树

在一个表示S的二叉树T中，设存储元素xi的结点深 度为ci;叶结点(xj,xj+1)的结点深度为dj 。

表示在二叉搜索树T中作一次搜索所需的平均比 较次数。P又称为二叉搜索树T的平均路长，在 一般情况下，不同的二叉搜索树的平均路长是不 同的。

数据结构

2 最优二叉搜索树

在检索过程中，每进行一次比较，就进入下面一层， 对于成功的检索，比较的次数就是所在的层数加1。 对于不成功的检索，被检索的关键码属于那个外部结 点代表的可能关键码集合，比较次数就等于此外部结 点的层数。

数据结构

3 最优二叉搜索树问题

对于有序集S及其存取概率分布 (a0, b1, a1, · · · , bn, an),在所有表示有序集 S的二叉搜索树中找出一棵具有最小平均路 长的二叉搜索树。 结点在二叉搜索树中的层次越深，需要比 较的次数就越多，因此要构造一棵最小二 叉树，一般尽量把搜索概率较高的结点放 在较高的层次。15

数据结构

例 标识符集{1, 2, 3}={do, if, stop}可能的二 3 分检索树为：1 12 3 2 3 2

3

1

3

12 1

2

(c)(a) (b) (d) (e)

设每个内、外结点检索的概率相同：pi=qi=1/7, 求每棵树的平均比较次数(成本)。 若b1=0.5, b2=0.1, b3=0.05, a0=0.15, a1=0.1, a2=0.05, a3=0.05,求每棵树的平均比较 次数(成本)。 16