折半查找判定树是二叉排序树吗_折半查找和二叉排序树的时间性能

【王道408数据结构习题整理】7.2 顺序查找和折半查找理论　　前言　　王道408数据结构习题目录　　折半查找　　结论1

　　结论2

　　复习：假定存在一棵树
，若以它的任意节点为根节点的子树的左子树
和右子树
的高度差的绝对值小于等于1，则称
为平衡二叉树。　　折半查找的判定树一定是平衡二叉树。但与前面一个结论：右子树的节点减去左子树的节点为0或1 有出入，请与平衡二叉树的定义区分。　　粗糙地说明为什么折半查找的判定树一定是平衡二叉树。注意，直观上看判定树的生成过程可以看出它是平衡二叉树。　　结论1：假定树的节点为n，则对于每个n，都有唯一判定树形式。　　证明：　　当
时，判定树形式唯一。　　当
时，由于4=1(根节点)+1(左子树节点)+2(右子树节点)，由于
时，判定树形式唯一，则可得
时形式唯一，类似的，
，由于当
时，判定树形式唯一，则可得
的判定树形式唯一。　　至此，我们说明了
时，判定树的形式唯一。　　考虑一棵
个节点的判定树，1)、
时，
，此时它取决于t-1个节点的左子树和t个节点的右子树形式是否唯一；2)、
时，
，此时它取决于t个节点的左子树和t个节点的右子树形式是否唯一。　　由此可知，若保证
$n=\frac{k}{2},\frac{k}{2}-1,\frac{k-1}{2}$ (仅n为整数时有意义)时的子树形式唯一，则
个节点的判定是形式唯一。　　考虑集合
（这么取的原因是我们已经保证了
时判定形式唯一)，正整数
5″ eeimg=”1″>，则在进行任何一种运算
$\frac{n}{2},\frac{n}{2}-1,\frac{n-1}{2}$ 之后的结果
，它仅可能满足2种情况：1、
5″ eeimg=”1″>；2、
$t \in A$ 。我们断言不可能出现
$t \le 0$ 的情况，因为
三种运算都推出
$n \le 5$ ，这与前提条件
5″ eeimg=”1″>不符。　　可以推出，对于每个整数
5″ eeimg=”1″>，经过反复进行其中任何一种运算
$\frac{n}{2},\frac{n}{2}-1,\frac{n-1}{2}$ ，都能保证在某次情况中的最终结果属于
。　　因此，对于任意的
个节点的判定树，它取决于它的左右子树形式是否唯一，而它的左右子树也分别取决于它的左右子树形式是否唯一，这么反复下去直到子树的节点数为1到5以内(为什么？考虑前面的论证)，由于已然证明1到5以内的判定树形式唯一，这样可以最终反推出任意的
个节点的判定树唯一。　　证毕! 　　观察1 ：令
表示节点为
个时判定树的形式，我们将讨论
和
的形式上的差异。　　若
，则
的左子树为
，右子树为
；
的左子树为
，右子树为
，即
和
的形式差别在于右子树，我们需要讨论
和
的形式上差异。

　　若
，则
的左子树为
，右子树为
；
的左子树为
，右子树为
，即
和
的形式差别在于左子树，我们需要讨论
和
的形式上差异。

　　总之，
和
的形式上的差异实际上在于它们的某棵子树
$A(\frac{t-1}{2})$ 和
$A(\frac{t-1}{2}+1)$ 的差异或
$A(\frac{t}{2}-1)$ 和
$A(\frac{t}{2})$ 的差异。　　我们可以列举
以内的差异：

　　对于任意大于5的整数
，则经过
$\frac{t-1}{2}$ 和
$\frac{t-1}{2}+1$ 或者
$\frac{t}{2}-1$ 和
$\frac{t}{2}$ 的运算会将结果的范围变得更小，并且某次范围会落到1到5的整数内。　　也就是说，
和
的形式差异仅仅在于它们某棵子树的某棵子树的某棵子树的某棵子树的差异，直到某棵子树的差异在
以内的情况。而
和
的差异实际就是
和
的差异，
和
的差异实际就是
和
的差异，
和
的差异实际就是
和
的差异。　　综上所述，
和
的差距仅仅在于它们某棵子树的某棵子树的某棵子树的某棵子树的差异，该差异要么是
和
的差异，要么是
和
的差异。

