折半查找判定树是用于描述折半查找过程的二叉树结构

折半查找判定树是用于描述折半查找过程的二叉树结构。树的根节点为查找区间的中间元素，左子树对应前半部分子表，右子树对应后半部分子表，递归构造形成一棵逻辑上的二叉搜索树。

1. 折半查找判定树

   • 树中每个节点代表一次比较的关键字。
   • 查找成功时，查找路径从根到该节点，比较次数等于该节点所在的层数（根为第1层）。
   • 查找失败时，查找路径走到某个空指针为止，比较次数等于路径上经历的内部节点个数（即未命中路径上的非叶节点数）。

2. 查找次数的上限

   • 无论查找成功与否，最大比较次数不超过判定树的深度。
   • 对于 $ n $ 个节点，其判定树的深度为：
     ⌊log⁡2n⌋+1 \lfloor \log_2 n \rfloor + 1⌊log2​n⌋+1
     这也是最坏情况下所需的比较次数。

3. 平均查找长度（ASL）

   • 当 $ n = 2^h - 1 $，即判定树为满二叉树时，在等概率查找成功的条件下：
     ASLbs=n+1nlog⁡2(n+1)−1 ASL_{bs} = \frac{n+1}{n} \log_2(n+1) - 1ASLbs​=nn+1​log2​(n+1)−1
   • 当 $ n $ 较大时，可近似为：
     ASLbs≈log⁡2(n+1)−1 ASL_{bs} \approx \log_2(n+1) - 1ASLbs​≈log2​(n+1)−1
     表明折半查找具有对数级的平均性能。

4. 折半查找的适用场景

   • 优点：时间复杂度为 $ O(\log n) $，远优于顺序查找的 $ O(n) $。
   • 限制条件：
     • 要求数据在顺序存储结构中（如数组）；
     • 关键字必须有序；
     • 插入和删除操作代价高（需移动大量元素）。
   • 典型应用：适用于静态或准静态数据集，例如只读数据库、配置表、频繁查询但极少更新的场景。

defbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmid# 查找成功，返回索引elifarr[mid]<target:left=mid+1else:right=mid-1return-1# 查找失败# 示例使用arr=[1,3,5,7,9,11,13]target=7result=binary_search(arr,target)print(f"目标值{target}在索引{result}"ifresult!=-1else"查找失败")

根据给定的有序数组构建折半查找判定树，本质是模拟折半查找过程中每次选取中间元素作为根节点，并递归地对左右子数组构造左、右子树的过程。最终形成的二叉树即为折半查找判定树。

构建步骤：

1. 选中间元素为根：对于当前有序子数组arr[left:right+1]，取中间位置mid = (left + right) // 2，对应元素arr[mid]作为当前子树的根。
2. 递归构建左右子树：
   • 左子树由arr[left:mid]构成；
   • 右子树由arr[mid+1:right+1]构成。
3. 终止条件：当left > right时，返回空节点。

Python 实现（构建判定树并输出结构）：

classTreeNode:def__init__(self,val=0):self.val=val self.left=Noneself.right=Nonedefbuild_binary_search_decision_tree(arr,left=0,right=None):ifrightisNone:right=len(arr)-1ifleft>right:returnNonemid=(left+right)//2root=TreeNode(arr[mid])root.left=build_binary_search_decision_tree(arr,left,mid-1)root.right=build_binary_search_decision_tree(arr,mid+1,right)returnroot# 中序遍历查看树结构（应保持有序）definorder_traversal(root):ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)# 层序遍历打印树结构（更直观）defprint_level_order(root):ifnotroot:print("Empty tree")returnfromcollectionsimportdeque queue=deque([root])result=[]whilequeue:node=queue.popleft()ifnode:result.append(node.val)queue.append(node.left)queue.append(node.right)else:result.append(None)# 去掉末尾多余的 Nonewhileresultandresult[-1]isNone:result.pop()print("Level-order traversal:",result)# 示例使用arr=[1,3,5,7,9,11,13]root=build_binary_search_decision_tree(arr)print("Original array:",arr)print("Inorder traversal:",inorder_traversal(root))# 应与原数组一致print_level_order(root)

输出示例：

Original array: [1, 3, 5, 7, 9, 11, 13] Inorder traversal: [1, 3, 5, 7, 9, 11, 13] Level-order traversal: [7, 3, 11, 1, 5, 9, 13]

这棵树的根是 7（中间），左子树以 3 为根包含 [1,5]，右子树以 11 为根包含 [9,13]，完全符合折半查找逻辑。

注意事项：

• 判定树的形状取决于数组长度和中间点选择方式（向下取整）；
• 若 $ n = 2^h - 1 $，则判定树是一棵满二叉树；
• 否则为完全二叉树或近似完全二叉树。