软设每日打卡——折半查找二叉判定树、平衡二叉树
对长度为n的有序顺序进行折半查找(即二分查找)的过程可用一颗判定树表该判定树的形态符合( )的特点。
A、最优二叉树(哈夫曼树) B、平衡二叉树
C、完全二叉树 D、最小生成树 答案:B
解: 折半查找又称二分查找,要求表有序,即表中元素an关键字有序,而且必须顺序存储。
折半查找可用一个称为判定树的二叉树描述(如题所述),判定树中的每一个结点对应表中的一个元素,但结点的值不是关键字的值,而是元素在表中的位置。
题目只是在问折半查找的判定树的形态,那么这里我们主要需要记住的点是,折半查找判定树必为平衡树(平衡二叉树)。即由折半查找过程中所产生的树,首尾以二取整。
那么为什么折半查找判定树一定是平衡二叉树?因为折半查找的过程是每次将查找区间折半,然后根据中间元素与查找值的大小关系确定下一步的查找区间,这个过程可以看作是在一颗二叉树上进行的。折半查找树是一种二叉搜索树,它的每个节点都满足左子树的所有节点的值都小于节点的值,右子树的所有节点的值都大于节点的值。(这句没太懂,我再研究一下)在折半查找树中,每个节点的左子树和右子树的高度差不超过1,因此它是一棵平衡二叉树。判定树是一种用于分析算法的数据结构,它用来表示算法在处理输入时所做的决策。对于折半查找算法,其判定树的每个节点表示一个比较操作,它的左子树和右子树分别比当前节点小和比当前节点大的元素。由于折半查找树是一颗平衡二叉树,因此它的判定树也一定是一颗平衡二叉树。
移到上方
平衡二叉树是一种特殊的二叉树,它的左右子树高度差(简称平衡因子)的绝对值不超过1(即-1,0,1),这样可以保证树的高度不会太高,从而保证了树的查找效率。
平衡二叉树的两个条件:
1、是二叉排序树
2、任何一个节点的左子树或右子树都是平衡二叉树(左右高度差小于1)
横线复制
这里拓展一下这个判定树的画法,我看的这个博主的文:(这个电脑粘贴坏了,后续我补充)
满二叉树(Full Binary Tree):
所有节点的度要么为0,要么为2,且所有的叶子节点都在最后一层。
不全的内容我后续补充