爱启航考研 计算机
启航官网 > 计算机 > 计算机备考 > 每日一练 > 文章
分享至

计算机考研每日一练:第七天

关键字: 计算机 考研 每日一练 时间:2019.01.16

数据结构之 平衡二叉树

平衡二叉树,是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。高度平衡?意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。

平衡二叉树的前提是它是一棵二叉排序树。

距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,称为最小不平衡子树。如下图所示,当插入结点37时,距离它最近的平衡因子的绝对值超过1的结点是58。

【考研党必备学习资料包】:考研真题+免费择校择专业+免费考研复习规划,更有考研课程优惠券等你来加购~名额有限立即领取【领取链接】

【爱启航考研辅导课程推荐】:面授课集训营(全年集训半年集训暑期集训秋季集训以及冲刺集训),专业课一对一辅导考研网课全程班包含公共课以及专业课,线上名师弟子班(名师直播授课),这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。


来源:启航考研 责任编辑:yulaoshi
热门活动