Question

折半查找判定树特点

Answer 1

树中的每个结点对应有序表中的一个记录结点的值为该记录在表中的位置 ，常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。

特点如下：

特点1：知道结点的个数就能画出折半查找判定树、进而算出ASL。

特点2：折半查找判定树一定是平衡二叉树（注意树高）。

特点3：折半查找判定树一定是二叉排序树（失败结点个数）。

1、二叉判定树。

是用于描述解决问题的思路，比如可以使用判定树描述N个数的比较过程，是一种对过程的描述。它也可以用于描述二分查找（即折半查找，以下都作二分查找）的过程。

描述二分查找的二叉判定树，我们也可以叫折半查找判定树，从这样的判定树，我们可以分析二分查找算法的效率。

2、长度为n的折半查找判定树的构造方法。

当n=0时，折半查找判定树为空；当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。