　　结论2：折半查找的判定树一定是平衡二叉树。　　证明：　　假定判定树有n个结点，考虑以树上任意节点为根节点的子树
。　　若
的节点个数在1,2,3内，则易得
是平衡二叉树。　　若
的节点个数大于3，则可以进一步分为2种情况：　　1、
的左右子树节点相同，则根据当节点数相同时，判定树的形式唯一可得
是平衡二叉树；　　2、
的左右子树节点不同，此时必然为右子树比左子树的节点多一，根据观察1的结论，也可得
是平衡二叉树。　　由于
的选取是任意的，故而折半查找的判定树一定是平衡二叉树。　　证毕! 　　结论3：折半查找的判定树只有最下面一层不满，即假定判定树高为h，则它的前h-1层必然是满二叉树。假定判定树的节点个数为
，则判定树的高度为
$\lceil \log_2(n+1) \rceil$ 。　　证明：　　从构造判定树的过程来看，折半查找的判定树只有最下面一层不满，即假定判定树高为h，则它的前h-1层必然是满二叉树这一点是成立的。

　　怎么证明这一点，我说不清楚，感觉从判定树的构成过程就体现了这一点。　　折半查找的判定树只有最下面一层不满，且折半查找的判定树实际上是同等高度的满二叉树的子图。因此，假定判定树的高度为h，则　　
$\begin{align*} & 2^{h-1}-1 < n \le 2^h -1\\ & h-1 < \log_2 (n+1) \le h \end{align*} \\$ 　　故而
$h=\lceil \log_2(n+1) \rceil$ 。　　证毕! 　　结论3

　　最后的折半查找判定树是二叉排序树，失败节点为n+1个。　　分块查找　　分块查找的基本思想

　　注意索引表上的顺序查找和折半查找和我们常规说的不一样。　　索引表上进行顺序查找：　　判断key是否小于等于第一个块的索引值，若为true，转为第一个块查找，若为false，判断key是否小于等于第二个块的索引值，若为true，则转为第二个块查找，以此类推。失败的情况有2种，1、key大于索引表的所有关键字；2、某个块中没有key对应的素。　　索引表上进行折半查找：　　注意，我跟王道上的做法不一样。。。　　观察：　　1、上面的索引表关键字10,20,30,40,50实际上划分了 6个区间
$A_1=(-\infty,10],A_2=(10,20],A_3=(20,30],A_4=(30,40],A_5=(40,50],A_6=(50,+\infty)$ 。　　其中
中素必然不在我们的分块中，因此我们可以先写一个判断代码：　　2、代码框架　　1、在处理key 在
之中的情况后，我们给赋予意义：所在的key仅可能在下标 [low,high] 所在分块中。　　2、while循环中的内部中，有一行代码，至于为什么这么做，原因写在代码里面了。　　3、怎么处理while中的条件？这个是最重要的一环。　　我们进行一些观察：　　1、当
，比如
时，key不匹配的情况：要么，则，此时区间长度变为了2；要么，则，此时区间长度变为了3。　　也就是说当
时，假设key不匹配，则一次循环下来搜索区间长度变为了
$\frac{n-1}{2}$ 或
$\frac{n+1}{2}$ ；　　2、当
，比如
时，key不匹配的情况：要么，则，此时区间长度变为了2；要么，则，此时区间长度变为了2。　　也就是说当
时，假设key不匹配，则一次循环下来搜索区间长度变为了
$\frac{n}{2}$ 。　　综上可知，初始区间为
，假定key不匹配，则一次循环下来受伤了区间长度变为了
$\frac{n-1}{2}$ 或
$\frac{n+1}{2}$ 或
$\frac{n}{2}$ （整数下才有意义)。　　我们断言，对于任意的整数
3″ eeimg=”1″>，在经过
$\frac{n-1}{2}$ 或
$\frac{n+1}{2}$ 或
$\frac{n}{2}$ 的运算后，结果
要么仍然大于3，要么结果是
和
。不可能出现
的情况，因为这会推出
三种情况
，这与前提
3″ eeimg=”1″>不符。　　因此，在执行上述循环体代码时，要么key匹配，要么最后搜索的区间长度为2或3。　　当搜索区间长度为2时，

　　若key不匹配，则最终区间长度为1。　　当搜索区间长度为3时，

　　若key不匹配，则最终区间长度为1或2，对于2的情况，其最终仍然变为区间长度为1的情况。　　总之，若key不匹配，最终的结果是搜索区间长度变为1，即的情况，由于我们所在的key仅可能在下标 [low,high] 所在分块中，因此我们只需要对此时的low(或high)所在分块进行查询即可。　　因此循环的判断应该写为。　　完整的代码如下　　

　　针对此表，设计测试案例 7,8 20,30 12,19 43,50,51 　　测试代码　　测试结果

折半查找判定树是二叉排序树吗_折半查找和二叉排序树的时间性能

相关推荐