news 2026/3/11 16:28:41

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
折半查找判定树是用于描述折半查找过程的二叉树结构

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

  1. 折半查找判定树

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

    • 无论查找成功与否,最大比较次数不超过判定树的深度。
    • 对于 $ n $ 个节点,其判定树的深度为:
      ⌊log⁡2n⌋+1 \lfloor \log_2 n \rfloor + 1log2n+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+1log2(n+1)1
    • 当 $ n $ 较大时,可近似为:
      ASLbs≈log⁡2(n+1)−1 ASL_{bs} \approx \log_2(n+1) - 1ASLbslog2(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 $,则判定树是一棵满二叉树;
  • 否则为完全二叉树或近似完全二叉树。
版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/3/8 17:21:14

达姆施塔特工业大学发现:专家混合模型AI安全机制存在脆弱性

这项由德国达姆施塔特工业大学系统安全实验室的吴立超领导的国际研究团队&#xff0c;联合萨格勒布大学和拉德伯德大学的研究人员&#xff0c;于2025年发表的突破性研究&#xff0c;首次揭示了专家混合模型&#xff08;MoE&#xff09;大语言模型在安全防护方面的惊人漏洞。这项…

作者头像 李华
网站建设 2026/3/8 23:13:30

AI试验数据综合分析管理系统:数据价值的技术解码器

在AI研发与工业试验领域&#xff0c;数据是核心燃料&#xff0c;但杂乱无章的多源数据往往成为效率瓶颈。AI试验数据综合分析管理系统&#xff0c;并非简单的“数据容器”&#xff0c;而是通过多层技术架构&#xff0c;实现数据从采集、治理到分析、安全的全链路智能化&#xf…

作者头像 李华
网站建设 2026/3/11 2:06:52

UltraISO制作U盘启动盘同时部署VoxCPM-1.5-TTS-WEB-UI运行环境

UltraISO 制作 U 盘启动盘并部署 VoxCPM-1.5-TTS-WEB-UI 运行环境 在人工智能语音合成技术迅速普及的今天&#xff0c;如何让复杂的 AI 模型走出实验室、走进实际应用场景&#xff0c;成为许多开发者和企业关注的核心问题。尤其是在没有稳定网络或无法联网的环境中&#xff0c;…

作者头像 李华
网站建设 2026/3/8 23:38:28

导师推荐!8款AI论文软件测评:本科生写论文还能这么快

导师推荐&#xff01;8款AI论文软件测评&#xff1a;本科生写论文还能这么快 2025年AI论文写作工具测评&#xff1a;为何需要这份榜单&#xff1f; 随着人工智能技术的不断进步&#xff0c;越来越多的本科生开始借助AI论文软件提升写作效率。然而&#xff0c;面对市场上琳琅满目…

作者头像 李华
网站建设 2026/3/10 3:20:54

公交移动电视:车载屏幕配合VoxCPM-1.5-TTS-WEB-UI播报站点周边信息

公交移动电视&#xff1a;车载屏幕配合VoxCPM-1.5-TTS-WEB-UI播报站点周边信息 在早晚高峰的公交车上&#xff0c;你是否曾因听不清下一站名而错过下车&#xff1f;又或者听到机械生硬的“下一站&#xff1a;人民广场”时&#xff0c;心里默默期待一句更贴心的提醒——比如“前…

作者头像 李华
网站建设 2026/3/10 19:45:42

奖项申报准备:参选AI创新类比赛提升Sonic知名度

Sonic数字人口型同步技术深度解析&#xff1a;从原理到应用的全链路实践 在AI内容生成&#xff08;AIGC&#xff09;浪潮席卷各行各业的今天&#xff0c;如何以更低的成本、更高的效率生产高质量视听内容&#xff0c;已成为各大平台和企业的核心命题。尤其在短视频、在线教育、…

作者头像 李华