这一讲，介绍最优 二叉检索树。二叉检索树，
它是把一个数组的元素排列到一棵树上，然后通过这棵树的算法
来检查某一个x是不是在这个数组里面，这个数组的元素
我们记作x1到xn，它是排好序的，比如说是n个数，就是
x1到xn，然后把这些元素存储在一棵二叉树的结点上，
来查找某一个给定的x是不是在这些个数里出现。
如果在的话，我们输出它在数组的哪个位置，如果不在的话，
我们就输出它不在这个数组里面。它不在数组里面正好反映在它在这棵树的空隙结点上，
就是方结点。这是一棵二叉树的例子，原来的存的数是1、2、3、4、5、6，
按照从小到大的顺序排好了，我们可以把这些个数呢放
在这棵树的结点上，就是这些个圆结点，这个圆结点是数据结点，
正好是数组中的六个数，那么这些个结点方结点叫做空隙结点。
如果在检索的时候，到达了这样的空隙结点，就表示x不在这个数组里面。
这是第一个空隙，就是说如果检索的那个数比1还小，就会落到这个结点
上。那么这个第二个空隙是，如果检索的数是在1和2之间，
就会落在这个结点上，那这是第三第四第五第六，这是最后一个空隙，这个空隙
就表示检索的x比6还大，它也不在数组里面，这就是一棵二叉检索树。
下面我们看一下这个检索的方法，初始的时候呢，x
和这个树根进行比较，如果x比这个根元素还小的时候，
它就进入左子树，把左子树那个根结点，
也就是原来这个x所在的那个树根，这个树根的儿子
把它看作左子树的根结点，同样的递归的按照这个算法往下走。如果x大于
根元素的话，它就递归的进入右子树，也按照同样的算法 向下检索。如果x等于根元素的时候，
算法停止，输出x所在的位置。
那么不管怎么样，x只要到叶节点，算法
一定停止，这个时候就输出x不在数组里面，下面我们看一下刚才那个例子，这是
刚才那棵二分检索树，组织成这样一个结构。
这是原始的数组，要检索的x是3.5。
它的检索过程就是先和树根4比较， 3.5比4小所以它就进入左子树，
下面就和这个2进行比较，那么3.5比2大，它就进入右子树，
就和3进行比较，和3比完了，3.5比3还大，就进入它的右结点，
这个时候进入到树叶，算法停止，说明3.5不在数组里面，那么
它处在什么位置呢？我们看到是第四个空隙，也就是说第一、第二、第三、第四，
正好被检索的元素处在3和4之间，这时候就输出了，这是它的检索算法。
那么在元素都是 概率，就是它出现在数组中的概率如果都是一样的时候，这棵树
组织成一棵均衡的树，是一个好的树。但是有的实际问题
被检索的元素出现在数组中的概率是不一样的，它是有着某种
概率分布。我们可以把概率分布用下边的这样的形式来表示，
x在数组的每个元素它可能会有 一个概率，比如说它就是数组的第一元素，第二元素等等，
一直到第n个元素，这样会有n个数字来表示它的概率，还有可能x
不在数组里面，那我们就用空隙的概率来表示，比x1还小的，
我们记作第一个空隙，就是x0，x1，这个x0的值可以看作负
无穷。那么在第一个数跟第二个数之间的空隙记作x1，x2
一直到它比最后一个数还大的空隙，比xn还大的空隙。
那么这个x n加1呢实际上就是正无穷，那么这就有了
n加1个空隙，这些空隙也有概率，也就是x可能处在某个空隙
之中，它也有一个概率。那么这就是说给定的这个
被检索的数组的元素，x1到xn我们用一个序列来表示它。
x在某一个xi的概率，就是它是数组元素第i个元素
的概率记作bi，那么它在空隙xi到x i加1
就是在这两个之间的这个空隙，这个概率记作ai。
这样的话就可以把x在n个位置和n加1个空隙的概率都把它列出来，
也列成一个数组。那么这里边凡是b的位置都是x在数组中的概率，
凡是在a的位置都是在空隙中的概率，一共2n加1 个概率值。那么这就是问题的输入，
一个是给定的数组，还有一个它的概率分布，我们问一问在这样概率分布的条件下，
这棵树应该组织成一个什么样子，使得我们检索 平均的比照次数做到最少，这是问题。
下边我们来看一个例子，这里边一共有六个 排好序的元素，然后这个就是概率分布。
这两项一个元素的序列，还有一个概率分布， 是问题的输入。那这里边我们看到这个红颜色的
都是x在 这六个位置的概率，那这是x是1的概率，这是
x是2的概率，一的直到x是6的概率，0.05。
好，那么这些黑颜色的这些个值都是空隙的概率，就是x不在数组中，那么有
这样多个空隙，这些空隙的概率我们也按照顺序把它列到这个输入里头，所以这两个就是
这个实例的输入。那么我们下边再来看一看
对于这样的分布，它就是作为问题的输入给出来了，
我们的算法就是要对于这样的分布给出一棵检索次数，就是平均的比较次数最少
的一棵二叉检索树，这是问题的 要求。下边我们看一下你怎么来计算它的
检索的平均时间，也就是说我检索一个数据它 所需要的平均的比较次数，这是那棵树。
我们假定组织成这个样子，这是刚才给定的那个实例的输入，
这是它的概率分布，我们组织成这样一棵树，那么在这棵树上， 如果我要平均检索x的话，需要比较多少次呢？
可以按照下面的公式来计算，我们看一下这个公式。
这个T1就是这个树的名字，m就表示对在这棵树的条件下
它的平均的检索次数，下面我们来看一下怎么计算。
先看它的第一项，就是说如果x就是数4，恰好被检索的x就是等于4，
那么它只，因为按照检索的时候，是先从 根往下走，所以它比较一次就可以知道x在数组里头。
那么比较一次的这个输入的概率是多少呢？是0.1，这正好是一二三四，
第四个数的概率，所以我们用这个工作量比较次数 乘以概率，就是它的第一项，1乘0.1。
然后下边我们看到，如果x是2或者是6的话，它需要比两次，比如说是2，
先和4比，比4小，进入左子树，再和2比，知道
x就是2，算法停止了，需要比两次，那么6也是同样的。
那么比两次，就是这两个数，就是在树的
第一层，这个叫第零层，这个是第一层，在第一层的话它需要比两次，这个概率是多少呢？
比两次的概率一个是0.2，一个是0.05，正好就是这个0.2和0.05，所以这是- 针对它的
这部分计算的值。然后我们同样的可以看这三个结点，
这是比三次，它们的概率就是0.1、0.2、0.1
乘以3，所以在这个第一个方括弧，在第一行
所计算的都是x在数组里的它所对应的
这些个工作量。那么除了这些个以外，x还可能处在空隙，它不在数组里面，
那我们看到，如果x要是处在这一层进入到这一层的叶节点，
那这一层在树中是第几层呢？第零层，这是第一层。
这是第二层，这是第三层，那么它进入这个结点呢，只需要跟它的父结点比过以后，
就知道，它会进入到这个结点，在这个结点本身本身并没有比较操作，
所以在这一层的结点，它是第三层，它只需要每个 结点都需要比n次就可以了，那就是说我们会有这一项，
这是比较次数3次，那这些个结点的概率是多少呢？我们就是
这六个概率值，一二三四五六，所以这是针对空隙结点的
工作量，那么除了这个以外呢，还有这个，这个空隙结点，它是处在第二层，只需要比两
次，这个乘以它的概率，按照这样的公式我们可以算出来，如果要检索一个x的话，
在这样组织的一棵二叉检索树，它需要比较2.51次，这个就是它的
计算的平均的工作时间，这是这棵树。
那么对于同样的输入，可能有其他的树的结构。
比如说我们看到这样一棵树，它的输入跟刚才一样，还是这个
实例，但是它的树组织的是另外的一个结构，我们以1号结点作为树根，
然后顺序地这样把它排下来，这样构成的一棵树。那么按照刚才同样的方法对这棵树
我们也可以计算一下它的平均的检索时间，那么这个T2这棵树平均的检索时间呢，
也是按照刚才的办法来算，根结点检索一次，这个概率是0.1，就是这个第一个概率。
然后在第二层，就是这个2号结点，它的概率是0.2，检索两次。
这个4号结点是检索3次，0.1，然后
这个6号结点是检索4次，还有一个3号结点，这两个是
检索4次，0.2加0.05，然后这个结点，这个是要检索5次的，乘以0.1。
然后下边的这一行，计算的都是每一层的空隙结点所需要的
工作量都在这一层里头，根据这个公式跟刚才同样的办法
把它最后计算出来，这个结果是3.25。
那刚才的是两点几，这个是3.25，可见这棵树
它的工作量比上一棵树工作量要大，因此从我们的想法来看，这
不是一棵好的树，刚才那棵树比这棵树的检索时间要少，那是一棵组织的更合理的树。
下边我们把这个问题把它描述一下，
这个是输入的数据集，一共有n个数，这个是它的存取概率分布， 这个也是输入的结果，然后我们假定
看看它的那个检索次数，应该那个，公式应该怎么写呢，我们可以看一下这个简单的树。
这个叫做第零层，这两个叫做第一层，这个叫做第二层，那么层数反映的是
从根到它的路径上有几条边，像这个结点这是一条边两条边，就是路径长度。
那么根结点的路径长度是零，我们刚才的计算中已经看到了
如果是这种圆结点，就是数据结点，它的检索次数刚好等于
它所在的层数加1，比如说这个3号结点，我们要从根向下走， 这样比较一次，这样比较一次，才知道x恰好等于3。
所以这个层数是1，但是它的比较次数是2。
刚好层数加1，但是对于这种方结点，空隙结点，
它的比较次数就是它所在的层数，比如说这个结点是第一层，那么如果x
处在这个空隙的话，它只要和根比一次就可以向右一走就走到空隙结点了，而在空隙结点是没- 有比较操作的。
所以空隙结点的工作量就等于它的层数，我们把这个总结成下面
的公式，如果这个xi它是在数据结点，
这个d(xi)代表xi的深度，也就是它所在的层数，用这个层数加上1，
再乘以它的概率这就是刚才我们的这个计算方法。如果这个x是
落到这个，最后会落到这个树叶结点，就是这个方结点，它是一个空隙结点，那这个情况下
它的工作量就等于它的深度，也就是它的层数，比如说这个就是2，再乘以它的
概率。这边这个项计算的是所有空隙结点的
按照它的深度，也就是它的比较次数乘以概率的和。
而这一项呢，计算的是所有数据结点，就x恰好在数组中的，
它的深度加1就正好是它的比较次数，再乘以
概率求和，那么这就是刚才那两个实例，
计算平均比较次数的公式，就是这样的公式。下面我们把
这个问题提出来，问题是给定的是数据集还有它的概率分布，
这两个是输入，问题的输入，要求你找一棵最优的
检索树，那么这个检索树呢是平均比较次数最少的这样的一棵检索树。
我们是，这是问题的解，就是这棵树。
下面把这一讲的内容小结一下，这讲呢首先先定义什么叫二叉
检索树，它的构成是什么样子。然后我们介绍了
它的在给定概率分布下，一棵二叉检索树的它的平均检索时间的估计。
就是刚才给的那个公式，包括它的数据结点和空隙结点分别
工作量乘以它的概率求和，这样一个公式，然后我们介绍了什么是最优的二叉检索树，
就是平均检索时间最少的那棵检索树，那我们的问题就是给定你一个
数组，给定你这些元素，它的概率分布，和空隙的概率分布，你来构造一棵
最优的二叉检索树，这就是问题的要求，这是这一讲的主要内容。
Wanling QuProfessor
